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

Окончательная информация: у сборной России 300 баллов у Паши, 269 у Саши, и по 212 у Димы и Егора. Общее количество полных баллов - 17, участников с >=243 баллами - 35, >= 170 баллов имеют 99 участников. >= 138 баллов - 145 участников. Кстати, ребята говорят, что на туре было подозрительно много реджаджей. Также добавлены мелкие багфиксы к решениям по итогам общения с командой.

12:56 - За 15 минут до конца, есть 17 участников с полным баллом, 30 участников с баллом >= 243, 96 набрали >= 170 баллов, 141 участник - >= 138 баллов. У России пока без изменений :( Пойду встречать ребят, может, какие хорошие вести появятся.

12:41 - Полчаса до конца, 14 полных, 43 участника >= 200, 87 участников >= 170, 132 участника >= 138. Россия - 300 (Паша), 237 (Саша), 212 (Дима), 190 (Егор). Эх, ещё бы немножечко!

12:30 - Число полных баллов выросло до 13. Россия - 300, 237, 212, 190. Кстати, организаторы наконец поправили имена в табличке. И Гена, наконец, всё сдал.

12:23 - 11 полных, 39 участников >= 200, 88 участников >= 149, 156 участников >= 100. Ситуация стремительно развивается. Где же наши, почему у троих из них всего одна сотня? Ждём хотя бы вторую.

12:13 - SnarkNews попытался восстановить старую нумерацию участников: http://158.250.33.215/~ejudge/player_d1.html

12:10 - Странно, что нет ни одного участника из Беларуси с полным баллом. Может, со странами тоже что-то не так, или всё-таки нет?

12:06 - Уже 10 полных баллов! Россия - 300, 237, 192, 190.

12:00 - На настоящий момент 6 полных, 34 участника >= 200, 73 участника >= 149, 145 участников >= 100. У России, если верить информации о стране, 300, 237, 190, 170. Неплохо, но хочется лучше!

11:40 - Если верить странной табличке, то сейчас 26 участников имеют >= 200 баллов, 59 - >= 149 баллов, 132 - >= 100 баллов.

11:20 - хотелось бы верить, что хотя бы страны не перепутаны. Если так, то у сборной России было только что 666 баллов в сумме. Надеюсь, это не помешает нам всех порвать ;) Сейчас вроде уже стало чуть больше, минимальный балл, который пишется, 149. Хотя это маловато, примерно 50-е место. Количество полных баллов в таблице - уже 3. Организаторы явно не рассчитали сложность задач...

10:58 - теперь и во всплывающей таблице участники перемешались. Видимо, ей всё-таки верить нельзя. А жаль...

10:56 - с другой стороны, это касается текстовой таблица, а оригинальная таблица с "всплывающими участниками" показывает 300 баллов у Паши Кунявского и 269 баллов у Гены. Но всё-таки непонятно, как 180 превратилось в 269. Видимо, нужно ждать, пока таблицу толком исправят.

10:52 - таблица обновилась, и показывает странные вещи. Похоже, что всех участников кто-то аккуратно перемешал, например, написано, что у Димы Егорова 300 баллов, а у Гены Короткевича внезапно стало всего 70. Я подозреваю, что тот участник, у которого 300, это всё-таки Гена. Ему бы уже пора идти купаться в море ;)

10:44 - таблица чуть-чуть изменилась, в частности, у Паши Кунявского 169 баллов, если верить замечательной системе, этот сабмит сделан ровно полтора часа назад - в 09:14.

10:07 - таблица до сих пор не обновляется. Gassa заметил, что есть один участник из Тайваня, который сдал задачу race. Неужели она решается ещё проще?

В 09:55 таблица результатов начала чуть-чуть обновляться, но медленно. Мы не знаем, насколько это соответствует текущему моменту контеста, вряд ли за час количество участников с >=100 баллами увеличилось всего на 3 (с 30 до 33).

В 09:37 организаторы тоже заметили, что таблица не обновляется, чинят.

В 09:30 - мы предполагаем, что доступная таблица результатов перестала обновляться - маловероятно, что за последние 15 минут не произошло никаких изменений.

В 09:20 на втором месте участник из Таиланда под номером 4 (Sorawit Suriyakarn) со 169 баллами. Третье место уже имеет всего лишь 112 баллов.

В 09:15 у Гены до сих пор 180. Может быть, N * Q взятий по модулю-таки не проходят, и нужно делать, как описано ниже? Вообще сервера очень быстрые, на пробном Флойд на 1000 заходил за секунду.

В 09:05 по виду около 25 участников уже набрали 100 баллов, среди них один из России.

В 08:50 у Гены уже было 180 баллов. У российских участников - 100 у Паши Кунявского, 42 у Егора Суворова.

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

---

Условия задач первого тура: http://acm.math.spbu.ru/ioi-2011-day1/

Текущие результаты: http://www.ioi2011.or.th/results

Результаты в приличном виде (спасибо Снарку :): http://sc2.ioi2011.net:8070/contest/

Результаты от SnarkNews с правильной нумерацией: http://158.250.33.215/~ejudge/player_d1.html

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

Ниже приводятся результаты моих размышлений в течение 30 минут. На кодинг всего этого по моим оценкам должно уйти не больше 3-4 часов, так что ожидаются полные баллы.

1) garden

Решение за N * Q (5 секунд должно хватить).

Дополним каждую из N вершин дополнительным флагом: по самому красивому ребру мы в неё пришли или нет. Получится 2N состояний, для каждого из которых однозначно определено следующее. Таким образом, ходя по этим состояниям, мы рано или поздно упрёмся в цикл (получилось что-то типа ро-эвристики). Нас интересуют те циклы, на которых лежат состояния (P, 0) и (P, 1) - это либо один общий, либо два цикла, а также интересны те вершины, из которых эти циклы достижимы. Ясно, что один dfs с запоминанием за O(N) нам поможет для каждого состояния найти величину предпериода до попадания в какую-то из этих вершин, а также размер соответствующего цикла. После этого легко выполнить запрос: для состояния (i, 0) сравним число из запроса с величиной предпериода; и если число из запроса не меньше - то возьмём по модулю длины нужного цикла и сравним остаток (если цикл, содержащий (P, 0) и (P, 1) - общий, то два варианта остатка; иначе выбираем один соответствующий). Заметим, что результаты взятий предпериода по модулю длины цикла мы можем преподсчитать для каждой из вершин заранее, а для каждого запроса нам придётся брать число из него не более чем по двум модулям. Это так, чтобы не было слишком много взятий по модулю, скорее всего, N * Q взятий по модулю тоже пройдёт - но я бы не рисковал.

Upd: после общения с командой выяснилось, что здесь не разобран случай, когда (P, i) лежат на предпериоде - но можно предпериод считать, например, очень большим периодом, или как-нибудь по-другому его разобрать, в общем, это мелкая техническая проблема :)

2) race

Наверно, надо как-то использовать, что длины не больше миллиона, но предлагается забавное решение за N log N с хешами, которое это не использует. А именно, от каждой вершины наверх будем передавать список возможных длин циклов, уходящих от этой вершины вниз. Будем хранить его в хешсете, кроме этого для хешсета будет храниться константа C, которая добавляется к каждому из чисел в хешсете. Подвесим дерево и запустим по нему dfs. Тогда в каждой вершине происходит следующее: возьмём первого потомка, вычислим для него список, добавим к константе C длину соответствующего ребра, дальше возьмём второго потомка, тоже вычислим аналогичный список, а теперь (внимание! ключевой момент) смерджим меньший список с большим (именно в эту сторону!) двумя способами. Первый способ будет искать значения K-C1-C2-A2i в первом хеше, где Cj - константы для списков, таким образом, мы учитываем пути, идущие через текущую вершину от первого потомка ко второму. Второй способ просто добавит значения A2i+C2-C1 к первому списку, после этого он будет содержать пути, уходящие из нашей вершины к первому и второму потомку, и теперь можно аналогично добавить третьего потомка, etc. Да, конечно, с каждым числом мы храним соответствующий ему минимум длины пути, чтобы обновлять глобальный минимум при мердже первым способом. Когда обработаем всех потомков - передадим список наверх, etc. Почему NlogN? Да потому что каждая вершина дерева оказывается в меньшем списке не более logN раз. Да, текущую вершину тоже не стоит забывать добавлять, ведь путь может идти от неё. Это, видимо, делается добавлением самой последней операцией в каждой вершине списка из одного нуля. Кстати, теперь понятно, и как использовать ограничение длины 10^6 - можно вместо хеша всё засунуть просто в массив от -10^6 до 10^6, с дополнительной связью в виде списка, для того, чтобы быстро проходиться по меньшему списку.

Upd: С массивами, видимо, делать нельзя - так как нужно хранить по массиву на каждый уровень. Тем не менее, хешмэп с удвоением, а также декартово дерево (Nlog^2N) и даже map решают - решение проходит по времени.

3) ricehub

Ну тут, казалось бы, метод нескольких указателей. Очевидно, что максимальный ответ за минимальную цену достигается в каком-то из рисовых полей (иначе всегда можно сдвинуться в ту из сторон, где рисовых полей не меньше, чем в другой, и станет не хуже). Кроме того, это отрезок из подряд идущих рисовых полей (иначе передвинем самую внешнюю точку внутрь отрезка в том направлении, где дыра - опять же, станет не хуже). Теперь будем двигать слева направо тройку указателей - начало, конец и середину. Если конец сдвинулся так, что даже в середине бюджета не хватает - двигаем начало. Середина, конечно, посередине отрезка с точки зрения количества полей - но её тоже можно двигать, имхо так будет проще.

Upd: после общения с командой выяснилось, что самый левый указатель иногда приходится двигать налево, и непонятно, какая получается асимптотика, но, во-первых, это проходит, а во-вторых, двоичный поиск по количеству полей при фиксированном центре, с учётом того, что по разные стороны от центра лежит одинаковое количество рисовых полей, решает.

Если вы видите какие-то баги, или у вас есть другие идеи решений - welcome.