Лог второго тура:

12:46 - Всё, пойду встречать ребят. Так ничего и не изменилось для команды России, похоже, так и останется два золота и два серебра. В целом >= 200 баллов уже у 86 участников, и, конечно, за оставшиеся 15 минут станет ещё больше.

12:24 - По задаче про попугаев стали появляться 99 баллов. Да, люди сильно продвинулись в изучении неточных решений. При этом сотен по этой задаче всего шесть. Также смотрю за Димой и Егором. У Димы много сабмитов по 26 баллов - похоже, он не придумал решения в слонах. А вот сабмит от Егора на 10 баллов, сделанный 15 минут, вселяет некоторую надежду, что у него просто какие-то баги в дереве.

12:11 - У Саши 100 за слонов! Надеюсь, два золота у нас уже железно. Догадается ли Саша сделать ход назад? И что же случилось у Димы и Егора?

12:00 - У Саши 295, 97 за слонов! К сожалению, Дима и Егор так и не вылезли пока из глубокого серебра, а Паша не заменил свои 98 на 100. При этом уже 65 участников набрали >= 200 баллов.

11:16 - Кстати, Дима дописал кучу в Дейкстре и у него стало 226. Все российские участники не ниже 9 места (хоть и 9 разделено с местами до 13). Эх, до конца бы так и оставить ;) Кстати, самое обидное, что если бы сейчас давали бы медали, то было бы всё равно два золота и два серебра. Это из-за первого тура так, получается то, о чём я писал ниже - выйти вперёд на этих задачах сложнее, а вот слететь...

11:15 - У Паши 98 по попугаям. Видимо, теперь надо сделать главный ход конём и догадаться до очень неожиданной идеи - в неточной задаче есть точное решение! На самом деле, это реально сложно, это как в шахматах взять предыдущий ход назад.

11:06 - У Паши 90 в попугаях. Всё-таки, он пошёл тем путём. Жаль... надеюсь, за два часа он сообразит про наличие абсолютно точного решения.

10:52 - У Димы сотня по попугаям! При этом уже 31 участник имеет >= 200 баллов, а 145 участников - >= 100 баллов. У наших у всех хотя бы 215 (Паша 281, Саша 248, Егор 224, Дима 215). Насколько этого достаточно, покажет время, но, думаю, будет ещё много подъёмов разных участников.

10:38 - У Паши уже 81 по попугаям. Видимо, это делается за 5 минут. Надеюсь, он не пойдёт дальше этим путём? Очень сбивает то, что эта задача с неточной оценкой, это психологически неожиданно и уводит от мысли искать простое точное решение :( Тем временем, Дима тоже получил 81 балл по этой задаче и имеет 196 баллов за этот тур. Надо бы ещё.

10:32 - У Паши 100 по слонам! Молодец! Не зря он в них сидел. Через минуту присоединился Гена и стал первым из абсолютных победителей. Паше остаются попугаи. Очень надеюсь, что он увидит в них сочетания с повторениями - на мой взгляд, это самый сложный момент в этой задаче. Иначе получается 98.

10:22 - У 17 участников >= 200, у 116 участников >= 100. Россия пока без изменений :(

09:58 - У Гены уже 297. Сейчас он чуть-чуть пооптимизирует слонов и станет одним из абсолютных победителей. Тем временем, у 11 участников >= 200 баллов, а у 100 участников >= 100 баллов.

09:54 - Тут же у Саши становится 98 баллов по попугаям (248 всего), и его обгоняет Гена с 250 баллами, у которого по попугаям одно из двух полных решений (другое глубоко внизу, что как бы намекает).

09:53 - Саша сдаёт попугаев на 93 балла и выходит на первое место по туру с 243 баллами. Но что же там за решения не на 100? И не придётся ли потом вместо них писать на сотню?

09:50 - У Егора 224, добавилось ещё 26 баллов по слонам. Что же он будет делать теперь, и что же за проблемы у остальных наших?

09:46 - Почему-то российские участники пока не двигаются (Егор - 198, Саша - 150, Дима - 115, Паша - 110). Очень волнуюсь, в чём же дело. Тем временем шестеро участников имеют >= 200 баллов, а 89 участников - >= 100 баллов.

09:32 - У Паши 10 баллов за слонов. Что бы это значило? Хотя бы 100 баллов уже имеют 68 участников.

09:26 - У Егора 81 по попугаям. Я вообще не понимаю, что там может быть за решение, кроме точного :( Неужели там есть жёсткий ложный след, как в задаче garden первого тура, где можно было вводить состояния не на вершинах, а на рёбрах, что до сотни не доделывается вообще никак?

09:15 - Странно, что сотня по задаче parrots только одна. Зато есть ещё два участника по 98 баллов. Неужели комбинаторика и построение объекта по номеру и номера по объекту - такая сложная вещь? Или не все знают про сочетания с повторенями? При этом хотя бы 100 баллов уже у 52 участников.

09:10 - у Димы 115, у Саши 150. Похоже, пошли в бой разные квадраты в слонах. Тем временем, у лидера из Вьетнама 207 (100 + 26 + 81), а >= 100 уже у 41 участника.

09:00 - у Гены 200. Мой прогноз при виде задач, что у Гены останется 4 часа на задачу elephants, оказался абсолютно точным.

08:49 - уже 28 участников с >= 100. У всех российских участников 100, кроме Димы, у которого 89 (без хипа?).

08:40 - уже 18 участников имеют >= 100. У российских участников 100 баллов у Паши, 89 баллов у Саши (сначала решил послать Дейкстру без хипа?)

08:35 - уже семеро участников имеют полный балл по одной из задач

08:20 - один из польских участников уже сдал задачу про крокодилов. Дейкстра с хипом, однако.

По информации от организаторов, контест начался в 08:00 и закончится в 13:00 (местное время - +3 часа от московского).

---

Результаты от Снарка: http://158.250.33.215/~ejudge/player_all.html

Решения всех задач второго тура.

Он мне показался даже проще чем первый. Сколь-нибудь ненулевое время я решал только elephants, остальные две задачи мне вообще показались упражнениями на базовые темы.

1) crocodile

Алгоритм Дейкстры, только нужно хранить в каждой вершине два текущих минимальных ребра, и ответ от вершины - второй из этих минимумов. Доказательство: пусть для каждой вершины посчитан ответ, тогда верно, что D[u] = {второму из чисел D[v] + w[u, v]}, где (u, v) - все рёбра, связанные с u. Теперь пусть, как в Дейкстре, для некоторых вершин уже посчитано D[v]. Тогда если взять вершину u такую, что min {второго из чисел D[v] + w[u, v]} минимально возможен, очевидно, он правильный (так как иначе была бы вершина с меньшим ответом). Включим u в множество уже посчитанных вершин и отрелаксируем. Странно, что за кучу в Дейкстре дают всего 11 баллов...

2) elephants

Самая сложная задача, примерно по сложности как race. Заметим, что в фиксированный момент времени задача решается жадно - возьмём самую левую точку и покроем, и т.д. Теперь, если мы посмотрим на то, какую точку после какой мы покрываем жадным алгоритмом, мы увидим дерево, глубина вершины в котором и является ответом, если решать суффикс нашей задачи, начиная с этой вершины. Если читать это дерево сверху вниз, а внутри уровня слева направо, то мы получим список слонов в порядке справа налево. Осталось научиться поддерживать это дерево и уметь быстро вычислять глубину самой левой вершины. Для этого нужно понять, какие операции делаются с этим деревом. Можно разбить перемещение слона на две операции: удаление и добавление. При удалении берётся поддерево удалённой вершины и подвешивается к соседней на том же уровне, а если на этом уровне вершин нет, то к крайней на более высоком. Если же мы добавляем вершину, она добавляется на некотором уровне, подвешивается к одной из вершин более высокого уровня и у соседа отрезается последовательная часть детей и подвешивается к ней. Структура данных, которая замечательно выполняет такие операции - это декартово дерево 

по неявному ключу, если дерево хранить в порядке обхода dfs'ом. Единственное, в нём тяжело искать соседа по уровню, а также искать место, где нужно разрезать последовательность вершин при добавлении. Для этого я предлагаю хранить ещё одно декартово дерево, в котором ключом является координата слона, а также хранится дополнительная информация - ссылка на узел в дереве по неявному ключу. Тогда мы умеем в нём и искать нужную позицию, и переходить к соседу, и вообще делать всё, что нужно.

3) parrots

Видно, что исходное сообщение представляет собой размещение с повторениями (то есть, просто число в некоторой системе счисления), а конечное - сочетание с повторениями (если мы отсортируем все полученные числа, так как информация о порядке всё равно потерялась), число которых, как известно, равно C из n + k - 1 по k. Самый эффективный с точки зрения отсутствия отсутствия потерь информации способ их закодировать - это перевести исходное размещение с повторениями в номер, а потом по номеру построить сочетание с повторениями. Раскодировать, соответственно, обратно. Несложно видеть, что все подзадачи решены (ещё бы они не были решены, если это нельзя сделать таким способом - нельзя сделать никаким другим), например, для подзадачи 5 получается всего на несколько порядков больше сочетаний с повторениями, чем размещений - ограничения подобраны довольно жёстко. Да, несложная длинная арифметика ещё нужна.

В общем, к сожалению, наши шутки на тему того, что второй тур может быть ещё проще, чем первый, оправдались :( И это очень грустно для нашей команды, потому что упасть на таких задачах можно запросто, а вот подняться - почти нереально. Нужно ставить на количество абсолютных. Я ставлю на 6. И остаётся только молиться, чтобы среди них были Паша и Гена.