Доброе время суток! С вами снова успевший уже всем надоесть AlTimin и я снова поднимаю себе вклад освещаю второй тур XXIV Международной олимпиады по информатике, который вот-вот должен начаться.
Условия тут
Говорят, что контест начался в примерно в 11:15 по Москве, но итальянцы снова тупят и таблички рельзультов пока нигде нет.
Пока все ждут таблички результатов, напомню про результаты первого тура. Российская сборная: Zlobober (258 баллов, 7 место), tigvarts (213 баллов, 22 место), yeputons (204 балла, 24 место), Copymaster (196 баллов, 29 место). В этом году ожидается примерно 27 золотых медалей (может быть плюс-минус одна), так что у наших есть все шансы взять четыре золота, чего не было уже восемь лет
0:15: Табличка результатов появилась. Контест начался в 11:20 по Москве.
0:18: Первый сабмит! Макс Ахмедов, 11 баллов по первой задаче!
0:30: А теперь о задачах. Их снова три. Первая: найти сумму всех попарных расстояний между клетками некоторой замкнутой клетчатой фигуры, не содержащей внутри себя дырок (то есть её дополнение тоже связно). Вторая: Есть кэш размера K и N объектов. Кроме этого, есть N запросов. При запросе некоторого элемента он должен быть пом ещен в кэш. Хочется как можно меньше раз выкидывать объекты из кэша. Утверждается, что при известной последовательности запросов оптимальное решение — выкидывать элемент, который понадобится как можно позже. Участникам же надо последовательности запросов составить себе некоторую подсказку длиной не более M бит. После этого у них будет в распоряжении только их подсказка, и по одному будут приходить запросы. Надо сделать так, чтобы решение было оптимальным. Третья: есть N рыцарей с силой от 0 до N-1. Проходит некоторое количество раундов вида "взять подотрезок с l по r и оставить только победителя (рыцаря с максимальной силой)". Последний рыцарь опоздал, и мы можем поставить его на любое место (порядок остальных мы знаем). Максимизировать количество раундов, в которых он примет участие.
0:35: Еще самбиты на 32 балла по первой задаче. Сегодня самая простая задача — третья, но она немного неприятна с точки зрения реализации. Думаю, что будет по ней много сотен, начиная примерно с часа после начала контеста.
0:55: Судя по тому, что уже 20 минут нет никаких изменений, то у них что-то сломалось. Надеемся, что только табличка.
0:56: Табличка со мной согласилась и приказала долго жить. 502 Bad Gateway.
1:00: Положил сюда условия.
1:05: Пнул SC. Табличку починили. Из интересного — сотня у Егора. Ждем еще три сотни по третьей от наших.
1:15: Леша получил 32 по первой. У Олега пока ничего, видимо занимается сотней по третьей. А Хо пока чего-то не хо-хо.
1:25: Гена и Егор получили 43 по второй задаче. Китайцы выкатили свое чудо-оружие из Шаолиня. Они совсем не палятся — чувака зовут Chao Li.
1:35: Две синхронных сотни по третьей задаче. Макс и Олег мужики. Ждем Лешу.
1:36: Сотня от британца по не особо точной второй задаче. Хм.
1:50: Хо нахохочил сотню по третьей. А вот британца, который получил сотню по второй, жалко. Он был одним из трех, кто получил полный балл по неточной задаче в первом туре. К сожалению, у него ноль по rings: видимо, не успел отдебагать. Жаль. :(
2:00: Два часа, полет нормальный. У Гены вторая сотня.
2:05: Макс и Егор набирают свои баллы по первой. 55 у Макса, 32 у Егора.
2:10: У Егора 55 по первой. Что-то Леша и Олег затихли.
2:15: Егор четвертый, Макс второй. В принципе, можно уже заканчивать контест прямо сейчас.
2:30: Программа-минимум для адекватных участников сегодня 55-43-100, видимо. А тем временем мы начинаем обратный отсчет.
-2:25: Как гласит известный анекдот, если у телефона на android осталось 95% заряда батареи, то его надо зарядить. Я это к тому, что мой телефон внезапно может разрядиться в ближайшее время. Но не переживайте, мысленно я с вами!
-2:20: Так просто вы от нас не избавитесь! Добрые организаторы дали нам розеток, так что мы можем вам надоедать еще некоторое время.
-2:15: Вести с полей: у Егора сотня по первой задаче. Это первая сотня по первой задаче, и теперь контест является хорошим: каждую задачу кто-нибудь решил, и никто не решил все задачи.
-2:13: У Олега 33 по второй задаче. Полезно для общего развития.
-2:10: Первая тройка: Гена, Егор, Макс. Идеально. Сейчас еще Леша с Олегом подтянутся, надеюсь.
-1:57 У Леши сотня по третьей. Ему осталось получить что-нибудь по второй для полного счастья.
-1:55: Хо, к сожалению, такой хо. Сотня по первой и первое место на данный момент.
Радио Codeforces: А сейчас для вас прозвучит композиция "Джонни Хо, Джонни Хо, Джонни Ха-Ха".
-1:50: Тем временем, Егор и Макс медленно опускаются вниз. Сейчас они на четвертом и пятом местах. Перед ними Хо, Гена и какой-то японец. Олег шестнадцатый, Леша двадцать первый.
-1:40: Наше хо-хо сильнее из хо-хо! Гена получил 77 баллов по первой. Судя по тому, что у него не прошла третья подгруппа, которая по смыслу вложена в четвертую, то у кого-то слишком хорошие тесты.
-1:35: Что логично, у Гены третья сотня за этот тур. Надеемся, что Хо его не догонит.
-1:20: 39 от Леши по второй задаче. Теперь можно с 99% уверенностью говорить, что у России четыре золота. Тем не менее, интрига сохраняется: что сделает мистер Хо и сдаст ли Макс вторую на 100?
-1:15: Хо.
-1:10: Для топа они тур перехалявили. Кроме того, сейчас первое место от 27-го(нижняя граница золота) отделяет почти 300 баллов.
-1:07: Третий полный балл. На этот раз у Егора.
-1:00: Час до конца контеста, полет нормальный. Леша сдал первую на 55.
-0:20: Конец контеста близок. Наши уже почти час ничего не делают. Тем не менее, у них все хорошо.
-0:15: Вот что мне не нравится в этом контесте, это то, что последние полтора часа никакой интриги нет. Заморозку бы для пущего интереса.
-0:10: Теперь у трех наших по 198 баллов, причем с одинаковой разбивкой по задачам. Мейнстрим!
-0:05: Как-то без огонька проходит конец второго тура XXIV IOI.
-0:00: По четыре золота у нас и у Китая, но у нас меньше сумма баллов за оба тура.
Объявление после тура во время показа результатов: "У вас есть бесконечное количество токенов. Используйте их с умом".
Обновили табличку: http://carp.di.unipi.it/
Появилась http://carp.di.unipi.it/
Появилась Your text to link here...
Как задачи ? Есть у Гены шансы, что у Американца макс бала не будет ?
Задачки клевые. Сходу не очевидно, как их решать, так что они содержательные. Кроме этого, там есть некоторая неточка. Видимо, на ней все и будет решаться.
Клево! Радует что спустя три года вновь что-то содержательное начали давать.
Задачи хорошие. Мы пока не умеем решать две сабтаски во второй (35 + 39 — eps) и одну сабтаску в первой (45). Правда не сказать, что бы я сильно долго думал, не засыпая при этом. Подробнее будет в ближайшее время.
Запасной вариант.
Кстати, насколько правильно считаются медали?
Ахах, где-то я уже читал задачу про опоздавшего на турнир )))
Не-не-не. Эта совсем тупая. Но легенда тоже порадовала.
И правда легкая очень, там же лог можно оставить или надо линейное решение ?
Там размер массива до ста тысяч. Лог.
Опытные участники вполне могут испугаться, к сожалению. На самом деле она не очень интеллектуальна.
А можете ограничения первой тоже сказать?
три сабтаска не о чем, четвертый 105 клеток, координаты int.
По третьей задаче: l и r мы тоже можем выбирать сами или они случайны и тогда нам надо максимизировать мат. ожидание или минимальное количество раундов?
Они даны
Заданы.
А можно задачи поподробнее? С ограничениями и более формально?
Как вам будет угодно
Хо тоже нахохочил 3ю на полный балл.
Остаётся надеяться, что только Гене покорится 45 по 1й.
Наверное, имелось ввиду 43 по второй :) Но по ней у всех будет сильно больше, еще больше половины контеста осталось.
Ну, 2ю уже закрыли — наверное больше шансов, что закроют и другие участники. А вот первую целиком — ещё нет.
Тогда 55, а не 45. Там нет ничего особо сложного, Гена эти баллы получит. Я думаю, что по первой сотня у него будет. А вот насчет второй не уверен.
А я уверен)
и я!
О, теперь и я уверен)
Очень красиво будет, если Гена наберет 55 по первой, а Хо — 43 по второй.
Получить по первой 55 для Гены (1,2 — просто напиши BFS; 3 — просто посортай координаты и выдай ответ) — дело 10 минут. Думаю, он пишет 100.
Думаю, имелось в виду именно то, что написано. Просто 55 по первой заходит у многих.
#alex_kpr_рекомендует?
При придумывании тегов ни один Alex_KPR не пострадал.Alex_KPR безжалостно и беспощадно рекомендует
Молодец. Можешь подойти ко мне и забрать свой паспорт.
сперва из ящика выпустите
да, и одежду отдайте
Посмотрю на твое поведение.
Жалко. У Хо есть шансы обогнать Гену.
Текущая сумма баллов по странам
Текущее количество медалей по странам
страна Italy2?
Страна-хост имеет право выставить неофициальный состав.
Там восемь человек.
snarknews немного не прав. Должно быть две команды: Italy и Italy2.
Разделил Италию и Италию2 (по сумме очков уж точно разделять надо).
В том году давали сертификат "Equal to * medal"
Суворов затащил первую.
Надеюсь, товарищ Хо не испортит контест
Хохокалка не выросла.
Выросла
Задача А, похоже, вполне решаемая на 100 по такой идее:
Пойдем сверху вниз и построим граф объединения. Вершинами его будут максимальные горизонтальные отрезки карты, два отрезка соединены ребром, если они касаются. Это будет деревом потому, что дополнение связно (любой цикл этого графа ограничивает связную область).
Дальше, видимо, только технические сложности в том, чтобы пустить DFS по этому дереву, возвращать из потомка для каждой его клетки количество кратчайших путей через нее и все аккуратно пересчитывать.
Я думал в сторону просто покрыть непересекающимися прямоугольниками так, чтобы не было циклов. Но твой вариант более добрый с реализационной точки зрения.
random.johnnyh доминирует.
Неужели можно так (что Гена будет ниже в рейтинге хотя бы на 17 минут) за два года прокачаться?
Это один, отдельно взятый контест. Причем с очень строгими правилами применимости задач. В любом случае, В — задача на придумку, а А — "стандартная" задача, так что мало сомнений, что у Гены этот тур 300, но есть, что у Johnny 300.
Утверждается, что B не очень интеллектуальна. Решение от Burunduk1: для каждого запроса храним, доживет ли этот элемент в кэше до того, как про него спросят следующий раз. N бит.
Да, действительно.
Ну, все же N+K (нам же про начальные элементы тоже это знать нужно). Этого все равно хватает на 100
У Гены по А:
1 — OK 2 — OK 3 — 0 4 — OK
это как?
Найти тех, кто делал тесты и побить их канделябром (так же возможны другие варианты по вашему вкусу).
Канделябр вполне в моем вкусе. Интересно, применит ли Гена кулхак "если выполняется условие задачи 3 — решать халявой"? :)
Судя по скорости, он просто нашел у себя багу.
Причем, раз тесты группы 4 не поймали, простую. В духе числа в int помножил, упало на каком-то вытянутом случае.
Ну это называется "какого лешего"? Почему этого частного случая нет в четвертой подгруппе?
Осталось Гене закрыть последние 32 и может идти
мешать Джонниотдыхатьуже
Уже можно не мешать.
НЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕТ!
600 у Джонни. Да уж.
#Геннадий_не_одержал
Хо-то таки торт
=(
Кто-нибудь ещё видел это? В середине контеста по первой задаче первого дня (odometer) в табличке организаторов было три сотни, причём третья у кого-то из глубины таблицы (может быть, Marco Keller?). Теперь опять две. А вчера сотен было тоже две?..
Три сотни сегодня видел.
Говорят, что у них был "Analysis Mode", т.е. после тура во время просмотра своих результатов можно было посдавать решения. Сейчас они, естественно, это отрубили нафиг.
То есть это дорешивание просочилось в табличку?
В общем, если организаторы знают, в чём было дело — скорее всего, всё хорошо.
Видимо.
Вот так всегда. На соревнованиях по программированию решает все программирование автомата без памяти.
Ладно, Гене соболезнуем, но наша сборная-то сейчас просто молодцы! Li Chao немного сливает, и у нас на текущий момент по медальному единоличное первое место.
27 золота. Пока у Китая тоже 4.
Да, Li Chao очнулся, теперь, вроде, от 4 золотых никуда не денемся ни мы, ни они.
Upd. Счет по сумме баллов 1751-1742 в нашу.
Егор красавчик) Три сотни это именно то, что было нужно)
Ура, молодцы наши, 4 золота)))
Я думаю, что Хо просто вовремя использовал эту карту. И мои искренние поздравления Егору, за которого я болел.300 это самое оно)