Только что закончился этап Открытого Кубка.
Предлагаю здесь обсудить задачи.


В частности, интересуют задачи A и B.

Сегодня на uva.onlinejudge.org состоится A Contest dedicated to Renat Mullakhanov (rem)
Начало в 13:00 MSK.

Полагаю, все команды уже вернулись с южного четвертьфинала NEERC, который в этом году проходил 20-23 октября. Вот как он прошел для нас.
Приехали мы в Саратов 20 октября утром - в день пробного тура. На открытии объявили, что писать мы будем в библиотеке СГУ. Крайне интересно, как производилось распределение - в одну из аудиторий 12 корпуса посадили практически все топовые и приближенные к таковым команды. В библиотеку же отправили множество не самых сильных участников. Стало как-то даже грустно что ли. Как оказалось, библиотека была очень хорошим и удобным местом для проведения соревнования. В отличии от той большой аудитории в 12 корпусе,  где мы писали контест в прошлом году и было очень тесно (проблему вызывало даже отодвинуть стул назад, чтобы пересесть - там сидели другие участники, не говоря уже о том, чтобы пройти по проходу), хоть в библиотеке и сидело очень много команд (чуть меньше половины от всех участников), там было очень удобно и комфортно.
На пробном туре были незначительные проблемы с рабочим местом, но они быстро и успешно разрешились и, несмотря на все опасения, повторно не возникли.
На Code Game Challenge написали достаточно простой алгоритм управления hovercraftом. Сильного желания придумывать изощренную качественную эвристику не было, ибо главной целью был все таки предстоявший контест, да и пришли мы на тур Code Game Challenge слегка не рассчитав время, опоздав примерно на 10 мнут к началу и основательно промокнув. (Неплохо черпанули воды в ботинки по дороге под сильным дождем. В итоге писали полностью босиком =) Сидели около окна и холодной батареи. Обернулись - сзади у батареи уже стояли чьи-то кроссовки =) Видимо, команды Samara SAU #1 =) ). По ходу тура выяснилось, что зачастую бот падает (появлятся решетка возле его имени и больше  бот не двигается), причем непонятно почему. Мы довольно долго усиленно сканировали глазами наш код, пытаясь найти место, где мог возникнуть runtime error. Однако потом неизвестным образом смогли также "уронить" бота и играя как "Gamer", т.е. при ручном режиме управления с клавы. Такое случалось примерно в 20-25% случаях и причину выяснить мы не смогли. После этого проще всего было списать падения бота на это же. Впрочем, на Code Game Challenge Show, как нам сказали, наш бот не падал ни разу, так что, возможно, имел место какой-нибудь локальный глюк.
На следующий день был основной тур.
После начала я сел читать задачи с конца, Артем - с начала. Он довольно быстро наткнулся на задачу B(3D City Model) и отдал мне ее писать. Я отадал ему додумывать задачу J(Buoys). Шаблон был готов и довольно скоро пришел первый Accepted. Вместе с B много кто сдавал задачу F(Elevator). Я прочитал и хлопнул себя по лбу: "Чуть ли не халявнее, чем B!". В общем, скоро нам зачли и вторую задачу.
Насчет третьей приведу рассказ Артема и Вовы:
-Ну, в C(Explode 'Em All) Артем сразу вцепился.
-Я увидел. что ограничение 25 и сразу решил, что это перебор. Только получалось 25*2^25 - много. Смотри, что делаем: разделяем все строки на 2 части и считаем для каждой маску столбцов, а затем делаем побитовый OR для всех пар.
Идея несложная, какое-то время ушло чтобы написать, потестить, вместе с Артемом нашли пару багов и получили третий Accepted.
После этого мне рассказали, что писать по задаче E(Kidnapping). На нее ушло еще около 10 минут.
К этому времени довольно много команд сдали J. Во время контеста мы не придумали доказательства корректности нашей идеи с тернарным поиском и я начал ее писать просто потому, что по другим задачам идей толком еще не было и казалось, что раз так много народу ее уже сдали, то наша идея скорее всего верна, ибо на поверхности и не так сложна (особенно для топ-10-15 региона, которые уж наверняка знают, что такое тернарный поиск). Написал, запустили, ответ не как в семпле. Проверили вручную - оказалось, что тоже корректный ответ. Отправили. Accepted.
Следующей по сложности задачей была D(Fire in the Country). К этому моменту (примерно через два часа после начала) у меня дала о себе знать некоторая усталость, в идее построения выигрышных/проигрышных позиций не хватало одного отсечения, в результате чего сложность вырастала до кубической и мы получили TLE40. Затем добавили отсечение, немного поковыряли мой код нахождения времени, за какое огонь доберется до каждой из вершин, получили WA6, немного поругали меня за то, что не начал сразу писать bfs, я написал bfs и получили шестой Accepted.
Осталось два часа и варианты - решать G(Revolutionary Roads) или H("North-East"). По поводу других задач зачтенных попыток не было даже у звездных составов NNSU и Saratov SU#2, так что для нас другие задачи, очевидно, не представляли особого интереса.
Примерно полчаса мы пытались разобрать G на составные части, я попутно написал выделение сильно связанных компонент (полагали, что это потребуется). Потом у меня возникло озарение, как правильно использовать дерево отрезков в H и я бросился писать, а Артем следить. До конца контеста остался примерно час, на замороженном мониторе мы были на 8 месте, у нас было решение почти такое же, как и рассказанное на разборе М. Мирзаяновым, однако не настолько четко сформулированное и, в результате код иногда приходилось додумывать на лету, из-за чего были баги, на отладку которых и ушел остаток часа. В процессе отладки пару-тройку раз из-за Stack Overflow Exceptionов зависал на пару минут Eclipse, что меня невероятно выводило из себя (за десять-то минут до конца контеста!). Eclipse перезапустили, это не помогло, в итоге что-то отладили, заставили работать на первом семпле, отправили, естественно получили WA#2, дальше еще несколько исправлений, неправильные ответы на семплах, еще исправления, вчитывание (все это за 5 минут до конца). В итоге в финальном ранклисте у нас так же 6 задач.
По дороге с контеста в гостинку рассуждали, что обычно под фризом сдают не так и много, делали ставки на то, выбьют ли нас из десятки итд. Но этого не случилось, никто снизу нас не обогнал (впрочем, более или менее реальные шансы на это имели лишь Samara SAU #2 и Saratov SU #6) и мы впервые, с третьей попытки, прошли в полуфинал.

Только что закончился первый полуфинал TopCoder Open 2010.
В финал прошли лидировавший практически "от старта до финиша" bmerry, Louty (этот парень впервые стал красным во время TCO2010 Online Round5!) и Klinck.
В wildcard round прошли sys96, Vasyl[alphacom], dzhulgakov и grotomol.
К сожалению, Petr закончил свое выступление на TCO2010 после того, как потратил чуть меньше часа на решение 250.

По задачам:
250: Дано поле 2^10+2 на 2^10+2. Клетки в нем заполняются следующим образом: сначала заполняется (1,1), затем самая нижняя левая из тех, минимальное расстояние от которых до уже закрашенных максимально. Найти клетку которая закрасится k-й.
500: Дано бесконечное поле с Алисой и 10 кроликами. Кролики бегают по полю согласно заданным маршрутам. Определить за какое минимальное время Алиса сможет побывать на той же клетке, что и каждый из кроликов.
950: Даны 25 участников CodeTopper Open 2010. Каждый из них может набрать любое целочисленное количество очков между worst[i] и best[i] равновероятно. В финал проходят верхние k. Требуется вывести для каждого из участников вероятность его попадания в следующий раунд.


Как надо было решать:
250: как сказал misof: "сделать 5 итераций вручную, потом сделать 4 итерации вручную"
500: более или менее стандартная динамика: d[маска пойманный кроликов][кролик,пойманный последним] = затраченное время.
1000: на нее у bmerry было чуть меньше часа, но даже он не справился.

Странно, что никто еще не написал

Результаты
Задачи

Победители:
1 место - Moscow SU Unpredictable: Kornakov, Kumok, Astakhov
2 место - Moscow SU ST: Rogulenko, Kaluzhin, Fedorov
3 место - SPbSU ITMO 1: Isenbaev, Kapun, Melnikov