AlexErofeev's blog

By AlexErofeev, 7 years ago, translation, In English,

Meanwhile, David Eppstein has published his own chart of top algo results of 2011
In russian version I've tried to review some of them, but if you know english better, you should follow original post.
I found it very interesting that there are some red topcoders among authors :)

Read more »

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

By AlexErofeev, 8 years ago, In Russian,
Только что закончился этап Открытого Кубка.
Предлагаю здесь обсудить задачи.


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

Read more »

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

By AlexErofeev, 8 years ago, translation, In English,
Today at uva.onlinejudge.org there's going to be held A Contest dedicated to Renat Mullakhanov (rem)
Start at 13:00 MSK.

Read more »

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

By AlexErofeev, 9 years ago, In Russian,
Полагаю, все команды уже вернулись с южного четвертьфинала 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) и мы впервые, с третьей попытки, прошли в полуфинал.

Read more »

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

By AlexErofeev, 9 years ago, translation, In English,
Already first semifinal of TopCoder Open 2010 finished.
Round was won by bmerry, who was leading through all the round, also Louty (this guy became red just after TCO2010 Online Round5!) and Klinck passed to the Finals.
sys96, Vasyl[alphacom], dzhulgakov and grotomol got it to the wildcard round.
Unfortunately, Petr finished this year's TCO participation after spending too much time on 250.

About tasks:
250: Given a field 2^10+2 by 2^10+2. Squares are filled this style: first they fill (1,1), then leftmost lwermost point of those, which minimal distance to already filled are maximal. Problem is to find kth filled square.
500: Given an infinite field with Alice and 10 rabbits. Rabbits run across the field in given directions. You are to find minimal time for Alice to step into the square, which already contains rabbit, for each rabbit.
950: Given 25 participants of CodeTopper Open 2010. Everyone can get an integer point between worst[i] and best[i] with equal probability. Topmost k pass to the Finals. You are to find probability of each participant to pass into Finals.


How to solve:
250:quoting misof: "make 5 iterations by hand, then make 4 more by hand"
500: more or less standard dp: d[bitmask of catched rabbits][rabbit, that was catched last] = spent time.
1000: even bmerry had about an hour to solve it, but it could not help, so I can't tell you anything now.

Read more »

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

By AlexErofeev, 9 years ago, In Russian,
Странно, что никто еще не написал

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

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

Read more »

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