Кто-нибудь еще участвовал в прошедшем ICFPC?

Предлагаю здесь пообсуждать решения, впечатления и набранное количество очков.

Вкратце опишу наш подход.

Simple problems

Для задач без оператора fold мы придумали решение, которое работало лучше чем полный перебор:

1. Сначала делаем прекальк.
2. Выбираем случайным образом X — вектор длины 5-10 из случайных 64 битных чисел.
3. Динамикой вычисляем какие могут быть вектора значений функций сложности не больше N, на этом наборе X. Число N определялось таким образом, чтобы общее количество вариантов не превосходило 10^6.
4. Теперь делаем запрос eval на сервер c этим вектором X.
5. По полученному Y начинаем раскручивать динамику назад и восстанавливать какие функции могут принимать такие значения.
6. Каждую подходящую функцию пытаемся отправить на сервер в качестве ответа.
7. Если она не подходит, то сервер нам выдает (x, y) -- ограничение на функцию вида f(x) = y. Продолжаем раскручивать динамику, предварительно отфильтровывая функции не удовлетворяющие этому ограничению.

Наборов значений существенно меньше, чем всего функций, поэтому это работает лучше чем полный перебор.

Problems with fold

В задачках, содержащих fold уже надо было перебирать функции зависящие не только от переменной x, но и от переменных y, z. Поэтому этот же метод применить не удалось. Здесь мы использовали обычный итеративный brute force:

1. Аналогичным образом, генерим случайный вектор X и с сервера спрашиваем вектор Y значений искомой функции. Эта пара (X, Y) задает нам ограничение на искомую функцию.
2. Начинаем перебирать все функции по порядку от меньших сложностей к большим.
3. Если функция подходит под ограничение то либо она и есть искомая и мы решили задачу, либо наше ограничение (X, Y) увеличивается и мы продолжаем дальше наш перебор.

Большую часть контеста мы пытались придумать решение более умное чем полный перебор, но все нашли эксперименты не взлетали. Примерно за 16 часов до окончания соревнования мы поняли, что даже если и придумаем что-то круто, то не успеем это закодить/отладить и начали просто подряд решать все задачки описанными выше алгоритмами. Успели за 15 минут до конца контеста :) (правда для этого пришлось в последний час поставить таймлимит в 1 минуту на задачу вместо 5).

Как было замечено на небольших сложностях (да и сами организаторы говорили про это на сайте), что часто правильным ответом может быть функция существенно меньшей сложности, чем заявлено в условии. Поэтому таким методом можно получить очков за достаточно большое количество задач.

Общее впечталение

К недостаткам этого контеста стоит отнести следующее:

1. Задачка в основном сводилась к оптимизации перебора (что не очень весело и дает преимущество тем у кого есть много CPU power). Хотя, возможно, топовые команды и придумали что-то интересное. Мы пытались гуглить state of the art подходы к этому делу -- нашли какую-то микрософтовскую статью про применение SMT. Но статья ограничивалась описанием в стиле "мы тут придумали клевый алгоритм, который имеет меньше чем экспоненциальную сложность, но как его закодить вы все равно не поймете".
2. Организаторы почему-то сознательно не стали делать публичный scoreboard. Мне совершенно непонятна мотивация этого решения -- ведь так убивается весь соревновательный дух.

К положительным моментам стоит отнести, что в этом году сервера организаторов работали исправно, багов практически замечено не было, публичный api был удобным, ограничения на ddos были четко прописаны. Поэтому, в целом я считаю контест очень неплохим. Лучше чем прошлогодний про перебор путей в графе, но хуже чем 2010 и 2011 года.

PS. Мы набрали 1182 очка. По последним сообщениям с оффсайта это соответствует примерно 40му месту:

We have clear separations between the scores of the top 3 teams.
#11 is at around 1400.
#25 is at around 1250.
#50 is at around 1100.
#75 is at 904
#100 is at 701
#125 is at 568
#150 is at 428
#175 is at 291
#200 is at 206
#225 is at 116
#250 is at 38
#275 is at 0

Кому интересно, наш код доступен на гитхабе: https://github.com/pankdm/icfpc-2013 (однако, к концу третих суток соревнования он окончательно превратился в тыкву).

PPS. Кстати, на http://labs.skbkontur.ru/icfpc2013/ есть клевый визуализатор набранных очков:

PPPS. Отчеты других команд:

1. nbu (1458)
2. THIRTEEN (1456)
3. (unmatched (1301)

This is the reminder about upcoming ICFPC 2013.

Here is some important information from official site.

• The contest will start at: 1700 PDT on August 8, 2013 (0000 UTC on August 9, 2013)
• The contest will end at: 1700 PDT on August 11, 2013 (0000 UTC August 12, 2013).
• You need to pre-register for the contest, 48 hours prior (extended from 72h) to the contest at the latest.

Don't forget to participate and have fun!

Предисловие

Вот уже несколько дней я хожу под впечатления от ICFPC, поэтому в качестве продолжения этого развлечения решил написать сей отчет. Он задумывался больше для себя, поэтому условие я не пересказываю (тем, кто не ломал себе мозг, раздумыванием над задачей этого году - советую сначала прочитать отчет адепта, а то все дальше написанное покажется феерическим бредом :). Сразу предупреждаю, что впереди будет много букав, немножко разбавленных картинками и комментариями Алексея.

День 0 (Пятница, 18 июня)

16.00
Появилось условие. Распечатав и пробежавшись глазами, я естественно ничего не понял. ("This wasn't the ICFP contest if it was that easy." (c) organizers). Прочитав еще раз я тоже ничего не понял, но решил, что как-нибудь провремся. Забил на время на условие - надо было собираться на вручение дипломов студентам ШАД. Перед выходом я еще раз взглянул на условие, пронумеровал строчки в фабрике я заметил там закономерность - и мне показалось, что я понял как устроена фабрика (забегая вперед, скажу, что на самом деле все оказалось по-другому, но в целом идея была правильной).

Немного предыстории. Про дату контеста я узнал с хабра (http://habrahabr.ru/blogs/icfpc/96526/), буквально за 3 дня до начала. Про этот контест я слышал еще в прошлом году от Антона (С.) и Жени (Х.). Тогда надо было управлять полетами спутника. В этом году задание на первый взгляд полная жесть, потому что воообще непонятно как делать то, что они просят. Но сейчас, когда я уже пишу этот отчет, я понимаю, что это задание мне очень понравилось и оно концептуально точно интереснее задания со спутником.
В этом году я уже заранее знал, что буду участвовать, но еще не знал с кем. В прошлом году Антон обмолвился, что можно с  ними участвовать, поэтому я сначала написал ему. Но оказалось, что они с Женьком едут пьянствовать на выпускной ШАД. Дальше я написал Леше Тарасову. Он загорелся этой идеей, сказал, что обязательно надо участвовать - и вот уже в команде 2 человека [Alexey: Я вообще мучительно разгорался, так как со временем был напряг и пришлось пожертвовать неофициальной частью выпускного ШАД]. Мысленно повспоминав, кого можно еще позвать мы сошлись на том, что зовем Олега (мы все вместе какое-то время работали в Яндексе, поэтому положительный опыт совместной работы у нас есть) и 3 человека будет достаточно. Решили участвовать у Леши дома (как он сказал - у него квартира раздолбанная, но вместительная).


17.30
Собрал все самое необходимое (ноут, зарядка к ноуту, зарядка к телефону, спальник, зубная щетка / паста) и поехал на красную розу смотреть вручение дипломов.


21.00
Встретил Олега и Лешу и поехали к последнему. По дороге зашли в магазин - купили всякой еды. (Пельмешки :) - вспомнить студенческие годы)

22.00
Можно сказать, что только в это время для нас начался контест. Фора приличная  - 6 часов, но догоняемая.
Немного о технической части. Мы уже заранее знали, что основным языком программирования будет питон (благо все его хоть немного знают).  Операционная система Linux (потому что Unix c его шеллом отлично приспособлен для решения всякого рода исследовательских задач с большим количеством текстовых данных). В качестве системы контроля версий был выбран дропбокс (и он более чем оправдал себя). В двух словах - это автоматически синхронизируемая сетевая папка, которую можно расшарить другим людям  (+ еще есть история изменений, но она нам не нужна).  То есть мы получаем выделенное ОБЩЕЕ место с разделенным процессором и памятью и вдобавок еще практически свн на имеющихся файлах. Из минусов - нельзя одновременно редактировать какой-то файл (возможны конфликты) и нужен постоянный коннект к инету, но это была не проблема. Практически все 72 часа мы сидели все вместе в одной комнате и кодили, кодили, думали, итд.. с небольшими перерывами на еду, прогуляться, поспать и магазин.


Придумали название команде: первое предложение было "NoCamel", (типа перловцы не пройдут [Alexey: вообще это слоган выпускников ФМШ-18, к которым я отношусь]) - отметено сразу. Остановились на "SnakeTeam".

Прочитали еще раз все вместе задание.
Начали разбираться с устройства фабрик, как с наиболее понятной части задания.
Сначала было гипотеза, что L, R кодирует "forward" и "backward" wires. Поотправляв маленькие фабрики на сервак - эта идея не оправдалась. Зато мы заметили, что и справа и слева от разделителя "0#" для каждого N встречается одинаковое число раз NL и NR. Стало понятно, что они кодируют правый и левый выход и вход элементов схемы.
X - это вход и выход. Но об общем устройстве схемы у нас оставались сомнения:
сначала думали, что оно такое

(количество элементов схемы)L:
схема:
(количество элементов схемы)L
поэтому у нас не получалось отправить даже самую простую схему.

Еще все осложнялось тем, что Олег приехал без ноута и поэтому сидел за Лешиным старым ноутом. (В котором сетевая карточка не работает, вай-фай работает по 20 минут через 10). А в данный момент надо много было сабмитить в инет. Поэтому было принято волевое решение съездить ко мне в ГЗ за вторым ноутом. (Ехать надо было от профсоюзной - управились за 30 минут)


0.00
Вернулись с ноутом и всякой другой мелочевкой (коврики, тапочки) и вновь взялись за дело.

Рабочее место готово:


Пока я ездил - мне в голову пришла гениальная идея, что 19L: - это соединение с "External" элемента с 19, а X в схеме обозначает, что сюда подсоединяется "Еxternal" элемент.
Мы ее быстро проверили - и о чудо, работает! Теперь мы можем мастерить самые простые схемы.

С помощью схемы только из Х-элемента мы узнаем input сервера.

Дальше делаем все возможные схемы из X и 1 элемента. (их всего 4). Получаем некоторую информацию про первый элемент. Его можно мыслить просто как две функции трехзначной логики от двух переменных. Таких функций не очень много: 3^ (3^2) * 3^(3^2) = 387420489

Кодинг-кодинг-кодинг:


Тот же кодинг, вид сбоку:



Я начинаю на питоне писать полный перебор по всем парам функций. В это время ребята решают задачку аналитически. У меня получился какой-то багнутый (в пересечении 4х вариантов ни одной пары функций), долго работающий перебор. Переписываю на плюсах, чтобы быстрее было отлаживать (кстати скажу, что это была моя первая и последняя программа на плюсах за этот контест). К тому времени Олег с Лешей аналитически (и вроде все-таки с помощью небольшого перебора) находят решение, которое мы удачно проверяем на моей программе. И Ура! Вот эти функции

L: x - y
R: x*y - 1

Время уже кстати близится к 2м часам. Голова больше не варит. Решили на этой радостной ноте лечь спать. Тем более, что дальше надо очень много работы сделать по тому, чтобы понять, как сгенерить фабрику, дающую нужную последовательность.

Единственное что еще сделали перед сном  - проверили предположение, что все элементы в фабрике одинаковые.

День 1 (Суббота, 19 июня)

10.00
Утро началось с осознания, того что мы пока знаем, что делать дальше (это приятно :)), но с другой стороны работы предстоит много.

Я потихоньку начал придумывать фабрики, а Олег с Лешей писать парсер фабрик и интерпретатор. Когда у меня бывали затыки я помогал Олегу и в итоге нам удалось распарсить пример фабрики и сэмулировать ее работу. Ура! на нашем входе она дает то, что нужно.

Примерно в это же время я придумываю как сделать фабрику, получающую на вход что угодно и выдающую все время 0. (в наших обозначениях это была фабрика x-c0)

Дальше был прорыв, когда за счет обратных ребер с задержками мы получили фабрику x-0x, то есть получающую что угодно на вход и выдающую ту же самую последовательность, только с приписанным 0 спереди. После этого становится понятно, что надо научиться генерить фабрики x-1x и x-2x и задача генерации фабрики, генерирующей произвольный вход - решена.

Доделываю эту техническую часть. В это время остальные члены команды придумывают удобный формат записи фабрик (хранится в текстовом файле, можно определять базовые фабрики в формате организаторов и ставить вместо ребер другие фабрики из других файлов). А также пишут собиралку фабрики из файла в формат для отправки.

В итоге мы получили следующие файлы фабрик.
Какие-то из них базовые (ни от кого не зависят), другие строятся из простых, как их кирпичиков.


с0-0с1.txt    вход: константый 0, выход: 0, дальше константая 1
с0-1с0.txt
с0с1.txt    вход: 00..0, выход: 11...1
c2c0.txt
map01-10.txt    заменяет 0 и 1 во входе на 1 и 0 на выходе
map01-20.txt
x-0c1.txt    вход: xxxx.. , выход: 011....1
x-1c0.txt
x-1x.txt    вход: xxxx.. , выход: 1xxxx..
x-2c0.txt
x-2x.txt

Формат сложных фабрик был примерно такой:

Файл c0c1.txt:
//-----
0L:        // базовая фабрика
X1R0#1L1R,
0L0R0#X0R:
1L

[(1,1,"c2c0.txt","d")] // массив преобразований фабрики
//-----------
(1, // к выходу из элемента 1
1,  // к правому выходу
"c2c0.txt", // подцепляем фабрику из файла c2c0.txt
"d") // ниже элемента (важно когда обратное ребро)

В процессе сборки фабрик нам потребовалась реализовать еще одну операцию - join: дописать подряд (вход одной к выходу другой) фабрики из нескольких файлов.
Например, файл c0-1c0.txt:

join
c0-0c1.txt
map01-10.txt

После всего этого, программа, которая по заданному выходу генерит фабрику, пишется просто элементарно. (Надо в обратном порядке записать нужные строки из  [x-0x.txt, x-1x.txt, x-2x.txt] в файл, а потом вызвать преобразовалку в формат для отправки.)

Таким образом, к 16.00 мы засабмитили топливо к машине 0 (фабрика, производящая требуемый префикс была размера примерно 600). Немножко пошаманив, мне удалось отправить топливо "11111" к трем машинам и это были наши первые шаги к получению очков.

Забегая вперед, скажу, что наш способ построения фабрик был далек от оптимального. У нас, чтобы сгенерить аутпут порядка N, требовалась фабрика размера 40N, в то время, как другие люди добивались результат 2N. В голове всплывает такая картинка:




Кстати, очень важно отвлекаться и менять вид деятельности. Поэтому дальше мы пошли погулять и подышать свежим воздухом, чтобы хоть немного проветрить мозг. [Alexey: Это была очень и очень правильная идея!]


18.00
Решили распараллелиться:
я занимаюсь ломанием топлива,
Олег - машин,
а Леша пишет скрипт, с помощью которого можно сабмиттить топливо для машины прямо из консоли.


Далее, методом научного тыка я выясняю следующее:
100...         :топливо из 1 танкера, 0 ингр.
1100...        :1 танкер, 1 ингр., ошибка размерности
11100..        :1 танкер, 1 ингр, С(1,1) = 0
1111000..    :(1, 1), С(1,1) = 1
1111100..    :(1, 1), С(1,1) >= 2         


Вообще говоря, машина - система уравнений вида a_1 * a_2 * .. > (>=) b_1 * b_2 * .... .
Количество уравнений - это количество chamber-ов в машине,
количество переменных - количество танкеров.
Топливо - это решение. Кол-во ингредиентов - это размерность решения.
Это стало понятно почти сразу после начала контеста, но если не знаешь как задавать топливо и машины в тритах, то этим никак не воспользуешься.


Нетрудно доказать, что последнее топливо будет подходить ко всем машинам, в которых 1 танкер и любое количество уравнений.  Я начал руками его подставлять во все машины подряд, попутно отдавая Олегу информацию про эти машины. (по сообщениям парсера можно узнать что-то про танкеры, чамберы у машины)

22.00
Точно таким же методом научного тыка я подбираю синтаксически корректное топливо к 2-х танкерным машинам. (получилось что-то типа "2201111111"). К этому времени Леша уже дописывает скрипт сабмита топлива и скрипт выдирания списка всех существующих машин. Мы говорим скрипту, чтобы он сабмитил по порядку во все машины 2 известных нам топлива: "11111" , "2201111111". Он радостно работает и число решенных нами машин весело возрастает (как впрочем и наше количество очков). Олег с помощью бубна сабмитит нашу первую машину и уезжает домой.

Дальше каким-то образом нам удается варьировать количество танкеров и ингредиентов в топливо, но общая логика ускользает. Например, почему:

22     = 2, 0
222    = expected '2'
2222     = 6, 0
22222    = expected '2'
222222     = 366, 0
2201    = 2, 1
122    = 1, 2

00.00
Леша дописал на перле свой мега-агрегат по сабмиту топлива. Теперь у нас на диске для каждой машины с номером N создавалcя в специально отведенном месте файл N.info. Первая строчка - описание машины в троичном формате, дальше весь лог нашего общения с ней. И если машина решена то пишется строчка "Solved". Другой специальный скрипт с помощью grep-a выдирает файлы в которых нет строчки "Solved" и делает список таких файлов. По которому можно пройтись еще одним скриптом и засабмитить какое-нибудь топливо по этой машине.

perl-coder detected!! ^):



Олег доехал до дома и по дороге ему пришла гениальная мысль. Нам Верещагин на курсе по Колмогоровской сложности рассказывал про сложность префиксного кодирования числа N.

Например, вот что сказал Олег:
"tanks comps chambers
219 0 0 0 1
2146 122000010 1 1 1
2625 1221'0'000010' 1 1 1
2627 1221'1'000001'0 1 1 1
2634 1221'2'000000'10 1 1 1
2638 122220'00'000000010' 1 1 1
2641 122220'01'000000001'0 1 1 1
2644 122220'02'000000000'10 1 1 1
2646 122220'10'000000000'010 1 1 1
2648 122220'11'000000000'0010 1 1 1

Чтобы префиксно закодировать число N, надо сначала написать количество бит, а затем сами биты. Но чтобы написать количество бит (log_2 N), надо написать log_2 log_2 N и т.д. То, что у меня выделено во 2 группе (1, 2, 3 или 4 цифры) - это размер последней группы. Но размер второй группы тоже надо указать. Он указан в первой
1221     - 1 цифра
1222220 - 2 цифры
1222210 - 3 цифры
...
"
Это еще не было окончательное решение, но чувствовалось, что мы еще на один шаг ближе к истине.

02.00
К этом времени мой мозг окончательно отключился и я перестал соображать. Поэтому мы отправились спать. А Олег кажется понял как кодируются числа в машине и начал писать парсер таких чисел. А затем заодно и парсер машины.

День 2 (Воскресенье, 20 июня)

Проснулся и сразу в бой!:



10.00
Не знаю до скольки еще вчера Олега сидел. Но на утро у нас были почти работающие парсеры машин и чисел.

На почте у меня было письмо примерно такого содержания:
"В общем, парсилка строки в последовательность чисел - parse_string.py. Только вот она не может парсить машины, ибо у них формат немного другой.

Предполагаемый формат машины: (кол-во чамберов) чамбер1 чамбер2 чамбер3 ...

Формат чамбера: (кол-во секций в верхней трубе) (верхняя труба) (0|10) (кол-во секций в нижней трубе) (нижняя)
(0|10) посередине - это Main (0) или Aux (10).

Формат трубы:
Префиксный код секций.
0 - 0
10 - 1
11 - 2
12 - 3
?? - 4
?? - 5

Прога, парсящая машины по такому формату, - parse_cars.py. Она глохнет на машине 2689, однако, предыдущие 76 обрабатываются нормально."

Уже почти все понятно, но на самом деле до конца все равно не ясно. Не помню, что конкретно мы делали следующее время - но к 14.00 нам удалось понять формат кодирования чисел в топливе и машинах, а значит и написать парсер машин и генератор нужного топлива. Таким образом, вся загадочная часть закончилась. Осталась только математическая и это не могло не радовать.
[Alexey: История определения была очень забавная. В какой-то момент из топлива удалось выделить осмысленный кусок 22011, который обозначал какое-то число. Чтобы узнать, что же это за число, мы сделали машину со специальной ошибкой, в которую подсунули 22011 в виде номера бака. В результате нам вернулся ответ: "в машине не подсоединен бак номер 8". После этого задача сразу рассыпалась. Мы выяснили как кодируются баки, 4 оказалось 22000, а 5 22001. Дальше быстро раскололи, как кодируется все топливо].
Леша начал реализовывать свою гениальную идею о том, как можно решать машины. Идея состояла в следующем: будем решать одномерную задачу, рассмотрим неравенство, задаваемое одним чабмеров. Возьмем логарифм от обоих частей. Получим линейное неравенство относительно логарифмов. Таким образом, надо решить систему линейных неравенств - классическая задача линейного программирования. Решаем ее так: берем какой-нибудь известный солвер (Леша умел пользоваться glpk - GNU Linear Programming Kit) и прикручиваем его к нашей задаче. Он решает ее в вещественных числах, поэтому нам еще придется найти целочисленное решение подходящее под ответ. Также обнаружилась следующая неприятная особенность: glpk умеет решать только замкнутую задачу a >= b (или по крайней мере мы умеем задавать ему только такую задачу). А  у нас были неравенства и a > b. Не знаю, какие костыли приделал к нему Леша, но в конце концов солвер сможет решать машины.


16.00
Приезжает Олега. Он начинает думать о том, как можно генерить сложные задачи. Я в это время дописываю наш первый солвер: stupid_solver.py, который каждой машине в зависимости от количества танкеров в ней отправляет последовательность из нужного числа двоек. Он берет какое-то количество машин.

Но мы на этом не останавливаемся: дальше я пишу brute_solver.py, который берет t переменных (t - количетво танкеров) и перебирает значение каждой от 1 до (10^6 ^ (1 / t)). То есть, чтобы всего вариантов на каждую машину было не очень много (10^6). Тогда же и был написан локальный проверяльщик подходит ли топливо к машине (так как гонять 10^6 вариантов по инету это ооооооочень долго - да и к тому времени их сервак начал подтормаживать)

В это же время Леша пишет свой решатель машинок методом ЛП. fool_solver.py (следующая стадия после моего stupida :), это название понравилось мне еще и тем, что звучит также как и full - метод то и правда достаточно универсальный). Запускаем наши методы почти одновременно - каждый из них решает порядка 100 машин - очень неплохой результат (правда было непонятно, сколько из этих уникальных машин).

Параллельно с этим пытаемся придумывать сложные машинки. Был идея придумать машинку, которая не решается в одномерных переменных. Понятно, что должно быть как минимум две переменных. Беру самое простое уравнение: A * B > B * A. ( > - следует понимать так: первая строка поэлементно >, все остальные >= , A,B - матрицы 2*2). Придумываю какие-то рандомные примеры, проверяю в перемножением матриц в Sage - ничего не получается. Прошу Олега решать такое матричное уравнение в неопределенных переменных в Mathematice. Ничего не выдает. И тут до Олега доходит, что оно в принципе не решаемо. Так как tr(A * B) = tr(B * A) - поэтому (A*B)[1,1] + (A*B)[2,2] = (B*A)[1,1] + (B*A)[1,1]. А с другой стороны (A*B)[1,1] > (B*A)[1,1] и (B*A)[1,1] >= (A*B)[2,2]. Противоречие.


Еще наблюдаем статистику по длине фабрик - люди умудрялись делать фабрики размера 6 (!!). Когда у нас например фабрика, генерирующая только легальный префикс имела размера порядка 500!. В общем быть с маленькой фабрикой нам не светит. Но с другой стороны, если ты решил машинку, то каждый тик будешь получать не больше чем в два раза меньше того, кто решил ее наилучшим образом. Поэтому надо просто больше задач решать и сложные придумывать.


20.00
Дальше мозг отказывается думать (по крайней мере лично у меня). Опять идем гулять. В ростиксе перекусываем. Мы с Лешей опрокидываем по 0.5 пива в надежде достичь пика Балмера. Также было решено сосредоточиться на придумывании новых относительно сложных задач, потому как решатель более менее нормальный у нас есть. Еще пришла следующая идея для машин. Рассмотрим уравнение a^99 = b^100. Минимальное решение у него 2^100 и 2^99, что исключает переборное решение. Если там еще чего-нибудь накрутить, то может получиться вполне себе задачка.



22.00
Пика Балмера мне достичь не удалось - мозг встал окончательно, зато прогаться стало легко как никогда. [Alexey: Ну идея пика Балмера как раз в том, чтобы меньше думать перегруженной головой. Мне пиво однозначено помогло. И прогаться стало значительно легче и думаться.] Олег начал реализовывать задачку с a^99 = b^100, только с наворотами (например безумные коэффициенты, за счет подстановок например таких a = c^1000, c = d^1000 итп. - я деталей уже не знаю). Леша еще улучшает солвер за счет каких-то оптимизаций и пытается придумать многомерный пример. А в целом туплю и иногда прогаю скрипты, которые меня просят.

Пытаемся скормить наши задачки нашему солверу - он их успешно не решает. Значит, можно засылать. Но сервер уже конкретно подтормаживает + появляется какое-то глупое ограничение на длину машины (100 вроде). Поэтому наш метод сразу пролетает. Олег выдумывает еще какой-то метод, основанный на матрицах. Задачки кажутся сложными - и мы их вручную сабмитим на сервак (сервер почти встал и скрипты вообще не пробиваются - удается иногда вручную засабмитить). В итоге мы заслали где-то 50 задач. И тут как-то заметили, что одну из таких задач уже решило человек 25. Видимо у них были простые решения (наверно даже одномерные). Забили на этот способ.

В это же время Леша периодически запускает свой солвер на новых задачках, а я запускаю брут солвер на них же. (Хотели сделать это по кронтабу, но изза торомозов, список новых машин с описаниями никак не выдирался с сервака - приходилось вручную делать).

01.00
Сервер окончательно встает (Error 503 Service Temporary Unavailable). Видимо все шлют новые / решает старые машинки (прям воруй / убивай какой-то). А так как все это делается скриптами - хабраэффект неминуем. Когда ты ничего не можешь заслать и даже посмотреть highscores - интерес что-то делать пропадает и хочется забить и лечь спать.

Тут мы как-то замечаем (не знаю как это получилось в условиях таких лагов), что ограничения на длину машины пропадает - можно слать наши первые задачки.
Пытаемся разобраться с кронтабом, чтобы лечь спать, а он каждые 10 минут засылал наши задачки, а также качал новые, решал их и отправлял. Чтобы если образуется какая-то дырка без лагов, то мы либо сделали свое дело, либо еще больше его подвесили - не давая остальным получать очки. Получились полуавтоматические скрипты с практически встроенным разумом. (но скачивать новые машины все равно надо вручную). Тогда же мы и написали обобщенный солвер - который сначала решает методом ЛП, а потом пытаеся обычным перебором (так на всякий случай - защита от глупых багов в ЛП).

Ручная проверка фабрики из 13К элементов:




04.00
Удивительно, но сервер заработал! Отсылаем еще 20 сложных машин (оставив 2 просто для фана на утро). Через какое-то время проверяем - их еще никто не решил. Можно со спокойной совестью ложиться спать. Между тем уже светает - в голове безумные мысли бегают, не дают уснуть (как впрочем и предыдущие 2 ночи). Расстилаем спальники на полу, на матрасе и до утра можно отдыхать.

День 3 (Понедельник, 21 июня)

10.00
На утро видим, что мы очень даже неплохо поднялсиь за ночь. (Очевидно, что за счет сложных задач). Мы уже в топ 20! За ночь набежало порядка 1000 задач - надо отдавать скрипту их решать. Он справляется с не меньше чем с половиной.

Сервер просто летает - это не может не радовать.

Засабмичиваем две оставшиеся задачи. Думаем чем бы еще заняться, кроме как запуска каждые 10 минут решения новых задач. Возникает идея придумать бота, который будет слать наши сложные задачки, а мы их будем решать и в итоге делить очки с ним пополам (можно даже сделать так, что мы будем их решать лучше бота :) - чтобы больше очков получать).

Сказано - сделано. Регаем бота. Без палева называем его "SnakeTeamBot" :) (в правилах ничего не сказано про то что ботов нельзя делать :)). Правда есть одно ограничение - нельзя слать машинок больше, чем ты решил. Ну что ж - даем боту в руки stupid_solver (чтобы он ненароком не решил сложные задачки :) ) и вперед. Дальше сабмит задачек и решения их с нашего аккаунта. (Все в почти автоматическом режиме - почти все реализовано на скриптах).

Естественно мысль пошла дальше - ведь можно написать скрипт, который будет делать все это несколько раз. Решено было забить, так как времени осталось мало и вряд ли мы кого-нибудь обгоним таким трюком [Alexey: написание бота было скорее развлечением и проверкой насколько хорошо работает алгоритм Олега по созданию мащин, получать сколько-то серьезное преимущество за счет бота не хотелось ].


13.00
Осталось 3 часа до контеста - занимаемся всякой фигней, помимо запуска решателя (уже сразу же после того, как отработал предыдущий - наплыв новых машин очень высокий)
Уверенно держимся на 15 месте.
Наш бот уверенно ползет вверх и уже забрался в топ100

14.00
Леша уходит на работу, да и мы разбредаемся по домам. Финишировать будем уже дома.

15.00
Уже из дома запускаю солвер. Между тем, нас догоняет команда vorpal [Alexey: это пресловутый vorpal sword из jabberwocky]. С каждым тиком отставание сокращается. Успеем ли мы выстоять?

16.00
Вот и конец.
Финальная таблица (5 верхних не показывается):
3 548,266    joho
3 317,292    HITOCry
3 246,312    Celestial Dire Badger
3 233,006    perpetuum_mobile
3 047,350    Fail0verFlow
2 657,573    ocamlriders
2 506,430    The Cat is #1!!
2 500,582    6-11
1 947,789    eger a marson
1 672,753    SnakeTeam
1 667,446    vorpal
1 323,462    shinh2

Финишировали с 15 местом - очень неплохой результат. Бот - на 54.

До верхних нам было не добраться, но натиск vorpala мы выдержали :). Видимо нам в этом неслабо помогла команда SnakeTeamBot [Alexey: по прикидкам она дал нам 200-300 очкой, то есть дал ровно одно место]. Кстати, мы мониторили сколько человек решили эти сложные задачки - к концу контеста, кроме наших монстуозных решений по 13к было решений еще максимум от 2х команд (примерно по 3к).

---

Итого

Впечатления от контеста сугубо положительные. Практически до конца оставался энтузиазм что-то делать. Порадовало, что задачка получилась очень многогранной и развиваться в ней можно было в разные стороны. Респект организаторам за подготовку такого мероприятия. Мне понравился опыт работы в команде - один бы я точно не написал такую тонну кода, который мы наваяли за эти дни и не разгадал все загадки оргов.

Про тулзы. Дропбокс - мега штука. Очень удобно. Нам периодически приходилось меняться компами - и когда ты садишься за чужой - у тебя точно такая же общая папочка как и на твоем. Linux - это тоже очень круто. Я не представляю  как можно в винде заниматься такими  задачками, когда там даже нормального шелла нет. А когда ты можем любое свое действие сделать автоматическим - это реально помогает. Еще мега круто писать на языках высокого уровня, а еще более круто писать всем на одном языке - питоне. Тебе нужна функция которая уже написана в другом модуле: "from module_name import function_name as f" - спасет отца русской демократии. (у нас был небольшой фэйл, что веб скрипт начал писаться на перле и потом его просто не было времени переписывать, поэтому приходилось склеивать эти штуки с помощью шелла). Еще очень важно все находиться в одной комнате и общаться вживую - это экономит кучу сил и позволяет лучше понимать друг друга. Собраться всем у Леши было отличной идеей.

Из минусов. Естественно, как и от всякого глобального мероприятия - от этого контеста жутко устаешь. Не так-то просто в бешеном темпе фигачить несколько суток подряд. Поэтому такое развлечение должно быть не чаще чем раз в год. Еще дико раздражало когда сервер висел. Если бы задачка не была завязана на черный ящик, который на сервере, то это было бы терпимо, но когда ты без сервера остаешься без информации - теряется всякий интерес что-то делать.

Такие дела. Участвуйте в icfpc и получайте от этого море фана!


[Alexey: Ощущения после окончания можно передать так: мы поехали на ралли Париж-Дакар и умудрились пройти все этапы, некоторые грубо проломив, доехали до конца и с еще очень приличным результатом.

После мероприятия у меня родилась фраза передающее мое состояние в данный момент:

"Дайте мне мощный комп и достаточно времени, и я запрограммирую землю."]

Бонус: вот это видео отлично передает мое общее впечатление от контеста.


UPD: http://jerom.livejournal.com/161481.html - отличная подборка отчетов других команд.