Блог Ивана Комарова - ICFPC-2007

02:01 - ICFPC-2007

Ну вот, наконец-то у меня дошли руки написать про то, как мы сыграли сабж. Забегая вперёд и раскрывая все козыри, скажу:

1. Оооочень понравилось! Обязательно буду участвовать в следующем году.


2. Получилось так, что фактически на контесте зажигали xoposhiy и timustc, а я так, был на подхвате и играл роль идейного вдохновителя. :)


3. В конце мы упёрлись рогом в железобетонную стену и результатов не добились. :( Хотя возможность войти в топ-15 была…

Вводная

Осилившие 20-страничное задание могут этот пункт пропускать.

Итак, на Земле потерпел крушение пришелец по имени Endo. Поскольку в своём текущем виде долго прожить в наших условиях он не сможет, нужно срочно модифицировать его ДНК так, чтобы в результате получилось другое существо, более приспособленное к особенностям земного климата.

Если отбросить лирику, есть три ключевых понятия:
1. ДНК — текстовый файл, в котором могут встречаться всего четыре символа: I, C, F и P — типа, такие кислоты. Преобразуется специальным конвертером в РНК.
2. РНК — последовательность семикислотных команд, отдалённо напоминающая инструкции черепашьей графики в каком-нибудь Logo.
3. Конечный результат (живое существо) — картинка 600×600. Рисуется специальным преобразователем из РНК.

Если изображение рисуется более или менее в лоб, то с ДНК всё не так просто — по ходу исполнения ДНК может (и должна) модифицировать саму себя и «окружающую среду». В подробности я, наверное, вдаваться не буду, кому интересно — посмотрит псевдокод в условии. ;) Цель участников — приписать к существующей ДНК (из которой получается source-картинка) префикс (желательно наименьшей длины), который сделает результат наиболее похожим на target-картинку.

Предусловия

Тройка (dfyz (ВПС), xoposhiy (далее местами Паша), timustc (далее местами Слава)). C#, Subversion, Visual Studio + R# 3.0. Хорошее настроение, еда, напитки, свободные выходные. Hop, step and ICFPC!

Пятница, 17:00—21:00

Стартовав на час позже, распечатываем условия (пока ещё без timustc), немного удивляемся многабуквенности аффтаров и на некоторое время замираем — идёт процесс вкуривания. Почти сразу разделяемся: я берусь за часть DNA2RNA, xoposhiy — за RNA2Image. Обсудив тонкие места, обговариваем процесс кодирования: Паша начнёт работать прямо сейчас в «Контуре», я — дома и после прогулки на DDR. Параллельно вызваниваем timustc, понимаем, что он будет играть из Новоуральска, вздыхаем.

Пятница, 21:00 — суббота, 02:00

Итак, Паша уже закоммитил первую работающую версию рисовалки и ушёл домой — думать и спать, а я упрыгался в хлам и только-только приступил к написанию своей части. В скайпе появляется Слава, с которым можно славно общаться по ходу дела, на улице дождик, в голове ясность — идеальные условия для раздумий и вбивания кода.

По большому счёту, сам преобразователь оказался не такой уж сложной штукой, но есть несколько тонких мест:
• числа для функций nat() и asnat() могут быть произвольной длины. Пользуясь тем, что они закодированы в бинарном виде, быстренько клепаю класс LongNumber с булевским массивом в сердце и парой несложных операций.
• в процессе поиска совпадений (pattern matching) хорошо бы вхождения подстроки в строку искать за линейное время. Чуть поколебавшись между Бойером-Муром и КМП, останавливаюсь на последнем.
• в функции protect() protection level теоретически может быть очень большим. Слава подсказывает алгоритм на основе быстрого возведения в степень, который я благополучно и копирую в код.
• appending unquoted references should perform better than in linear time. В переводе на человеческий это означает следующее: нужно уметь быстро выполнять операцию «взять произвольную подстроку ДНК и прилепить её в начало». Вот тут у меня ничего не придумалось — я тупо делал это за O(N). :( Как оказалось, очень и очень зря.

Понадеявшись на то, что линейность в алгоритме не приведёт к фатальным последствиям (наивный), я проверяю, что всё работает, коммичусь и иду спать. А Слава тем временем находит в ДНК картинку, которая просто тупо рисуется на экран. В ней два префикса — один выводит на экран каталог по восстановлению Fuun'ов (это как раз тот инопланетный вид, к которому принадлежит Endo), а другой — включает солнце. К каталогу мы ещё вернёмся, а вот префикс для солнца timustc без промедления сабмитит как решение, и мы попадаем в top-20. Hurray!

Суббота, 11:00—16:00

Здесь я подло отключился от хода контеста. Но у меня была уважительная причина — из Америки после N-месячного отсутствия вернулся torrio и изволил меня видеть. Как-то так вышло, что мы посидели немножко, а потом ещё немножко, а потом от времени почти совсем ничего не осталось. :( А без меня тем временем Слава с Пашей отладили мой DnaExecutor и написали GUI, который отрисовывал картинку на экран по мере поступления новых блоков РНК. В этот момент я закончил бурное веселье встречу дорогого гостя и вновь приник к экрану монитора.

Суббота, 16:00—20:00

И вот тут-то стало понятно, что мы попали с позорным O(N). Префикс, который был дан в условии («if you use it, something interesting will probably happen») вырисовывал на экране self-check — проверку на то, что все компоненты нашей адской ДНК-машины работают правильно. Его-то, в принципе, можно было дождаться, а вот каталог (уже стало ясно, что всё самое интересное лежит там) отрисовываааался нууу оччеень по-эстооонски. Весь вечер мы профайлили, матерились, придумывали частные оптимизации, но в конце концов стало понятно, что с текущим подходом мы можем ждать хоть до второго пришествия и нам нужно придумать какую-то мегаструктуру данных. Отчаявшиеся и унылые, мы с xoposhiy пошли по домам. Перед самым уходом timustc написал, что он закоммитил ДекартовуСтроку — что-то хитрое на основе декартового дерева, вроде как способное решить все наши проблемы. Я рассказал Паше, что вообще такое есть декартово дерево и мы ушли окончательно.

Суббота, 22:00 — воскресенье, 01:30

Чтобы чуть прочистить мозги, я решил сыграть SRM на топкодере. Если бы я знал, ЧТО произойдёт через пять минут после начала, я бы хорошенько подумал, прежде чем открывать арену. :)

---

Слава Исенбаев (22:04:37 21/07/2007)
ААААААААААААААААААААААААААААА!!!!!!!!!!!!!!!!!!!!!
оно работает!!!!!!!!!

  dfyz (22:04:57 21/07/2007)
:'( Я играю СРМ :((((

  dfyz (22:05:09 21/07/2007)
через 75 минут поговорим

---

Естественно, после такой разорвавшейся бомбы я уже не смог сосредоточиться на задачках. :) В итоге 500 — глупая геометрия — у меня упала, и я даже до сих пор не разобрался почему — не до того было.

С использование ДекартовойСтроки DNA2RNA заработал мгновенно, но стал тормозить GUI. Я позвонил Паше (судя по его голосу, новость о прорыве произвела нехилое впечатление), выяснил, где есть тонкие места и собрался оптимизировать, но:

---

Слава Исенбаев (23:55:14 21/07/2007)
я нашел место, из-за которого вссе тормозит

dfyz (23:55:47 21/07/2007)
?

Слава Исенбаев (23:56:34 21/07/2007)
функция CurrentPixel

dfyz (23:57:47 21/07/2007)
почему там?

Слава Исенбаев (23:58:31 21/07/2007)
она за O(count) работает, а вызывается почти всегда

---

После чего мне осталось только сдаться и пойти спать.

Воскресенье, 12:00 и до упора

Когда я пришёл в «Контур», Паша уже вовсю шастал по каталогу, распечатывая страницы. Количество новой информации, обрушившейся на нас, просто поражало. За день мы:

• поняли внутреннее устройство ДНК и активацию генов
• узнали некоторые сведения про кодирование строк и чисел в ДНК
• расшифровали сведения по тому, как зашифрованы некоторые страницы каталога (правда, расшифровывать сами страницы мы не стали — это было слишком сложно, да и времени не хватало)
• нашли таблицу со списком генов (только первую страницу)
• написали активатор генов и успешно активировали ген M-class-planet, который вставлял изображение Земли перед source-картинкой
• нашли несколько скрытых страниц в каталоге
• увидели скрытую стеганографией картинку в ничем не примечательном изображении

… и после всех этих успехов было НЕВЕРОЯТНО обидно сознавать, что буквально ни бита этой информации мы не смогли использовать! Теоретически, совершенно ясно и понятно было что делать дальше — выводить все страницы таблицы со списком генов и составлять префиксы, которые по очереди активируют различные гены, получают классную картинку на выходе и гарантируют нам место в top-15.

Я на 100 % уверен, что это была самая интересная и захватывающая часть соревнования. И не смогли мы до неё добраться всего лишь потому, что не научились сменять страницы в таблице генов, а на первой не было ничего интересного. И ведь нам казалось, что это так просто: самым первым геном шёл AAA_geneTablePageNr, который мы безуспешно дёргали в самых различных позах весь вечер воскресенья. То, как передавать гену аргументы и забирать возвращаемое значение, было чётко описано в одной из страниц каталога, но у нас этот способ банально и тупо НЕ РАБОТАЛ. Все мыслимые и немыслимые комбинации, ухищрения и попросту извращения приводили к одному из трёх результатов:
а. выводилась обычная картинка
б. выводилась первая страница таблицы
в. всё падало

На этой мажорной ноте ICFPC для нас закончился, потому что мы сдались. :( Ничего больше не придумывалось и Dfyz's team не сдала ничего, кроме тупого префикса, включающего солнце. Эх.

Впрочем, вру. Утром понедельника Паша смог ужать этот «стандартный» префикс, который посабмитила куча команд, до 27 символов вместо 28. Но на самом деле до этого догадались практически все, так что положения это не улучшило.

Bottomline

Очень бы хотелось услышать в комментариях _adept_ и netp_npokon, которые, я подозреваю, продвинулись намного дальше нас. Расскажите, как передавать гену параметры? :)

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