Блог пользователя KOTEHOK

Автор KOTEHOK, 11 лет назад, По-русски

Ссылка на первую часть

Вот и заканчивается IOI 2013. Расскажу кратко о том, что произошло с момента предыдущего поста (начала открытия). Открытие оказалось достаточно коротким, что всегда радует участников олимпиады. После открытия лидеров повезли на очередное собрание GA (General Assembly — собрание лидеров команд), посвященное разбору проблем пробного тура, а затем дали возможность ещё раз встретиться с участниками и обсудить услышанное на собрании, и дать последние наставления своей сборной (как правило, самое главное наставление в таких случаях — будьте готовы к любым проблемам, и используйте своё самое мощное оружие — мозг). После того, как участников увели в карантин (изолировали от любых коммуникаций с внешним миром), началась самая тяжёлая часть для лидеров команд и тех, кто изъявил желание помогать им в переводе задач на национальные языки.

В этот раз от России приехали трое тренеров, что позволяет перевести все три задачи на русский язык уже в процессе, когда задачи предлагаются для ознакомления членам GA, чтобы те могли высказать свои замечания. С самим переводом особых проблем не возникло, однако к сожалению, после этого нужно ещё и залить сделанные переводы в wiki, которая с прошлого года используется для этих целей. Вот тут-то и поджидали нас проблемы, потому что, как выяснилось, часть фраз (поначалу — целые разделы) в принципе невозможно было залить в эту систему (они в итоге оказывались по-английски). По мере сообщения о наличии таких фраз организаторы пытались исправлять эти проблемы, однако даже в финальном варианте условий осталась пара непереводимых заголовков таблиц. Кроме того, ближе к концу перевода в системе перестала также работать генерация pdf-условий (генерировались странные ошибки или просто устаревшие версии условий), поэтому pdf пришлось генерировать вручную. Когда в два часа ночи (через 7 часов после того, как задачи были выданы) мы наконец закончили перевод, мы ушли с надеждами, что хотя бы у участников завтра проблем не будет. К сожалению, эти надежды были ложными.

Первый тур начался с задержки на час, в то время, как гостей привезли в 9 утра на экскурсию к музею, который открывается в 10 (поразительное сходство). Поначалу таблица результатов не работала, впрочем, мы не сильно переживали по этому поводу — такое уже бывало ранее. Однако заработав через полтора часа на несколько минут, таблица результатов обновляться перестала, и стали распространяться печальные слухи, что участники тоже испытывают проблемы. К сожалению, это оказалось правдой — тестирование во время большей части тура работало очень медленно, с задержками на час и более. По завершению тура участники были очень злые, а гостей для создания аналогичного настроения привезли последним пунктом экскурсии в планетарий, котороый как раз ровно в этот день оказался выходной. Дальше я ничего не помню — пошёл спать :)

В день между турами всех повезли на пляж, на котором даже можно было купаться в океане, несмотря на то, что в Австралии сейчас зима. Там было хорошо, единственный недостаток, что ланч представлял собой два твёрдых куска льда — один из которых являлся сэндвичем, а второй — соком. Впрочем, с едой тут почти всегда какие-то проблемы :(

Правда, время возвращения с пляжа было рассчитано плохо. По расписанию, лидеры и им сочувствующие должны были приехать в университет в 16.00 при отъезде с пляжа в 15.00, однако в реальности ехать пришлось два часа. И опять состоялось уже второе собрание по задачам, однако в этот раз всё прошло не так гладко. По третьей задаче (game) поступило некоторое количество жалоб на то, что она слишком стандартная, а также при выданных ограничениях в ней проходит решение "в лоб". В результате научный комитет предоставил в качестве опции запасную задачу на замену, но она оказалась хорошо использованным баяном, по крайней мере, она встречалась на национальных сборах как минимум пяти стран, в том числе российских. Поэтому, решено было менять ограничения и переделывать тесты к задаче game. Уж не знаю, как это связано, но в результате до полуночи нельзя было вводить в систему фразы перевода этой задачи, а желающим ввести в своё условие на национальном языке финальные ограничения вообще было предложено либо ждать 7 утра, либо идти спать, добавив фразу "см. английское условие для того, как устроено разбиение на подзадачи". Впрочем, даже выбрав "идти спать", мы всё равно пошли спать в 4 часа ночи, как это ни печально. В итоге, проснувшись на следующее утро в 8 и увидев проливной дождь и небо без единого просвета, я решил не ехать на второй пляж, экскурсия на который была организована для гостей, и проспал почти весь день.

Окончательный наш результат — три золотых медали (KAN zemen malcolm) и одна из первых серебрянных (tunyash), второе командное место (после Китая). При этом KAN разделил третье место в абсолютном зачёте.

Очень высокий результат, хочется пожелать ребятам, и тем, кто с ними работал, родителям, педагогам, дальнейших успехов! Для нас сейчас очень важно сохранить высокий уровень подготовки и высокие результаты, для которых, на мой взгляд, очень важно наличие трёх следующих глобальных начинаний:

  • Летняя компьютерная школа (ЛКШ), которая хоть и не ставит своей целью подготовку к олимпиадам, тем не менее, играет большую роль в обучении школьников алгоритмам и популяризации информатики. А также просто настраивает людей на хорошее :)

  • Интернет-олимпиады (и другие командные олимпиады) школьников по информатике, которые стали достаточно массовыми и проникают в самые отдалённые уголки нашей страны.

  • И конечно, самое важное — это команда тренеров, которые на самом высоком уровне занимаются непосредственно подготовкой всероссийских сборов школьников по информатике!

Очень надеюсь, что мы сможем и дальше двигаться вперёд и покорять всё новые и новые вершины. Не хотелось бы, чтобы нас постигла печальная участь Польши, которой в итоге не досталось ни одного золота. Ещё раз подчеркну, для всех, кто участвует так или иначе в процессе подготовки школьников, студентов, в своей школе, регионе, вузе или на всероссийском уровне: всё, что вы делаете — важно. Помните, что вы работаете для конкретных людей, которые через много лет обязательно скажут вам спасибо! А пока, зная, как редко благодарят педагогов собственные ученики непосредственно в процессе обучения, говорю огромное спасибо вам всем от себя лично :) Мы с вами победим!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +106
  • Проголосовать: не нравится

Автор KOTEHOK, 11 лет назад, По-русски

Часть 2

По многочисленным заявкам на тему "блог сборной России на ioi-2013" попробую написать хоть что-нибудь. В этом году я приехал как гость, поэтому в основных моментах моя программа отличается от программы участников. Например, в то время, как у участников был пробный тур, на котором, по слухам, плохо работали принтеры (впрочем, вы помните хотя бы одно место, где они хорошо работали с первого раза? ;), я ездил на экскурсию в Lone Pine Koala Sanctuary, в котором представлены некоторые виды австралийских (и не только), животных, например следующие:

Полный текст и комментарии »

  • Проголосовать: нравится
  • +102
  • Проголосовать: не нравится

Автор KOTEHOK, 13 лет назад, По-русски
Лог второго тура:

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. Россия пока без изменений :(

10:12 - У Паши стало 126. Неужели он всё ещё сидит в слонах? Не пора ли заняться попугаями и сдать их на сотню?

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:38 - У одного из участников из Китая уже 237 баллов. У Егора тем временем 198 (98 по попугаям). Да, наверно, будет обидно из-за двух баллов писать совсем другое решение... 

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://acm.math.spbu.ru/ioi-2011-day2/
Текущие результаты: http://www.ioi2011.or.th/results
Результаты в приличном виде (спасибо Снарку :): http://sc2.ioi2011.net:8070/contest/
Результаты от Снарка: 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. И остаётся только молиться, чтобы среди них были Паша и Гена.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

Автор KOTEHOK, 13 лет назад, По-русски
Лог первого тура:

Окончательная информация: у сборной России 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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +51
  • Проголосовать: не нравится