Доброе время суток! С вами снова успевший уже всем надоесть 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: По четыре золота у нас и у Китая, но у нас меньше сумма баллов за оба тура.
Объявление после тура во время показа результатов: "У вас есть бесконечное количество токенов. Используйте их с умом".