Продолжается TopCoder Open 2011.

Вчера в 10 утра должен был начаться проводимый нами турнир по покеру, победителю которого мы приготовили очень ценный приз в виде MacBook Air. Желающих сыграть оказалось достаточно много, поэтому всех пришлось разбить на два полуфинала. Из 16 человек, желающих сыграть, 8 оказалось русских, и волшебный Random Seed как-то разбил участников так, что один стол оказался целиком русскоговорящим. За ним выиграли Петя и Миша Кевер. По неприятному стечению обстоятельств у меня не осталось фотографии самого полуфинала, но позднее в тот день мы сыграли еще раз, уже неофициально, на том же самом месте, поэтому можно увидеть как это примерно выглядело:


В прошлый раз я почти не выкладывал фотографий места, где проходит TCO, кроме одного вида из окна. Проходит соревнование в отеле The Westin Diplomat.


Это в городе Hollywood. Город находится в 20 минутах от Маями, но выглядит как небольшая деревенька, правда с пальмами в очень больших количествах :о) Сам отель смотрится в этом месте неуместно, будучи 36-ти этажным зданием. Как можно было понять по виду из окна, он находится прямо на берегу океана. Выйдя из отеля, попадаешь сразу на пляж, и через два шага уже прыгаешь в воду.

Сегодня я и Эрик, CEO нашей компании, полетели во Флориду в город Hollywood на TopCoder Open 2011, который мы спонсируем. Помимо нас его спонсируют Intel и Facebook.
Мы вылетели из Сан Франциско в 8 утра. В аэропорту увидели Петю Митричева, что даже заставило нас ненадолго поверить, что он переехал в Сан Франциско. Уже прилетев во Флориду перекинулись с ним парой слов, из которых выяснилось, что Петя никуда пока не переехал и, кажется, что переезжать не хочет...
Добрались до отеля, где на входе уже встречала вывеска ТопКодера. Что это за компания перечислена внизу третьей? :о


Пошли в Ballroom, где по расписанию до шести вечера спонсоры должны были приготовить их столы. Время было без трех минут шесть :о( У Интела в комнате целый огромный угол, у Фейсбука и у нас по небольшому столу и телевизору. Вот так это примерно выглядит:


Когда все приготовили, пошли заселяться в номер. Из разговора с участниками позже я понял, что TopCoder не очень расщедрился на номера с видом на океан для участников. Так как нам TopCoder номер не предоставил, мы взяли себе сами с красивым видом.


В 2008-ом, когда я много ездил по разным ивентам, я фотографировал всех крутых ACM-щиков, и людей, тесно с этим связанных, с плюшевым поросенком. Я выкладывал уже в блоге на Codeforces фотографии многих из них, еще больше выложено в фотоальбоме на mail.ru. В этот раз от меня не ускользнули еще три важных человека в сообществе. Иван Метельский, кто готовил раунды на TopCoder, и играет очень важную роль в проведении TopCoder Open в частности:

И Артем Рахов и Михаил Мирзаянов, которые создают и поддерживают Codeforces. Ребята мне даже подарили фирменную футболку codeforces :)

Как и в прошлом году, в этом году готовиться к ICFPC мы начали заранее. Основная проблема прошлого года была зоопарк языков программирования. В этом мы заранее договорились, что будем писать на Java, но позже, из-за того, что некоторые ребята умели писать только на С++, поменяли выбор на С++. Всем было понятно, что этот язык не подходит для такого рода соревнования, но идея писать в crazy mode и тратить время на memory leaks и другие чудеса С++ в принципе всех устраивала. Потом это немного выйдет боком – просранная инициализация переменной заставит нас поломать голову над тем, почему решение падает один раз из 20 посылок :о) А еще надо было писать под Linux, так что для меня это было еще и первое серьезное знакомство с vim.
Умные ребята заметили, что картинка на сайте с символом lambda содержит в себе JAR архив, в котором лежит другая картинка, с изображением MTG-карты с лямбдой. Было понятно, что условие будет связано с lambda calculus и с Magic: The Gathering. Это так и оказалось.

Условие.
Условие можно пропустить, если вы его знаете, или прочитать по диагонали (особенно описание карт). Вникать не обязательно.
Играют два игрока. У каждого есть 256 слотов. Каждый слот характеризуется его хп (в начале 10К) и его содержимым. Содержимое – либо число, либо функция.
Также у каждого игрока есть неограниченный набор карт. Каждая карта – это тоже либо число (такая карта всего одна -- zero), либо функция. На своем ходу игрок выбирает одну карту, и один свой слот. Если у слота ноль хп, ход сразу завершается, и ничего не происходит. Иначе, игрок говорит, хочет он сыграть слот на карту, или карту на слот. В первом случае, если в слоте функция, то она вызывается, и в качестве параметра ей передается выбранная карта, а если в слоте было число, то ход завершается с ошибкой. Во втором случае все происходит наоборот – значение в слоте передается в качестве параметра функции на карте. В обоих случаях результат выполнения заносится в выбранный слот.
Например, пусть в слоте лежит фукцния I (функция, которая принимает один аргумент, и возвращает его). Пусть игрок выбрал этот слот, и выбрал карту zero, а затем выбрал, что он играет слот на карту. Тогда значение на карте (ноль) будет передано функции в слоте (I) в качестве аргумента. Результат (который, очевидно ноль) будет помещен в слот.
Далее по тексту ход “revive 5” будет обозначать игру карты revive на слот 5, а ход “5 revive” – игру слота пять на карту revive (номер слота и название карты выбраны для примера).
Игра кончается либо когда у одного из игроков все слоты имеют 0хп, либо после 100К ходов.
Кратко пробежимся по картам:
I(x) – функция, которая возвращает x.
Zero – число ноль
Succ(x) – возвращает x + 1
Dbl(x) – возвращает x*2
Inc(x) – увеличивает хп в своем слоте x на один.
Dec(x) – уменьшает хп в слоте оппонента с номером 255-x на один.
Attack(i,j,n) – наносит в свой слот номер i n урона, а в слот оппонента с номером 255-j n*9/10 урона. То есть себе наносится урона больше. При этом если в своей клетке меньше чем n хп, то атака не пройдет – это важный момент. При этом если в слоте оппонента меньше хп, то атака пройдет, просто оставив в клетке 0 хп.
Help(i,j,n) – наносит в свой слот номер i n урона, и свой же слот j лечит на 11*n/10. Опять же, если хп не хватает в i-ой клетке, то ничего не сработает.
Put(x) – возвращает I.
Get(x) – возвращает содержимое своей клетки с номером x. Очень удобная функция :о)
Copy(x) – возвращает содержимое клетки оппонента с номером x.
Revive(x) – если в своей клетке x ноль хп (она мертва), делает в ней 1 хп.
Это все были скучные функции. Еще две функции выносили мозг:
K(x,y) – возвращает x
S(x,y,z) – вычисляет h=x(z), вычисляет g=y(z), возвращает h(g).
И одна функция делает всю эту игру втройне интереснее:
Zombie(i,f) – если у оппонента слот 255-i мертв, то делает ей -1 хп, и помещает туда функцию f.
Сразу же после этого, перед ходом оппонента, все клетки, у которых -1 хп, автоматически вызывают содержащуюся в них функцию (и кол-во хп меняется обратно на ноль), передав ей в качестве параметра I. При этом (и это самое крутое) в этот момент значение функций inc, dec, attack и help меняют знак в своем позитивном эффекте. Так, inc наносит урон вместо лечения, dec лечит вместо нанесения урона, attack лечит вместо нанесения урона врагу (но по прежнему наносит урон себе), help наносит урон дважды вместо нанесения урона и лечения.
Теперь к повествованию.

Первый день, четверг.
Контест начался в пять вечера по моему времени. Я ошибся с переводом времени, и был уверен, что он начнется только в пятницу. Случайно открыв сайт в восемь вечера я был очень неприятно удивлен.
О стратегии пока думать было рано. В любом случае будет нужен эмулятор игры, поэтому сначала я написал классы карты, слота, игры, и вбил эффекты всех карт. С++ для этого оказался не самым лучшим выбором, но было поздно идти назад :о) Потом написал небольшой интерпретатор, который позволяет играть двумя игроками. Жюри предоставляло свой, но он был ужасно неудобен в плане управления, и добавления AI. День примерно так и кончился. Ребята за ночь хорошо проанализировали разные комбирации, и составили целую страницу идей.

День второй. Пятница.
Теперь, когда небольшой набор инструментов есть, можно пытаться думать о стратегии. Первая мысль, которую мы проверяем, это бесконечные циклы. Получается написать функцию, которая вызывает inc(0), то есть лечит нулевую клетку, а потом вызывает саму себя. Неприятность в том, что если в течение хода выполняется более 1000 функций, то ход останавливается с ошибкой (при этом выполненные эффекты не отменяются). Из-за этого лечащая функция успевает полечить только на 200. При стартовом ХП у клетеки в 10000 сразу видно, что inc и dec бесполезные функции (dec может быть разве что полезен добивать слот, который оживили revive-ом, так как у слота в этот момент 0 хп, но это мы так и не применили почти).
Несколько важных моментов еще: 0-ой слот стратегически очень важен, потому что к нему легко обращаться. Допустим, чтобы его оживить достаточно сделать x revive; x zero, где x – номер любого другого слота. И, в тоже время, нулевой слот очень сложно убить, потому что все функции, которые общаются к клетке оппонента, обращаются к клетке с номером 255-i, поэтому чтобы нанести урон в нулевую клетку, надо передать 255 в качестве аргумента, а набрать 255 используя только succ и dbl очень сложно. Ближе к середине контеста станет понятно, что тот, кто убивает нулевую клетку быстрее, побеждает, потому что оппонент теряет возможность эффективно играть.
Значит первая идея стратегии такая. Сначала мы набираем с помощью dbl число 8192 в 0-ом слоте. Потом мы делаем attack(0,0,get(0)), что значит, напомню
1. Нанести себе get(0) = 8192 урона в нулевой слот (он останется жив)
2. Нанести оппоненту 8192*0.9 урона в 255-0=255 слот
Затем сразу делаем attack(1,0,get(0)), что наносит нам 8192 урона уже в первый слот, а оппоненту опять 9/10 от 8К опять в 255. Это убивает 255-ый слот оппонента. А в убитый слот, как мы знаем, можно посадить зомби. А зомби вызывается от имени оппонента, и не имеет проблемы с 255-x. В зомби закладываем функцию, которая делает help(0,0,8192), которая, как мы помним, если выполняется от имени зомби, имеет другой эффект, и просто наносит два раза 8192 урона в нулевую клетку, что ее благополучно убивает. Затем строим функцию help(1,1,8192), которая убивает первую клетку таким же образом.
Сложность в реализации была в том, что не любую функцию легко построить. Например, пусть мы хотим получить attack(get(0),get(0)). Мы играем 0 get, получаем get (в нулевом слоте была функция I, мы передали ей get в качестве аргумента, и она вернула get). Мы играем 0 zero, получаем get(0). Мы играем attack 0, получаем attack(get(0)). Как теперь сделать attack(get(0),get(0))? Чтобы это сделать, надо сделать K 0, S 0, 0 get, 0 zero. Не тривиально? А что, если нужная нам функция гораздо сложнее? Поэтому пришлось потратить не маленькое количество времени на то, чтобы написать раскрывалку скобок – программу, которая берет на вход строку, и возвращает ходы, которые эту строку позволят получить. С таким функционалом писать ботов стало проще. Для не интерактивного бота (который просто за ранее вычисляет свои ходы, и играет их игнорируя действия оппонента) мы просто складываем в вектор результаты работы раскрывателя скобок.
Для первого бота мы просто написали функции вызова зомби последовательно с функциями help(0,0,8192), help(1,1,8192), доверив раскрывателю скобок их построить, и не думая об оптимизации этого процесса с помощью функции get совсем.
Такой бот за ночь с пятницы на субботу в неофициальной турнирной таблице, предоставленной организаторами,  занял третье место.

День третий. Суббота.
Но конкуренты придумывали более крутых ботов, и наш бот постепенно падал вниз. Надо было оптимизировать. Благодаря использованию метода get, и просто оптимизации всех частей кода, получилось убивать нулевую клетку на 50-ый ход. Но кто-то умел делать это быстрее – потому что проигрывали мы в конце с такой тактикой всем топовым командам. Но для этой стратегии улучшить этот аспект уже не получилось. Все, что мы смогли улучшить сильнее, это убийство последующих слотов – за счет, опять же, грамотного использования команды get, мы убивали последующие слоты раз в три хода, убивая все за 1200. Лучшее что я видел в дуэлях, это алгоритм, убивающий нас за 500 ходов с чем-то. Он был на первом месте очень долгое время. Но было понятно, что не важно, как быстро ты убиваешь все. Важно было как быстро ты убиваешь нулевую. Потому наш алгоритм, который работает за 1200, часто убивали за 70К ходов, просто потому, что убивали нам нулевую быстрее – а без нулевой мы не могли сделать ничего.
Вечером я забил на развитие алгоритма с зомби, и начал исследовать новую идею, бота под кодовым названием healer. Если набрать число 8192 в первом слоте, а затем сделать help(0,0,get(1)), то мы нанесем себе в нулевой слот 8192 урона, а потом полечим его на 11/10 от 8192, то есть в итоге мы полечим клетку на 800 хп. Если это делать в бесконечной рекурсии, то она успевает поличить до максимума – до 65К (любые числа больше 65К в игре делались равными 65К насильно) прежде чем падает из-за вызова 1000 функций. Полагая, что все оппоненты, как и мы, будут пытаться слепо нанести 10К урона в нулевой слот, это должно было делать его неуязвимым. Такое получалось сделать уже на 36-ой ход.
Идея интересная, но час был поздний. Развивать ее времени бы не хватило, а проверить концепт как-то было надо. В качестве проверки я написал простой алгоритм, который после лечения до 65К нулевой клетки лечил по очереди все остальные, а затем начинал делать attack(get(0),get(0),get(1)), храня в первом слоте 16К, а в нулевом счетчик, который после каждой атаки увеличивался на один. Таким образом каждый ход я наносил 16К урона себе в очередную клетку (в которой 65К хп – ей это как комариный укус) и 9/10 от 16К оппоненту в очередной слот. Полагая, что оппонент не лечился, это убьет ему слот.
В таком виде я бота заслал. Он убивал все слоты оппонента за 4К ходов, если оппонент бездействовал или не учитывал, что у нас может быть 65К хп. Healer играл хуже чем зомби (но это и ожидаемо – это проверка концепта). Для зомби все шаги были оптимизированы до фанатизма, а в этом боте просто вбиты в том виде, в каком приходили в голову. Некоторые топовые боты его рвали как грелку. Это тоже ожидаемо. Но в остальном он дал некоторую пищу для размышления.
1. Он часто побеждал после 100К хода со счетом 255-1. То есть у нашего бота был убит один слот, а у оппонента один оставался жив. Легко понять, что это значит, что против нас играет что-то похожее на нашего зомби – оно убивает 255 клетку нам (мы ее лечим очень поздно), а затем пытается убить что-то еще, но не ожидает, что там 65К хп. В тоже время мы отлечиваем все наши клетки кроме 255-ой (которую нам убили), а потом убиваем оппоненту все клетки кроме нулевой, потому что наша 255, об которую мы бы это делали, мертва.
2. Часто мы проигрывали после 100К хода со счетом, допустим, 96-160. Не сложно заметить, что сумма чисел равна 256. Это, как опять же легко понять, оппоненты, которые просто пытаются быстро убивать слоты по порядку с конца, в то время как мы лечимся по порядку с начала. И, так как они убивают быстрее, чем мы лечим, то в итоге счет в их пользу (одно лечение занимает шесть ходов в нашей реализации, а одно убийство – четыре в лучшей, которую я могу представить).
Я ушел спать, а ребята оптимизировали healer’а.

День последний. Воскресенье.
Утром восресения до конца контеста оставалось еще 8 часов, но это было воскресенье, и на него уже были планы, поэтому я вышел из игры. Позже ребята допилили нового helper’а, который убивал оппонента быстрее, но в итоге в неофициальной таблице результатов зомби выигрывал чаще, чем healer, и именно его мы заслали как наше финальное решение.

Все наши боты были не интерактивные – мы предпросчитывали последовательность ходов, и просто ее выполняли. Поэтому написанный мной в начале эмулятор, который позволял поддерживать по набору ходов текущее состояние поля, по большому счету оказался бесполезным.
Контест не оставил такого же ощущения удовлетворения, как прошлогодний. В основном потому, что в этом году из-за большого количества отвлекающий факторов, и планов, не получалось посвятить все три дня целиком контесту. Это очень обидно. Написать симулируемый отжиг, чтобы найти короткую последовательность убийства нулевой клетки, или какую-то модель машинного обучения, чтобы менять тактики на ходу в зависимости от действий оппонента, было бы очень интересно, но я даже не брался за это, потому что понимал, что времени не хватит. И писать это на С++ в vim было бы очень смело.
В следующем году придется очень заранее думать над тем, чтобы планов никаких не было. Надо отметить, что соревнования посередине ICFPC написать хорошо не получается. TCO Round 1 был в восемь утра, но за день до этого я лег в четыре, потому что дописывал бота. В итоге место в третьей сотне – событие, которого не происходило очень долгое время. А на раунд mail.ru я вообще забил, потому что был увлечен ICFPC. В любом случае я бы не полетел в Россию на онсайт :о(

Ферлонам, Хаустовым Павлам и сочувствующим -- можно ниже не читать :о)

Для остальных -- отличная задача.

Дан массив длины 2N. Первые N элементов и последние N элементов отсортированы по возрастанию. Надо отсортировать весь массив за линейное время с константой памяти.

Я предполагаю, что это не классика, потому что существует (неверное) (распространенное) мнение, что лучшая реализация Merge Sort требует O(N) памяти. Сам факт, что описанная выше задача имеет решение, очевидно, опровергает это.

UPD: Ваши решения можно проверить на случаях

6 7 8 9 10 1 2 3 4 5

и

1 3 5 7 9 2 4 6 8 10.

Почти любое наивное решение не способно решить один из них.

Условия: http://contests.snarknews.info/files/snws11/probs/day5.pdf 
Результаты: http://contests.snarknews.info/index.cgi?data=snws11/standing5&menu=index&head=index&mod=snws11&class=snws11 

Задача А.
Сначала заменим все числа на A%mod, так как понятно нас интересует только остаток, затем добавляем сначала все числа с одним остатком, затем с другим итд. Допустим, что сейчас добавляются числа с отстатком m, а до этого уже были добавлены какие-то числа с другими остатками. Поддерживаем динамику d от двух параметров, где d[v][q] = количество последовательностей из уже добавленных чисел таких, что есть ровно v пар чисел с одинаковым остатком, НЕ равным m, стоящих рядом, и q пар чисел с остатком, равным m, стоящих рядом.
Кроме того, двигаясь вправо поддерживаем: n - сколько уже вообще добавлено чисел, и r - сколько уже вообще добавлено чисел с текущим остатком. Теперь, закрепим v и q. У нас есть три опции:
1. Поставить число между двумя одинаковыми числами, не имеющими остаток m. Таких вариантов, очевидно, v, и такое действие уменьшит v
nd[v-1][q] += d[v][q] * v
2. Поставить число между или рядом с числом с остатком m. Это увеличит q. Таких вариантов, если подумать, 2*r-q:
nd[v][q+1] += d[v][q] * (r*2-q)
Наконец, поставить число в любую другую позицию. Это не изменит ни q ни v. Это все оставшиеся варианты, то есть n+1 - v - (r*2-q)
nd[v][q] += d[v][q] * ( n + 1 - v - (r*2-q) ).
Потом, когда остаток от деления меняется, добавляем числа с предыдущим остатком к старым:
nd[v+q][0] += d[v][q];
В конце ответ будет в d[0][0] - потому что не должно быть никаких чисел с равным остатком рядом.

Задача B.
Я занумеровал вершины в порядке выхода из DFS, и вывел их по убыванию этой величины.

Задача C.
Единственное ограничение, данное нам -- это то, что кратность ребер не превышает четырех. В частном слуачае, когда вес всех ребер равен единице, это будет задача на матричную теорему Кирхгофа, которая решается за N^3.
Я упускаю что-то очень важное :о)

Задача F.
Очевидно, сами числа не важны, важна только их длина. Нам надо понять, сколько битов понадобится, чтобы представить число с записью 10^K в системе счисления B. Это, если я правильно помню, равно floor( K*log(B)/log(2)+1 ).

Я расскажу как я решал задачи, которые я сдал.
Мне, в свою очередь, интересно, как решать B :о)

Очень клевый контест для командной работы -- в задачах надо много думать и не очень много кодить. Но все равно поверить, что кто-то на ней сдал девять задач невероятно :о

Результаты с тимуса: http://acm.timus.ru/monitor.aspx?id=83

Результаты с петрозаводска: http://karelia.snarknews.info/index.cgi?data=macros/run&menu=index&head=index&round=01&sbname=2010s&class=2010s

Задача C.
Можно заметить, что окружность вписывается тогда и только тогда, когда произведение радиусов окружностей, между которыми мы ее вставляем, является квадратом рационального числа. Более того, если их радиусы равны A/(B^2) и A/(C^2), то радиус впихнутой окружности будет A/((B+C)^2). То есть если с самого начала можно впихнуть окружность, то можно будет и на каждой следующей итерации, и наоборот. Отсюда, сначала проверим, является ли произведение данных нам радиусов квадратом рационального числа, и, если да, представим радиусы в виде
r1 = (a) / (b)
r2 = (a) / (c)
Где a = r1*r2/gcd(r1,r2). После этого будем на каждой итерации вычислять радиус центрального шарика, и смотреть, с какой стороны относительно центрального шарика нужный нам - и продолжать рекурсивно.
Отдельно надо рассмотреть крайний случай, когда впихнуть шарик нельзя, но запрашивается один из крайних.

Задача G.
Решим по очереди для каждого делителя N, и в конце для N, так, чтобы к моменту, когда мы решаем для некоторого делителя, для всех меньших делителей мы уже знали ответ.
Теперь, чтобы решить для N перебираем все делители N, для каждого делителя смотрим, каков шанс нарваться на этот делитель в интервале [1,10^18], причем так, чтобы при этом не делилось ни на какой больший делитель. Это делается с помощью включения-исключения. Допустим, что мы решаем для числа 12, и хотим узнать, каков шанс нарваться на число, кратное двум, но не кратное четырем или шести. Ответ будет
chance = ( 10^18 / 2 - 10^18 / 4 - 10^18 / 6 + 10^18 / 12 ) / 10^18
Для каждого делителя A прибавляем к ответу ( ans[A] + ans[N / A] ) * chance.
В конце в ответе надо учесть, что, прежде, чем попасть в любой такой делитель, мы сколько-то раз потыкаемся в взаимнопростые числа. Это учитывается как-то так:
ret = ( ret + 1 ) / (allChances);
Где allChances - это сумма всех chance для всех делителей N.

Задача I.
Надо найти N такое, что следующая формула вернет ноль:
- a[n - 1] + (n-1)/n * (- a[n - 2] + (n-1)/n * (- a[n - 3] + (n-1)/n * (...) % n) % n) % n
Восстанавливать надо с конца, получается
ret = 0;
ret += a[n - 1];
ret %= n;
ret *= n
ret /= (n-1)
ret += a[n - 2];
ret %= n^2;
ret *= n;
ret /= (n-1)
...
То есть, тоже самое псевдокодом
for(i from N-1 to 0) {
 ret = (ret + a[i]) % mod;
 if( i == 0 ) break;
 ret *= N;
 mod *= N;
 ret /= (N-1);
}
Тут самое сложное - это сделать это все быстро. Особенно деление по непростому модулю. Так как это длинная арифметика, и решать надо все равно на Java, кажется очевидным попользовать модный modInverse, но такое решение ловит TLE. Я в конце концов пропихнул такое решение:
for(i from N-1 to 0) {
 ret = (ret + a[i] * mul) % (mod_mul);
 if( i == 0 ) break;
 ret *= N;
 mod *= N;
 mul *= (N-1);
 mod_mul *= N*(N-1)
}
ret = ret * mul.modInverse(mod_mul) % mod;

Задача H вроде тривиальная - ДП по подмножествам.
В задаче D строим для первых 100 элементов, и мучительно угадываем закономерность.

На сайте TopCoder.com опубликовали даты и место проведения TopCoder Open 2011

We are excited to announce the 2011 TopCoder Open! The TCO11 will take place September 25 - 28, 2011 at the Westin Diplomat Resort & Spa, Hollywood, Florida, USA. More details about this awesome event to come in March. So if you went to compete, better start practicing now!

(Это не тот Голливуд, где снимают кино. "Тот" Голливуд находится  в другом конце Америки в Los Angeles).

То, что TCO пройдет во Флориде, примечательно, так как последние несколько лет TopCoder Open неизменно проходил в городе развлечений Las Vegas, в отеле Mirage. Удивительно, что место проведения поменяли в этом году.

Несколько слов об отборочных
Отбор проходит каждый раз в несколько этапов (я думаю почти все хотя бы раз пытались отобраться на TCO). Первые несколько раундов для опытных участников обычно являются формальностью -- не проспать, убедиться, что интернет не упадет, написать.
Самое опасное начинается раунда с третьего, где количество проходящих участников уже сравнительно небольшое, а на ТопКодере, как известно, цена ошибки очень велика. Чтобы отобраться на финал мало уметь решать сложные задачи, и мало решать их быстро. Надо на протяжении пяти онлайн раундов ни разу не допустить ошибку. Один пропущенный ноль в константе, int вместо long long, и вы вылетаете.

Как проходит сам онсайт.

В своей жизни я был на нескольких различных соревнованиях. Значительно меньше, чем Петя, или создатель этого сайта, но на приличном количестве, чтобы иметь представление. И с этого ракурса я могу сказать: TopCoder Open -- это то, как чемпионат мира по программированию должен быть проведен.
Во-первых, само место проведения -- это одна большая сказка (это я про Лас-Вегас, но я надеюсь, что во Флориде это не хуже). Вы выходите из отеля, и сразу погружаетесь в невероятную атмосферу. Можно гулять, бухать и веселиться целыми днями, за исключением пары часов на непосредственно тур.
Но даже если вы решите остаться в отведенных под соревнование ballroom'ах, вам не будет там скучно. Все соревнования проводятся очень открыто: зрители ходят прямо между компьютерами участников, и обсуждают на месте. В центре стоят мониторы, которые показывают, что происходит на экранах игроков. Пару лет назад все участники разбивались на несколько полуфинальных групп, и можно было смотреть за другими полуфинальными группами. Сейчас это, вероятно, не так круто, так как участников меньше. Но можно понаблюдать за соревнованиями в других номинациях (что, конечно, поскучнее).
Участники, чтобы не отвлекаться на толпу, сидят в наушниках, или в берушах. Вокруг стоят столы спонсоров, где можно потырить бесплатных прикольных сувениров, поболтать с представителями. Иногда можно найти попкорн, всегда есть энергетики и напитки.

Главное -- нет никаких тупых открытий и закрытий. Все организаторы соревнований, будь то воронежская пародия на олимпиаду или финал ACM ICPC, почему-то считают, что нам очень интересно послушать "какие мы умные, как (оратор) гордится находиться с нами в одной комнате", а также выслушать полный граф поздравлений всех ораторов друг другу. На ТопКодер Open этого говна нет. Есть выступления спонсоров. Но они если и скучные, то авторы могут притянуть ваше внимание. Так, в 2007 и 2008 годах (а может и после этого) компания Eli Lilly после своего представления задавала вопросы по только что рассказанному, и за каждый правильный ответ давала iPod. Казалось бы, как бы скучно не было, слушать надо :о)

Для меня единственный TopCoder Open на котором я был, остался самым незабываемым с точки зрения организации и атмосферы соревнованием, и я бы пожелал каждому из всех вас попасть на него хотя бы раз. Соревнование в сентябре, а сегодня только январь -- поэтому советую последовать совету из новости на topcoder.com и начать усиленно готовиться уже сегодня!

Я уверен, что многие из вас, кто сейчас занимается олимпиадным программированием, попутно занимаются или пытаются заниматься разработкой игр. Я могу с ходу вспомнить упоминания как минимум двух человек об этом хобби, один из которых красный и медалист (если не дважды) ICPC.
Я давно хотел тут написать об одной игре - мы занимались ей с другом, запустили, и она существовала на протяжении двух лет. До этого я так и не написал о ней, потому что не хотел чтобы это сочли как её рекламу, но теперь, когда мы полностью прекратили её поддержку, я думаю я абсолютно чист в желании рассказать о ней.

Я сначала расскажу немного предыстории, затем как мы его разрабатывали, со всеми препятствиями, как мы его запустили, как он развивался, и почему мы его закрыли.

Игра - обычная браузерная ММОРПГ. Посмотреть на нее можно здесь: alideria.ru.

Сначала предыстория. Я раньше играл в игру, назовем ее ИКНН (игра-которую-нельзя-называть), которая собственно послужила прототипом Алидерии. Игра тогда была очень сырая, и я, за компенсацию игровыми ценностями, помогал администраторам переписывать какие-то фрагменты с чистого PHP на PHP+JavaScript, чтобы перенести часть каких-то вещей на клиент, и добавить асинхронности. Я сам тогда был не очень крут как в PHP, так и в JavaScript, и эта работа на самом деле принесла невероятное количество опыта.
В какой-то момент времени оказалось, что я приложил руку почти к каждому аспекту игры на тот момент, и это дало мне понять, что, вероятно, я смогу написать такую игру и сам. Я начал ее писать, и благополучно забил, написав какие-то основы типа регистрации, брождения, боя, инвентаря и магазинов. Это даже было немного играбельно.

Спустя некоторое время мне постучал другой человек, Дима, который тоже помогал разработчикам ИКНН. Только он занимался ей со стороны рисования картинок. Он предложил мне написать вместе игру, а также познакомил с еще одним человеком, тоже Димой, который тоже помогал разработчикам ИКНН, но он, в свою очередь, писал квесты. Я до сих пор его считаю самым талантливым человеком в этой области из всех кого я знаю :о)

Я сразу отрыл исходники игры, которой я занимался, и это послужило как отправная точка. Дима, который рисовал, успел только сделать дизайн (который до сих пор стоит в игре), и ушел из проекта, оставив нас в двоем с Димой, который делает квесты. Он, в свою очередь, согласился проинвестировать часть своих денег в игру (я тогда жил на стипендию и такой возможости не имел), оплатив виртуальный хостинг, и начав заказывать картинки вещей на сайте free-lance.ru. Работа у нас шла очень медленно, в основном потому что я готовился к соревнованиям. Через полтора года у нас был уже рабочий прототип, но все еще не готовый к запуску. В это время у меня начался год, который был посвящен ICPC целиком, а за ним стажировка в Microsoft. Таким образом игра оттянулась еще примерно на год. После стажировки за пять месяцев мы дописали все, что недоставало для запуска, вставили заглушки вместо картинок, которых не хватало, и 16-ого февраля 2009 года мы ее открыли. В качестве первой попытки привлечь аудиторию мы просто кинули ссылку в ИКНН, в игру вошло 20 человек, и виртуальный хостинг накрылся попой. Заказ выделенного сервера пришелся аккурат на праздники в честь 23-его февраля, и поэтому на протяжении первых 10 дней жизни игры она существовала между полностью убитым состоянием, и едва живым :о)
Затем выделенный сервер у нас появился.

Первые проблемы, которые встали после этого:
1. Многие участки кода были очень сырыми. В первые дни работа шла в режиме 10 часов в день, с непрерывным исправлением ошибок, о которых писали в чат. Там же произошла первая отправка запроса вида delete from player_items с забытым where... На протяжении жизни проекта запросов в забытым where, и многочасовых разгребаний их последствий, будет штук 40 :о)
2. Чат, написанный на PHP, нагружает сервер очень сильно. Я не верю вообще в возможность написать на PHP чат, который будет делать адекватную нагрузку. Поэтому сразу пришлось писать новый чат на C++. Это было достаточно сложно, учитывая, что в работе с сетью и потоками под линукс на С++ я был полнейшим нубом. Потом-таки пришлось переписать на Java.

Затем время текло, игроки требовали вещей, которые мы не успели сделать до старта игры. Например - кланов. ММОРПГ без кланов - это не ММОРПГ :о) Систему кланов мы сделали очень крутую, с огромной системой прав доступа, удобным управлением клановыми вещами, и необходимостью всем кланом строить постройки, чтобы получать бонусы. Запускали все это добро в апреле, прямо в мой день рождения. Нет ничего приятнее, чем подарить себе на день рождения релиз клевой штуки. И полный день у компьютера с наблюдением, что все работает. Конечно, в первую секунду упало все, что могло упасть...

Как мы ее раскручивали. Я к моменту запуска уже работал в ИКНН почти официально, и получал кучу бабла - 1000 долларов в месяц за достаточно не большое количество часов. Поэтому деньги на рекламу были. Мы покупали рекламу в Яндексе, Гугле и на ВКонтакте. В тот момент при равных вложениях третья обходила первые две на голову. Потому что тогда контекстная реклама на ВКонтакте вроде как только появилась, и тысяч крутых игр, которые бы ей пользовались, там не было. Сегодня на наш тогдашний бюджет с ВКонтакте наверное даже одного посетителя не получить :о)
Такая реклама позволила медленными темпами развить игру до 200 человек онлайн. И эта цифра никогда не была побита по большому счету. Потому что реклама становилась дороже, а наш бюджет больше не становился. В какой-то момент мы рекламу попросту отключили.

Следующая проблема, которую мы наблюдали - кликов много, но после этого средний игрок уходил через пять минут. Зарегистрировав персонажа в игре и поставив себя на место новичка мы поняли, что в Алидерии вообще невозможно разобраться. В качестве заглушки мы сделали несколько обучающих сообщений, падающих в чат при первом заходе, но это почти не помогло. Тогда мы начали работать над сложными первыми шагами, которые можно наблюдать в игре сегодня.
Если бы эти первые шаги были запланированы сразу, то, скорее всего, их реализация имела бы нулевую стоимость. Но, так как весь код игры уже был написан, и он не был рассчитан на первые шаги, приходилось вставлять ужасные костыли везде, и это заняло тонну времени и усилий.
После запуска первых шагов 30% игроков, регистрирующихся в игре, доходили до второго уровня.

В какой-то момент времени мы стали думать о введении платных сервисов. Проект с самого начала разрабатывался как что-то, что со временем должно приносить прибыль. Легче всего было подключить мерчант веб-мани. У Димы был персональный аттестат, и имея его подключить мерчант - это пять кликов на сайте. Но вы можете догадываться, что WebMoney есть у очень малого процента посетителей игры. По этому, помимо мерчанта сразу же начали сотрудничество с компанией, управляющей коротким номером для СМС-сообщений. Запуск СМС-ок и WebMoney для покупки внутренней валюты, и нескольких премиум-сервисов за эту внутреннюю валюту (вида "в течение месяца вы будете получать x1.5 боевого опыта" за 300 рублей) начал приносить какую-то небольшую прибыль. К этому мы добавили позже 2pay, основная крутость которого - это терминалы (ну и яндекс.деньги), и этих трех способов нам хватало по сей день. За все время жалобы от игроков о невозможности пополнить баланс мы слышали лишь несколько раз, всегда от игроков из ближнего зарубежья, и чаще всего выяснялось, что у нашего СМС-оператора есть короткий номер в этой стране, который мы просто добавляли.

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

Чтобы вы понимали, чего ждать от такого подхода: при 200 игроках онлайн в середине дня, платных сервисах, ограничивающихся премиум-аккаунтами по 150-300 рублей (в среднем игрок, вкладывающий деньги, активировал три разных премиум-аккаунта на месяц), игра приносит порядка 30 тысяч рублей в месяц (до вычета расходов на сервер, новые картинки, рекламу итд).

Для сравнения, в ИКНН, где онлайн 800 человек, и где можно покупать уникальные вещи за реальные деньги, есть по меньшей мере пять человек, чей комплект вещей стоит более 15ти тысяч долларов. Это мне подсказывает, что их прибыль значительно больее чем в четыре раза превышает нашу.

Другие проблемы, с которыми мы сталкивались:
1. Всегда есть бараны, которые взламывают игру. Иногда приходится тратить очень много времени, чтобы разгрести последствия действий этих баранов.
2. Если администрация ведет себя открыто с игроками (не прячется за абстрактным ником Администратор), общается с ними, то игроки ведут себя значительно требовательней, и относятся к администрации как к обязанной немедленно выполнять их требования. Это заметно раздражает :о
3. Игроки ждут апдейтов очень часто. Выпускать их часто очень сложно. В итоге, опять же, недовольства игроков.
4. Вообще, игроки недовольны всегда. Бывали случаи, когда игрок просил какое-то изменение, а когда оно вводилось, в первых рядах кричал, что это изменение погубит игру.
5. Очень сложно сбалансировать игру. В нашем случае никого баланса между стихиями так и не было достигнуто.
6. Фрилансеры имеют свойство пропадать. Очень неприятно, когда очередной комплект вещей ждешь два месяца...
7. Сделать качественную модерацию в игре очень сложно. Все люди в какой-то мере неадекватны, и если их сделать модераторами, это быстро проявляется.

Еще очень важно потратить время на создание админки. Для сравнения - в ИКНН все квесты целиком пишутся кодом. У нас все разговоры, фразы, переходы, требования, пункты в дневнике, и базовые действия вроде "добавить игроку вещей" или "установить игроку триггер 121" делались через интерфейс админки. По большому счету к коду прибегали только когда в квесте надо было либо сделать нестандартную логику (НПЦ появляется только с 2 до 6 дня допустим), либо когда надо было вставить в квест миниигру.
При этом я делал в ИКНН квест, на который я потратил почти неделю чистого времени, и который в Алидерии я бы почти целиком просто вбил в админке.
Аналогично, по ходу управления игрой постойнно приходится добавлять или забирать у игроков вещи, деньги, заклинания, выкидывать их из клана (глава пропал допустим), расформировывать кланы, выкидывать игроков из зависших боев, перекидывать игроков из локации в локацию. Хорошее правило, которому я следовал - если какое-то действие пришлось сделать трижды, надо его добавить в админку.

Игра наша просуществовала на протяжении двух лет. Кода за это время было написано тонна, картинок куплено еще больше. Мы выбрали вариант развития в ширину, а не в глубину, вводя новые квесты, локации, возможности. Тем самым постоянно портя еще сильнее и без того отсутствующий баланс.

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

Я упоминал выше про взломы игры. Конечно, любой взлом игры происходит из-за ошибки программиста. Из самых тупых взломов я помню следующий:
Когда игрок авторизуется в игре, мы ему присваиваем номер сессии, который в сущности просто является случайным числом, возвращенным функцией mt_rand(). Очевидно, код авторизации был написан одним из первых, то есть за три года до открытия игры, даже раньше, и в нем как-то получилась в то время очень странная конструкция
mt_srand(time());
session_id = mt_rand();
Теперь, мы видим, что перед генерацией сессии инициализируется seed, и инициализируется он на основе текущего времени с точностью до секунды. Добавим к этому, что в Алидерии в информации любого игрока можно увидеть как он давно онлайн с точностью до минуты, а в углу главного экрана игры есть часы с текущим временем на сервере. Хакеру было достаточно перебрать всего 120 значений зерна, чтобы подобрать id сессии нужного ему игрока. В роли нужного ему игрока выступил я, с доступом к админке :о)
Важный урок, который я после этого вынес - не надо размещать ссылку на админку прямо в игре :о Так бы может, взломав меня, он бы хотя бы не нашел как до неё добраться. В админке после этого он сделал только одно действие - поставил админские права своему персонажу. И всплыло это только через две недели.

На последок скажу несколько советов из полученного опыта тем, кто сейчас думает в эту сторону.
1. Когда вы начинаете проект, есть большой шанс, что через месяц он вам будет не интересен, и вы будете хотеть написать уже совсем другой проект, а код текущего будете считать грязным и ужасным (хотя навреное у крутанов нет такой проблемы). Разумно, однако, продолжать работать над текущим проектом.
2. Имеет смысл перед началом работы над сложным проектом написать сначала что-то простое на той технологии, которую вы планируете использовать (например, напишите Марблс). Это откроет вам глаза на многие проблемы, о которых вы не догадываетесь.
3. Игроки не любят сложную игру. Если вы сделаете Magic The Gathering Online, и игру, в которой есть только кнопка "Получить +10 опыта", вторая будет популярнее, и принесет больше прибыли. Ботва - хорошее тому доказательство :о)
4. И, конечно, запуск игры стоит денег. Как минимум на содержание сервера и покупку рекламы. Это с предположением, что у вас есть команда, покрывающая все необходимое в игре. Иначе надо еще рассчитывать бюджет на покупку недостающего контента. Прежде чем тратить значительные усилия на разработку, убедитесь, что ваше финансовое положение позволит потом проект запустить.

Внимание! Шестиминутный лимит был убран - у вас есть время до трех ночи по МСК чтобы послать ваши решения, если вы не успели послать сразу, допустили ошибку, или скачали тест, не зная, что о существовании шестиминутного лимита.

1. Что мне делать, когда я открыл dashboard?
Нажать на название задачи слева, и затем НЕ НАЖИМАТЬ на кнопку Download Input. Можно прочитать все задачи, прежде, чем начинать их писать.

2. Я  прочитал вторую задачу и не понял ее, это нормально?
Это нормально. Ненормально наоборот.

3. Откуда мне читать данные и куда мне их писать?
Как и на GCJ, вы отправляете только ваш аутпут. Откуда вы читаете данные и куда пишете - не важно, до тех пор пока вы можете передать выкаченный из интернета файл вашей программе, и загрузить полученный вывод обратно в интернет.

4. Я дописал решение, и я уверен, что оно верное (= я не пытаюсь просто отсортировать строки в третьей задаче). Что дальше?
Дальше надо нажать Download Input. Ваш браузер куда-то скачает файл. Кнопка сделана убого, поэтому лучший вариант нажать по ней правой кнопкой и выбрать Save Target As (Save Link As или как это может еще называться я вашем браузере). С этого момента у вас начнутся шесть минут, причем вероятность, что вы сможете увидеть таймер, очень низка - шесть минут надо держать в голове. Запустите ваш код. Как только ваш аутпут готов, скопируйте его в буфер обмена, вернитесь в окно с HackerCup, и нажмите Submit Answer внизу. Вставьте output, нажмите ОК.
Вы не получите подтверждения о том, получил ли сервер вашу посылку.

5. Я сделал все, как описано выше, но когда таймер закончился, я увидел фразу Time Expired. Это нормально?
Это нормально. Ваше решение учтено.

6. Меня нет в таблице результатов, что мне делать?
Эту проблему сообщают еще N-10 человек. Facebook разбирается.

7. В FAQ сказано, что надо отправлять Source Code. Куда его вставлять?
В этом раунде не надо отправлять Source Code.

8. Если я нажму Download Input в течение шести минут повторно, скачается другой тест?
Нет, ваш тест не меняется между нажатиями Download Input.

Очевидные вещи:
У вас есть ОДНА попытка сдать задачу. Протестируйте ваше решение очень хорошо. Напишите альтернативное решение, чтобы при скачивании инпута проверить на нем мелкие тесты, и убедиться, что они сходятся с вашим основным решением. Шесть минут может оказаться достаточным, чтобы найти и исправить ошибку.

Вступление

ICFPC – это контест, на котором команды в течение трех суток пытаются решить какую-то одну забавную задачу по программированию. Язык программирования, который использует победившая команда, признается лучшим языком программирования года до следующего контеста. Я о соревновании узнал впервые в начале этого года, случайно увидев ссылку на него на википедии со статьи про TopCoder, и очень захотел попытаться в нем принять участие. В тот момент информации о контесте 2010 еще не было, а потом я че-то зафтыкал и забыл. Так бы я его в общем-то и пропустил, если бы мой бывший одногруппник Кирилл не написал мне на Вконтакте, что он собирает команду для участия в нем, и приглашает меня принять участие.

 Я относился к этому скептически, потому что собственно я хотел писать на C#, а ребята собравшиеся в той команде – линуксоины.  Моно все еще нормально .NET 4.0 не поддерживает. Или, по крайней мере, найти такое Моно, не очень легко. Но вариант писать с командой победил просто потому что это казалось более интересным. Про язык пока думать не хотелось. В команде два человека писало на Ruby, и один на С++.

Готовясь к контесту мы завели, как видимо и почти все команды, хранилище кода н github, завели дашборд на EtherPad, настроили Jabber-конференцию (Все-таки в конце концов мне пришлось его завести. Оказалось безболезненно – в миранде он как выяснилось есть по дефолту, без необходимости ставить плагины :о))

Контест по моему времени начинался в пять утра в пятницу. Я встал где-то около семи...

День первый, Пятница

Согласно описаниям прошлогодних контестов в блогах, обычо условие задачи занимает 20 страниц. В этот раз, когда я открыл его, и увидел, что скроллбар сравнительно большой (= документ маленький), я был приятно удивлен. Ну это было преждевременно.

Итак, чтоже от нас хотят. Ссылка: (http://icfpcontest.org/2010/task/) У нас есть машины и топливо. Машина состоит из чемберов, чемберы состоят из двух пайплайнов – верхнего и нижнего. Пайплайн по существу – лист чисел от 0 до 5. Так же каждый чембер является либо основным, либо нет.

Топливо – это от одной до шести квадратных матриц произвольного размера.

Грубо говоря, числа в пайплайне – это номер матрицы. Топливо подходит машине, если для любого чембера умножение любого вектора А на произведение матриц в верхней пайпе всегда вернет вектор, где каждый элемент не меньше, чем в векторе, полученном при умножении вектора А на произведение матриц в нижней пайпе. При этом, если чембер является основным, то первый элемент результирующего вектора для верхней пайпы должен быть строго больше, чем первый элемент для нижней не зависимо от входного вектора. Подразумевается, что все элементы А не отрицательны, а первый элемент положителен. Более того, требуется, чтобы в процессе умножения входного вектора на каждую матрицу слева на право первый элемент никогда не становился нулем.

После прочтения этого это можно сразу забыть на пару дней :о) Потому что дальше начинается самая жопа. И машины и топливо задаются в тернарном формате. Про него известно то, что он тернарный, описывает числа, листы и туплы, и что он может описывать бесконечно большие числа и бесконечно длинные листы. И все :о Ну и еще у вас есть пример машинки, описанной в тернарном формате, но не более того. В этом и есть весь шарм ICFPC и его отличие от соревнований типа SRM или Marathon – вы даже не знаете, ЧТО вам надо решать :о)

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

Ну и фабрику надо выводить в специальном формате, который тоже не описан, но дан пример фабрики, описанной в нем. Также дана последовательность. Скармливание этой последовательности на данную фабрику даст нам некоторую ключевую последовательность. Любое топливо должно начинаться с ключевой последовательности.

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

Многое не понятно? Не беда, мы чуствовали тоже самое :о)

Задача контеста – засылать топливо для существующих машин. Точнее, засылать фабрики, которые его производят. Чем меньше команд кроме вас поставляют топливо для заданной машины, тем больше профита вы будете получать за нее каждые 15 минут. Чем короче фабрика (чем меньше у нее вершин), тем больше вы будете получать профита с нее.

Окей. Задачу прочитали, надо думать :о) Все что у нас есть в начале – это возможность засылать фабрики на сервер и смотреть, какой тернарный аутпут она дает, если на вход ей подана секретная входная последовательность, лежащая на сервере.

Собрав несколько фабрик руками, мы поняли, что без визуального редактора нам не жить. Как написать визуальный редактор, чтобы он запускался и у меня на винде, и у ребят на линухе? Qt мы допустим не знаем. Ок, на ум пришло JavaScript + HTML5 Canvas – Firefox-то есть у всех.

Начинаю писать. Время где-то 9:15 утра. В 10:00 утра на работе митинг. Пытаюсь успеть, но необходимость позавтракать, умыться, и, собственно, дойти до работы, сыграли свою роль.  Я успел буквально только набрать в Bing “html5 canvas tutorial” и по уроку сделать, что клики по канве рисуют гейты, складывая их в массив.

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

После митинга я за час заканчиваю редактор фабрик (да, это оказалось не так просто :о)), и мы начинаем тестировать. Не очень быстро, но становится понятно, что гейт – это функция тернарная функция f(x,y)=>(x,y), и мы постепенно начинаем восстанавливать  эту функцию засылая разные фабрики. Когда функция восстановлена, я прикручиваю к нашему редактору на JavaScript эвалуейтор фабрик, который по последовательности на входе и фабрике генерит ее выход. Получаем “key sequence” – тернарку, которая должна идти в начале любого топлива. Вот это уже было тупо. Редактор на JavaScript было премлемо, но любой код, который может пригодиться потом – это было тупо. В это же время примерно один из участников команды – Бегемот, расшифровывает входную последовательность на сервере, но у него отпадает интернет, и он не успевает ее послать. Я расшифровываю ее тоже мелкой кодякой на С++, и успеваю как раз к моменту, когда он входит в интернет, и мы одновременно почти отправляем ее в Jabber :о)

Теперь задача найти фабрику, которая будет генерить эту последовательность. Вот тут настал тупняк. Ребята ушли уже спать, а я начал думать. Брутфорс писать было лень (и слава богу, потому что в этот момент я не знал, что потом надо будет делать фабрики для производства топлива длиной под тысячу символов, которые бы не брутились). Начал выводить фабрики, которые не зависимо от входа будут делать нужный выход. Научился делать два блока – один возвращает ноль, а затем поданную на вход последовательность, другой – получает на вход последовательность и возвращает ее, увеличенную на один. Первый из шести гейтов, второй – из десяти. Их комбинации, очевидно, могут создать фабрику для любой последовательности. Тока фабрика будет иметь длину, в 20 раз большую длины входной последовательности :о)

Пишу на JavaScript конвертер выходной последовательности в фабрику (ну опять, почему JavaScript???), и засылаю ее на первую машинку. Команда получает 0.014 баллов :о) Я писаюсь кипятком – у нас не ноль :о)

На другие машинки не засылается. Теперь надо думать над тернаркой. Сразу бросается в глаза, что часто встречаются две подряд идущие двойки. Кроме того, почти все машинки начинаются с двух двоек и заканчиваются 10. Казалось бы, 22 – начало листа, 10 – конец. Но не работает. Да и есть машинка, заканчивающася не на 10, а самые простые машинки начинаются не на 22, а на 1.

Проблема еще в том, что префикс, который должен быть в начале каждого топлива, вообще не похож на описание машинок, а ведь по логике он должен быть в том же формате.

До ночи ничего не придумываю, ухожу спать с надеждой, что ребята расшифруют.

День второй, Суббота

Утром тернарный формат еще не был разгадан. И никаких зацепок не было.

В девять утра был первый отборочный на топкодер, и я решил поискать подсказок в чате. Один чувак отозвался на фразу IFCPC, и в диалоге с ним я прозрел. Префикс у топлива не является вообще валидной тернарной строкой, и описание топлива идет после префикса, а не начиная с него! Это даже прямым текстом указано в условии, но че-то я затупил. С этой информацией Бегемот засылает наконец-то топливо на хоть какую-то машину, кроме пустой, просто перебирая текст после конца префикса. Кирилл пишет на Ruby бота, который рассылает это топливо на все тачки, и он подходит на неслабое их количество. Баллы начинают течь рекой! Конечно, не сравнимо с другими командами, которые так долго не тупили.

Следующее прозрение происходит, когда мы понимаем, что если подать валидное топливо (а у нас теперь есть хотя бы одно такое), то можно изучать ошибки парсера машинки. Ошибки были четырех типов: «ожидается 0, 1 или 2, а обнаружен конец», «ожидается 2, а обнаружен конец» и «ожидается 0, 1 или 2, или число здесь должно быть 0 или 1, а обнаружен конец». Третья ошибка выносит мозг. Ожидается 0, 1, 2, 0 или 1? Что это значит? Иногда пишет, что машинка валидна, но что-то с ней не так: нет ни одного мейн чамбера, или топливные баки не соединины (там есть определенное правило по соединению топливных баков). Долго, очень долго, мы втупляем, каждый сам по себе, иногда кидая мысли в джаббер. Копим разные последоавтельности с ошибками, составляем полный список. Спустя пол дня, где-то после обеда уже, я нахожу машинку, которая пишет «не соединен 0 бак сам с собой». Замена на конце нуля на 10 меняет ошибку на «не соединет нулевой с первым». Начинаю перебирать и умудряюсь восстановить формат представления чисел. Awesome. Перебираю еще пол часика и понимаю весь формат. Я не мог поверить своему счастью. Конечно, когда он уже расшифрован, он кажется очень простым :о) И он реально крут. Мы готовы приступить к непосредственно задаче. Прошло всего полтора суток из трех :о)

Сразу пишется на JavaScript (ну твою ж за ногу) парсер машинок из тернарки в JSON и парсер топлива из JSON в тернарку и сразу в фабрику.

Кирилл улучшает скрипт, чтобы тот рассылал больше типов топлива, и уходит спать. Скрипт убивается через 10 минут после этого, когда сервер вернул 503. Не очень Robust :о)

Сначала я решаю руками некоторые простые машинки, где матрица имеет размер 1 на 1 (открыть машинку, подать ее на парсер, подумать, написать JSON топлива, закодить в фабрику, заслать – автоматизацией не пахнет :о)), пока не нахожу машинку 13252. Смотря на нее я понимаю, что некоторые числа в описании топлива в решении могут быть очень большими, знаков по 100. И мое решение на яваскрипте явно не способно их обрабатывать. Приходится переписывать половину кода на Java – потеря времени -  с BigInteger, с осознанием того, насколько изначально было тупо писать все на JavaScript. Теперь весь код, уже готовый, невозможно использовать, потому что JavaScript даже не научишь писать в файл/читать из файла. При этом конвертор в фабрики я не переношу, и автоматизация все еще хромает, так как надо сконвертить машинку в JSON на стринчке, запустить ява-приложение, и опять на страничке сконверить аутпут в фабрику.

После этого я решаю все машинки вида 13252, и на этом получаю сильный старт – такие машинки к тому времени решены 6-7 командами, а значит баллов за них дают неплохо. Обгоняю постепенно в таблице результатов соседние команды, спустя какое-то время мне уже не надо проматывать странцу чтобы найти нас :о)

Далее вырисовывается несколько путей развития:

1.      Улучшить наши фабрики – сделать их покороче, чтобы баллов за них капало побольше

2.      Написать решалки каких-то базовых машинок

3.      Или сделать свои машинки

Я выбрал третий путь, и начал делать машинки, выбирая несколько больших степеней двойки, и рисуя семь чемберов, которые, видимо, можно будет решить только подобрав эти степени двойки. Засылаю одну такую машинку, и ее почти сразу решает пять команд...

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

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

День третий, Воскресенье

С утра мы уже на 14-ом месте с 300К очков, наши машинки уже решило по 5-6 команд не считая нас, и к списку решенных нами машинок добавилось порядка 60 нубских. Мы все еще растем неплохими темпами (не смотря на то, что наши машинки научились решать).

Я ухожу смотреть матч Бразилия – Ивори Коаст, а ребята продолжают улучшать бота и думать. Просмотр матча в баре без выпивки не удался, и вернулся я в состоянии, не пригодном для решения задачки. Однако новости хорошие – Бегемот придумал новый способ генерить фабрики, который позволит делать фабрики в 10 раз короче!

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

В это время я начинаю писать брут для топлива на C# (как хорошо, что в .NET 4.0 есть BigInteger), который перебирает одноингридиентные топлива с кажным элементом от 1 до 10. Парсер написался легко, но попытки найти машинку, которую бы он решал, заканчиваются буквально нахождением двух трех.

При этом копировать аутпут брута на JavaScript страничку, чтобы сконвертировать топливо в фабрику, очень неудобно, и встает необходимость перенести конвертор топливных фабрик на C#. Раз уж надо переносить генератор, решаю сразу писать идею Бегемота. Это занимает ужасное количство времени (вероятно не последнюю роль в этом сыграл побочный эффект матча Бразилия – Ивори Коаст), но в конечном итоге новый конвертор топлива в фабрики, готов.

Затем запрос “C# WebRequest” в Bing и 30 минут учат софтинку грузить список машинок с сервера, грузить машинки, брутить их, конвертить и засылать, и за несколько минут количество решенных нами машинок увеличивается в 1.5 раза! :о)

При этом софтинка перепосылает все уже решенные нами машинки с более короткими фабриками.

Теперь внимание вопрос. Почему я написал брут форс, а не линейное программирование, если даже ребенку очевидно, что это – задача на линейное программирование? Большинство конкуретнов, которые нас потом обошли не очень сильно, разумеется написали ЛП.

Вечером, когда ребята проснулись, возникает печаль. Mono с .NET 4.0 не так-то легко найти. Они оба не могут запустить мою софтинку. Я генерирую у себя на машине все простые топлива, чтобы Кирилл добавил их в свой скрипт. Теперь на новые машины сразу засылается новое топливо. К сожалению, мой C# кодяк в отличие от бота Кирилла, не запоминает решенные машинки, и каждый раз идет по всему списку. Чтобы он как-то все-таки решал свежие машинки, я запускаю его восемь раз с разным стартовым отступом. Оборачиваю пол кода в try-catch, чтобы не повторить подвиг Кирилла с падением через 10 минут. Ухожу спать в полночь, до конца контеста пять часов.

Ночью происходит забавный момент. Во-первых, уже с вечера многие команда, похоже, написали ЛП-солвер, и начали очень быстро расти. И конкуренция в последние часы просто дикая. Нас рвет SnakeTeam, которую Бегемоту было принципиально порвать, и дерет нас за счет... своих машинок! Потому что 1000 решенных простых машин дает порядка 10 баллов за прирост, в то время как 72 своих (72 - лимит), которые решит одна команда кроме вас, дает 30 баллов за прирост! Прогадал я, однако, с засылкой машинок под лимит раньше времени.

Так вот, забавный момент. Была под нами команда SzM – стыдно за МГУ. Бегемот открыл ихнюю машинку, прочитал, и понял, что он знает как ее решать, в тоже время, наши боты пока ее не умеют делать. Он решает ее, и решает все машинки SzM. В итогде, в конце контеста SzM за нами с минимальным отставанием :о) Получается ихние же машинки не дали им нас обойти :о)

В итоге мы на 19-ом месте. Вокруг невероятная концентрация российских команд: над нами TBD, повыше SnakeTeam, под нами Стыдно за МГУ, jabber-ru.

Вот в общем такая история. Основные уроки, которые были вынесены:

1.      Подумай 10 раз на каком языке пишешь.

2.      Не пиши на JavaScript :о)

3.      Внутри команды используйте один язык программирования :о)

 В следующем году обязательно буду писать снова :о Никакие из соревнований, где я участвовал прежде (кроме конечно ICPC 2008 - с этим ничто не сравнится :О)) по накалу страстей даже рядом, по-моему, не стояли :о)