Здравствуйте, Andir, Вы писали:

A>Здравствуйте, _DAle_, Вы писали:

_DA>>Извиняюсь за некий сумбур. Если кому будет интересно, как мы участвовали, расскажу.

A>Конечно интересно! На чём писали? Работу параллелили?

A>С Уважением, Andir!

Попробую немножко рассказать.

Итак, в прошлом году я и несколько моих знакомых участвовали в ICFP06 по одиночке. Очень понравилось, но решили, что без команды участвовать практические нереально — видна только верхушка айсберга. В этом году изначально собрались командой: crem, DAle, HeaDacHe, pinc (ники с topcoder.com). За неделю где-то завели svn у crem'a на компе, следили за блогом. Так как в блоге были картинки, решили написать примитивный binary -> greyscale picture просмотрщик, чем я и занялся после приезда в Минск с концерта Металлики К началу контеста просмотрщик был почти написан, но в будущем не пригодился. Общение было в основном в irc, иногда разговаривали по телефону.

Кратко об условии. Участникам предоставлялся ДНК код некой инопланетной зверушки, представляющей из себя строку из символов I C F P, длиной 7.5 мегабайт. Затем был приведен алгоритм, превращающий ДНК в РНК. РНК же из себя представлял набор команд для отрисовки картинки (довольно изощренными методами). Даны были две картинки: текущее состояние зверушки и желаемое. Сделать надо всего ничего: добавить к текущей ДНК префикс так, чтобы картинка в результате была как можно более похожа на желаемую (точное совпадение пикселов), ну и префикс для этого надо было использовать желательно как можно короче.

Дальше хронологически

20.07
13:30 Появилось условие. 22 страницы. Нас только трое.
13:30 crem разобрался с RNA->IMG частью, собирается писать на perl.
13:50 Решили послать префикс из условия. Увидели, что можно на сайте посмотреть, что это за картинка получается. Там был selfcheck.
14:00-15:00 Начали писать DNA->RNA. pinc на ruby, я на С++, независимо друг от друга.
16:00 crem вроде уже дописал свой конвертор, появился HeaDacHe.
19:00 HeaDacHe написал несколько алгоритмов поиска подстроки для моего DNA->RNA на с++. Версию на ruby решили не развивать из-за тормозов.
20:00 Я дописал DNA->RNA, правлю ошибки, в это время уже написаны какие-то скрипты для отрисовки.
.. 00:00 DNA->RNA все еще не заработал, вместе с HeaDacHe'ом ищем ошибки. crem и pinc за это время улучшили рисовалку, появилась возможность дампить картинки при отрисовке RNA с нужной частотой и еще куча полезных мелочей.

21.07
01:00 crem наваял компаратор картинок для сравнения наших результатов с target.png. Мы наконец-то завели DNA->RNA, выдает какой-то RNA, вроде что-то рисуется, но на selfcheck пока вылетает.
03:00 Наконец-то прошел selfcheck. Теперь у нас есть вроде правильно работающий DNA->RNA. Работает, правда, медленно. Иду спать.
...
11:00 Пока я спал, народ уже получил картинку с repair guide. На ней два префикса. Подставив второй префикс ("солнце") получили картинку, которая похожа на начальную, но с цветами, которые были в конечной. Послали. Оказалось, что эта картинка дала нам результат в 1.27%. Поднялись выше в табличке, место на 30. Картинка совпадает на 67% c конечной.
12:00 Прогнали профайлером DNA->RNA. string::operator+=, поиск, как оказалось, вызывается не так уж и часто, так что KMP-алгоритм был похоже лишним.
14:00 Храню теперь ДНК в статическом буфере, убрал почти все STL-приблуды, заменил на memcpy, убрал рекурсию из части функций. Заработало раз в 10 быстрее, но все равно слишком медленно. Явно видно, что тормозят копирования кусков ДНК. Префикс из условия c selfcheck'ом преобразовывался за несколько секунд, но с пустым префиксом преобразоавние длилось очень долго.
15:00 HeaDacHe'у удается соптимизировать еще раза в 2.
17:00 К этому времени получили картинки для первого префикса с полученной утром картинки. Это был repair guide navigation..
...00:00 Тут мы просто застряли. DNA->RNA дальше практически не оптимизируется в таком варианте. Я пробовал переписать часть кода, но наткнулся на ошибку в рассуждениях. Понятно было, что надо не копировать строки, а хранить что-то вроде пар (смещение, длина) и с ними оперировать, но виделось достаточно много проблем с таким подходом. С подстановкой же числа страницы было вообще глухо. Появилось бесчисленное количество идей, но ни одна из них не прошла, да еще и картинки из префиксов получались слишком долго...

to be continued