Кто-нибудь еще участвовал в прошедшем 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)