Таблица результатовSPOILER ALERT: в комментариях и теле этого поста, скорее всего, будут обсуждаться задачи соревнования, поэтому если вы участвуете в каком-либо онлайн-зеркале, либо хотите порешать задачи самостоятельно, будьте к этому готовы.
Краткий обзор задачАвторы соревнования, кажется, решили сделать самый оригинальный проблемсет со времён IOI 2010, и предложили во втором туре две интерактивки и одну обычную задачи.
Prize. Это интерактивная задача. В ряд расположены n ≤ 200 000 неизвестных целых положительных чисел, причём единичка ровно одна, и если есть x чисел, равных t, то чисел, равных t + 1, хотя бы x2 + 1. Мы можем спрашивать про позицию ряда, в ответ нам возвращается количества чисел слева и справа, меньших стоящего на выбранной позиции. Требуется за определённое количество запросов найти позицию единички. В первой подзадаче (которая стоит 20 баллов) гарантируется, что все бывают только единички и двоечки, и надо написать обыкновенный бинпоиск. Далее сразу следует большой идейный скачок: оставшаяся подзадача на 70-80 баллов, в которой нет дополнительных ограничений, и оцнивается максимальное число запросов по всем тестам —- 0 баллов за >10000 запросов, 70 баллов за 10000 запросов, 80 баллов за >= 5000 запросов, и между ними число баллов зависит от числа запросов линейно.
Ключевая идея решения — так как количества чисел каждого вида очень быстро растут, легко проверить, что чисел от 1 до 4 не более, чем 470, а шестёрок вообще не бывает. Таким образом надо научиться пропускать большие отрезки из пятёрок каким-нибудь логарифмическим способом, и получить, в зависимости от скрытой коснтанты, между 90 и 100 баллами в сумме. Опять же, может быть велик соблазн начать долго бороться за осташиеся <10 баллов, надеюсь, все участники с ним справятся и будут набирать баллы по оставшимся задачам.
Simurgh. Это тоже интерактивная задача, очень интересная. Дан граф на не более, чем 500 вершинах. Также в нём загадано некоторое остовное дерево. В качестве запроса разрешается выбрать некоторое остовное дерево и узнать, сколько у него общих рёбер с загаданным. Нужно определить всё рёбра загаданного остова и уложиться, опять же, в некоторое число запросов. Подзадачи: 1) n <= 7, q = 30000; 2) n <= 50, q = 30000; 3) n <= 240, q = 30000; 4) граф полный, n <= 500, q = 12000; 5) n <= 500; q = 8000.
Первые три подзадачи можно довольно быстро придумать, развивая идею о том, чтобы выбрать какое-то остовное дерево, и меняя в нём одно ребро на какое-то внешнее ребро, следить за измнением функции общего числа рёбер, дальше пока не понятно. Цитата от rpeng: The less matroid theory you know, the easier this problem is for you.
Books. Наиболее классическая задача тура, при этом более решаемая, чем wiring или trains. Нам надо отсортировать предметы, лежащие на n столах в каком-то данном порядке на равном расстоянии. Мы начинаем возле некоторого стола s и можем ходить туда-сюда, перетаскивая не более одного предмета. Найти минимальное расстояние, которое надо пройти, чтобы отсортировать предметы. n ≤ 106.
Полностью разобранный случай s = 0 дает 50 баллов, причем этот случай довольно простой: требуется рассмотреть все нетривиальные циклы в перестановке, объединить те из них, которые пересекаются (поскольку между ними можно переключаться бесплатно), а потом прибавить к тривиальной нижней оценке 
отрезки между соседними "компонентами".
Если s ≠ 0, то все чуть-чуть сложнее, поскольку нам придется потратить еще сколько-то шагов на то, чтобы дойти от старта до первой интересной точки. Жюри предлагает делать это динамикой по подотрезкам, либо (в полном решении) аккуратно понять, какие вершины с обеих сторон нам интересны, и при этом не забыть разобрать никакой случай.
Совсем текущее состояние: У Саши 63 место, у Егора 38 место, у Денис 27 место и у Вовы 19 место. Итого, три серебра и одно золото, причём, у Дениса самое первое серебро, что, конечно, очень обидно, но всё равно очень классно. Есть куда расти в следующем году!
Текущее состояние на момент конца тура: Тур длился 5:30, последние 25 минут табличка не обновлялась. За это время Саша успела улучшить результат по последней задаче до 50, чем, скорее всего, гарантировала себе серебро! Основная интрига для нас заключается в том, много ли участников оказались выше Дениса в итоге, или нет: до падения таблицы результатов Денис был на 24 месте, а золотых медалей, если мы ничего не путаем, 26.
Сейчас будет показ результатов, на котором по идее должны рассказать о текущем состоянии. Впрочем, мы подозреваем, что полные результаты появятся не скоро.
05:21: Тур продлён на 30 минут (минимум). По неподтверждённой информации, у них возникли серьёзные проблемы с тестирующей системой. Таблица не обновляется.
05:05: Саша и Денис все ближе к границам, волнуемся. К тому же нет гарантии, что текущая таблица правильная.
05:02: Сообщают, что контест продлен, неизвестно, на сколько именно.
04:51: Саша успевает набрать 13 по simurgh и теперь более уверенно попадает в серебро.
04:49: В последние минут Егор пихает books, Денис что-то шлет по simurgh.
04:46: САША!!! Смогла 90 по prize! Граница серебра, но какой все же камбэк!
04:33: yutaka1999 300. voidmax добил books на 50, точно золото. Denisson опасно болтается на границе.
03:54: К нам вернулся интернет. voidmax тоже смог сдать simurgh на 51.
03:30: Тем временем, у xumingkuan 70 по simurgkh, это первый участник, кто справился с полным графом.
03:15: kiyotaka и Denisson продолжают слать books, demon1999 послала simurgh на 0.
03:10: наш прогноз на границы медалей: золото 350, серебро 250, бронза 170.
03:03: Denisson привез 50 по books! С хорошей вероятностью наше первое золото. kiyotaka преодолел ноль по этой же задаче.
02:52: voidmax все же смог набрать 12 по books.
02:49: kiyotaka пытается улучшить свои 51 по simurgh, voidmax пытается получить больше нуля по books (upd: kiyotaka тоже посылал books, и тоже на 0).
02:44: У arsijo теперь тоже 90+51+0 и пятое текущее место в общем зачете. С хорошей вероятностью это уже окончательное золото.
02:42: demon1999 за последний час несколько раз посылала prize, но все на 20. Переживаем.
02:37: То же самое сделал и kilt_01. Если все эти ребята соберут и очень популярные 50 по books, у всех с хорошей вероятностью уже будет не хуже серебра.
02:27: К клубу набравших 
присоединяется giraffeh и подбирается вплотную к границе золота.
02:21: То же самое делают и Arthur и Mediocrity.
02:19: kiyotaka тоже набирает 51 по simurgh. Пока участников с таким баллом меньше десяти, приятно, что двое из них из России. #interactivepride
02:14: Помимо трех русских участников в текущей зоне золота находится arsijo из Украины, благодаря отличному результату на первом туре. Довольно близки к границе MadNick из Казахстана, а также kefaa и gepardo из Беларуси.
02:03: Опасный Lukas Michel из Германии первым на этом туре решил две задачи (практически) полностью: books и prize.
01:57: demon1999 все-таки включилась в набирание баллов по prize, начала с простого бинпоиска за 20.
01:55: kiyotaka и voidmax перебрали все остовы и набрали 13 по simurgh.
01:42: У Denisson 51 по simurgh.
01:39: У американца, чудом приехавшего на IOI вместе с делегацией Китая, 90+, 51 и 50. Кажется, это ровно те баллы, для получения которых не надо придумать что-то нестандартное.
01:27: Участник из Германии получил первую сотню по books.
01:20: Chmel_Tolstiy замечает, что команда Таиланда занимает 91, 92, 94 и 95 места.
01:19: demon1999 решила набрать 12 баллов по books.
01:13: В топ-20 три участника из России, один из Украины и двое из Грузии.
01:03: А вот и voidmax ворвался с 97.42 по prize. Уже порядка двадцати участников имеют ≥ 90 баллов, скорей всего, эти баллы будут необходимым условием для серебряной медали.
00:57: kiyotaka тоже быстро справился набрать все необходимые баллы по prize. Володя и Саша пока с нулями, ждем от них сразу хороших баллов.
00:40: У Denisson 94.9 баллов по prize, это очень хороший старт. Кроме него 90+ по prize у какого-то участника из Таиланда.
00:27: Появились 50 баллов по books и 13 баллов по simurgh от sancho. Denisson также заработал свои 20 баллов по prize.
00:09: Таблица результатов обновилась и в ней стали появляться первые участники с 20 баллами по первой задаче.
00:00: Соревнование началось по расписанию.
Всем привет!
Через полчаса начнётся второй тур международной олимпиады школьников. Вчера ребята посетили шестую по высоте башню мира Milad Tower; фотки с экскурсии, как обычно, можно увидеть в нашем телеграм-канале.
Мы с Михаилом Endagorion, как и позавчера, будем делиться мыслями по поводу происходящего на туре. Напомним, что по итогам первого тура 21 место (в официальном зачёте) занимает Владимир voidmax Романов, 28 место принаждлежит Денису Denisson Шпаковскому, на 37 месте расположился Егор kiyotaka Лифарь, и, наконец, на 54 месте находится Александра demon1999 Дроздова. Также отметим выдающийся результат украинского школьника Антона arsijo Ципко, занимающего на текущий момент 7 место.
Пожелаем всем участникам удачи!
Полезные ссылки (список будет пополняться):
