Due to the installation of a new fire alarm in ITMO server room, the system may be occasionally unavailable on the 27-th of May between 06:00 and 15:00 (UTC). ×

KOTEHOK's blog

By KOTEHOK, 6 years ago, In Russian,

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

Вот и заканчивается 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 разделил третье место в абсолютном зачёте.

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

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +106
  • Vote: I do not like it  

By KOTEHOK, 6 years ago, translation, In English,

There were a lot of requests like "Russian team ioi-2013 blog". I'll try to write something. This year I am a guest on IOI, so I have a schedule that differs from the contestants' one. For example, when the contestants had the Practice Session, where, as rumoured, there were something bad with printers (but do you remember at least one place where printers worked good from the beginning? ;), I had an excursion to Lone Pine Koala Sanctuary, where are some beautiful Australian (but not only) animals, for example the following ones:

Read more »

 
 
 
 
  • Vote: I like it  
  • +102
  • Vote: I do not like it  

By KOTEHOK, 8 years ago, In Russian,
Лог второго тура:

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. И остаётся только молиться, чтобы среди них были Паша и Гена.

Read more »

 
 
 
 
  • Vote: I like it  
  • +27
  • Vote: I do not like it  

By KOTEHOK, 8 years ago, In Russian,
Лог первого тура:

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +51
  • Vote: I do not like it