dastapov | Fair Guessing of Bit Vectors, или как я участвовал в ICFPC 2013.

Эпиграф

Нас было 7 человек. У нас было 20 модулей на хаскеле, приватный репозиторий на гитхабе, 6 веток в этом репозитории, ImplicitParams, MagicHash и UndecidableInstances в коде и одна highmem нода на амазоне, а также hangouts для общения, юнит-тесты, просто тесты, google docs для заметок и куча статей про SMT-солверы. Не то что бы мы это все использовали, но на ICFPC ты ищешь в инете всякую дурь и бывает трудно остановиться. Единственное что вызывало у меня опасение - это SMT-солверы. Нет ничего более беспомощного, безответственного и испорченного, чем человек, читающий статьи в ходе контеста. Но я знал, что рано или поздно мы подсядем и на эту дрянь.

Краткое содержание для тех, кому лень читать все

Наша команда называлась "(unmatched", и состояла она из меня, Жени

jkff, Ромы ro-che.info, Вани

_navi_, Саши

sorhed, Макса (которого нет в ЖЖ) и еще одного Саши

wizzard0.

Мы набрали 1301 из 1820 возможных, из них 457 в lightning round, т.е. в первые 24 часа (UPD: и, похоже, заняли там 10 место! Аааааа!). Мы заняли место между 11-м и 25-м, но еще не знаем, какое конкретно.

Мы писали на Haskell и вот наш репозиторий.

Спасибо моим соратникам - вы все молодцы и умницы! Традиционное спасибо моей жене

yulanta за моральную и прочую поддержку :)

А теперь - длинная история про то, как дело было.

Условие задачи

(Сейчас оно лежит на http://icfpc2013.cloudapp.net/, но как знать - вдруг переедет или пропадет, сохраню его тут для потомков)

Нужно угадать задуманную организаторами функцию от одной переменной. Точнее даже не одну, а 1800+ таких функций.

Вот синтаксис простого языка, на котором записываются функции:

 program    P ::= "(" "lambda" "(" id ")" e ")"
 expression e ::= "0" | "1" | id
               | "(" "if0" e e e ")"
               | "(" "fold" e e "(" "lambda" "(" id id ")" e ")" ")"
               | "(" op1 e ")"
               | "(" op2 e e ")"
          op1 ::= "not" | "shl1" | "shr1" | "shr4" | "shr16"
          op2 ::= "and" | "or" | "xor" | "plus" 
          id  ::= [a-z][a-z_0-9]*

Вот несколько примеров таких функций:

(lambda (x) (shr4 (not x)))

(lambda (x) (shr1 (or x (not (shr4 x)))))

(lambda (x)
 (if0
  (and (xor 1 (plus (shr1 (shr16 x)) x)) 1)
  (xor x_15 (plus x x))
  (xor x_15 (shr4 (not x)))))

(lambda (x) (fold (shr4 x) 1 (lambda (foldElem foldAcc) (if0 foldElem foldAcc foldElem))))

Как видите, из констант есть только 0 и 1, а из хитрых операций - только fold (причем он в программе может быть только один).

Тип всех значений и выражений - беззнаковое 64-битное слово. Семантика всех операций тоже более-менее привычная, not, and, or - побитовые, а не булевские, сдвиги - без переноса, сложная семантика только у fold:

Given P = (lambda (x) (fold x 0 (lambda (y z) (or y z)))), 

   P(0x1122334455667788) 

   reduces to 

   (or 0x0000000000000011 
   (or 0x0000000000000022 
   (or 0x0000000000000033 
   (or 0x0000000000000044 
   (or 0x0000000000000055 
   (or 0x0000000000000066 
   (or 0x0000000000000077 
   (or 0x0000000000000088 
       0x0000000000000000))))))))

Организаторы предоставляют "черный ящик" (сервер, общающийся по HTTP/JSON), который содержит в себе ~1500 подобных уникальных функций для каждой команды.

Чтобы различать эти функции, у каждой из них есть ID, кроме того, про каждую функцию известно, из каких операций (но не констант!) она составлена и какого она размера. Размер считается просто:

                             |0| = 1
                             |1| = 1
                             |x| = 1
                |(if0 e0 e1 e2)| = 1 + |e0| + |e1| + |e2|
|(fold e0 e1 (lambda (x y) e2))| = 2 + |e0| + |e1| + |e2|
                      |(op1 e0)| = 1 + |e0|
                   |(op2 e0 e1)| = 1 + |e0| + |e1|
                |(lambda (x) e)| = 1 + |e|

То есть, полностью информация об одной загаданной функции выглядит как-то так:

  {
    "operators": [
      "if0",
      "shr16",
      "shr4",
      "tfold",
      "xor"
    ],
    "size": 15,
    "id": "06E6XMGjIr0YUCl5JvbxrqeJ"
  }

Нужно угадать эти функции, задавая черному ящику вопросы.

Вопросы бывают всего двух видов:
* "какие значения принимает функция вот на этих аргументах? (до 256 штук за раз)" -- в ответ сервер вернет вам до 256 значений-результатов
* "не вот эта ли функция загадана под ID таким-то?" -- на что сервер может сказать "угадал!" или "не угадал, на аргументе таком-то твоя функция возвращаем N, а моя - M!"

Если вдруг вам такая задача показалась неожиданно простой, то специально для вас организаторы придумали несколько ограничений:
* Сервер не любит, если к нему обращаются очень часто - можно делать 5 запросов в 20 секунд
* Как только вы задали любой вопрос про конкретную функцию, начинает тикать таймер, и теперь у вас есть пять минут, чтобы ее угадать. Угадали - получили балл, не угадали - не получили ничего, и функция считается "потраченной", больше ее угадывать не выйдет.

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

Дальше все просто: все наперегонки отгадывают функции, кто отгадал больше всех (и соответственно набрал больше всех баллов) - тот и победил.

Ничто не предвещало беды

Начало ICFPC я запланированно ... проспал, т.к. оно пришлось на три часа ночи в моей временной зоне :) Но - ура! - в нашей команде были люди из силиконовой долины, которые тут же накинулись на условие и стали его Думать.

Из чата:

xxx: алё 
yyy: Звонить нечем ) 
xxx: ну блин. А остальные где? 
zzz: Я звонить не могу, жена спит. Давайте пока в доксе.   
xxx: ок

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

Знал ли этот генератор, что ему суждено стать основой всего нашего решения? Наверняка не знал. Он был маленький, но с большим потенциалом :) Хоть в нем было от силы двести строк, он уже умел генерировать максимум один фолд, следить за областями видимости (не генерировать ссылки на fold-переменные снаружи фолда и наоборот) и не вылазить за указанный размер.

Посколько я еще не до конца проснулся, и не осознал задачу, я решил не путаться под ногами, а сделать что-то мелкое и полезное. Например, можно в этом году ради разнообразия сделать так, чтобы мы общались с сервером организаторов не на пестрой смеси шелл-скриптов и коммандлайновых утилит, а через красивое Haskell API. Как оказалось, благодаря Ване у нас уже были Haskell-типы для всех возможных запросов к серверу и ответов от них, и серализатор в и из JSON, и я написал command-line клиент для общения с сервером. В дальнейшем весь код, который мы писали, можно было дергать с командной строки при помощи этого бинарника, и это оказалось очень классной идеей - на каком-то из прошлых icfpc у нас было штук пять разных бинарников и с десяток скриптов, связывающих их воедино, и это было очень сложно и запутано.

Тут я наконец проснулся и перечитал все, что написали организаторы и мои коллеги. Выяснилось, что ограничение на количество запросов к серверу таки энфорсится, что задачи довольно равномерно распределены по размерам, но неравномерно по набору операций - например, есть целых 460 задач, у которых есть fold на верхнем уровне (tfold), и только 222 из одной арифметики.

А еще выяснилось, что не будет живой таблицы результатов :(

Из чата:

xxx: Блин, опять год без лидерборда. 
     Долбаные академики не понимают, что такое компетишн.

Тут я с горя полез экспериментировать с сервером и вместо тренировочной задачи зачем-то попытался решить одну из "продакшена" и завалил ее. Так мы лишились одного очка (почему это важно, станет ясно позднее).

Как решать поставленную задачу для функций больших размеров было пока непонятно. В чате уже (не прошло и шести часов!) муссировались идеи про SAT-словеры и bit blasting, а также параллели с вычислением эквивалентности булевых функций через (O)BDD.

В конце концов победил такой подход:
1)Something has to be done
2)Brute-force is something
3)Therefore, brute-force has to be done

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

Тут все "американцы" нашей команды засыпают, просыпается ~~Мафия~~ Европа, и мы начинаем делать брут-форс. Через небольшое время у нас был маленький и гордый брутфорсер, который засылал на сервер 256 чисел (мы сгенерировали их рандомом и тупо записали в исходнике, чтобы всегда использовать одни и те же), получал от сервера ответ и пробовал тупым перебором найти функцию, выдающую такие же результаты на этих входных данных.

Тут мы спохватились, что наш брутфорсер перебирает вообще все функции, а не только те, которые состоят из указанных в задаче компонентов. А еще организаторы на услужливо говорят, в каких задачах fold бывает где-то внутри, а в каких - только самым верхним выражением. А в функциях, у которых fold снаружи, аргумент функции сразу получается shadowed и внутри фолда не виден, и это надо учесть. А еще ...

Короче, к T+13 у нас уже много чего было, но еще ничего не работало. Где-то к T+16 мы наконец-то убрали все косяки, и у нас получился брутфорсер, решающий все задачи размером до 13 включительно.

А можно ли больше? Наверняка же можно. А насколько больше, чтобы гарантированно не вылететь за пять минут? Из уже имеющегося кода была сделана функция, которая перебирает все задачи размером до 16, пробует сгенерировать для них все возможные выражения, и если генерация укладывается в указанные временые рамки - считает задачу "решаемой. Установив тайм-аут в 10 секунд, мы быстро прошерстили имеющиеся задачи и поняли, что штук 350 мы можем решить аж бегом.

Мы сгенерировали список ID этих задач, запустили скрипт, который их решает, а сами стали оптимизировать наш генератор функций. Очень быстро и очень несложно он был ускорен где-то три раза, после чего мы принялись генерировать "вторую порцию" задач, которые можно решить за вменяемое время.

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

К этому моменту у нас уже был 361 балл. Мы запустили эту новую решалку в три потока ... и она сожрала всю память, сколько дали. Держать весь сгенерированный список в памяти было не самой светлой идеей :) Примерно в это же время кто-то тиснул в твиттер вот эту картинку, на которой видно решение, использующее 172 Гб памяти(!). У нас столько не было, и мы "урезали осетра".

Сложность задач была ограничена размером в 14, список выражений не держался в памяти, а тут же выбрасывался - то есть мы сначала проверяли, что успеем сделать полный перебор за пять минут или меньше, а потом собственно делали этот перебор по-настоящему.

Три или четыре копии этой программы крутились до окончания lightning round, и "накосили" нам 457 очков.

Сразу после окончания первых суток организаторы опубликовали примерное содержание турнирной таблицы: сколько баллов надо иметь прямо сейчас для попадания в десятку, 25 и 50 первых мест соответственно. К моей радости выходило, что мы попали в top 50.

Тут я отправился спать, а Силиконовая Долина принялась ускорять и улучшать наше решение.

Быстрее, выше, сильнее

Утром второго дня я нашел в истории командного чата много интересных сообщений:
Кроме того в логах остался следующий страшный сценарий:

xxx: тут Женя придумал страшную штуку кстати, до которой могли
     додуматься организаторы 

Штука такая: 
участник присылает запрос с начальными векторами 
они строят какую-то функцию простейшую, выдают на ней значения 
участник подбирает новую функцию
посылает организаторам 

те пытаются сгенерировать новую функцию, так чтобы на старых совпадало,
но на каком-то другом входе — нет 

выдают как контр-пример 

и так до тех пор, пока размер сгенерированной функции не достигнет заявленного   

ну или до тех пор, пока не наступит таймаут какой-то 

так чтоб она старалась как можно дольше продлить угадывание   

yyy: ну они разве что могут if-ы какие-то добавить... 
     совпадение на случайных 256*64 битах — это тебе не шутка 

xxx: ну может у них своё секретное кунг-фу :)

Но как мы все знаем, до таких ужасов дело не дошло :)

Когда Америка уже засыпала, а Европа еще толком не проснулась, обсуждались альтернативные идеи: кешировать результаты вычисления всех возможных мелких программ на каких-то фиксированных входах, сделать подобие rainbow tables из всех возможных мелких функций на одном фиксированном значении аргумента и результатов применения к ним всех возможных операций и еще несколько, которые я не могу толком восстановить по логам, т.к. в обсуждении не участвовал.

Венчало историю такое сообщение:

Памятка потомкам: 
Мы ничего не меняли в общей структуре программы, 
только делали чтоб все быстрее работало. 

В результате мы стабильно решаем тренировочные задачи
размера 25 и меньше. 

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

Мы раздумывали про идею с протаскиванием битмасок, но пришли к выводу,
что ничего не понятно, т.к. не понятно, как протаскивать битмаску
внутрь Plus или Fold, а если ее не протаскивать, то внутри
все равно будет полный перебор 

Т.е. может это нас и устраивает, но мы занимались lower hanging fruit. 

Про SMT и т.п. даже не думали. 

Также ВНИМАНИЕ: Давайте пока никакие программы больше не сабмитить
до воскресенья. Спешить уже некуда, а качество будет только улучшаться. 

Да! Ещё возможный low-hanging fruit: попробуйте параллелизовать перебор 

мы ушли

Пока я спал, код генератора выражений и их вычислятеля был ускорен, а в генератор была добавлено отсечение тривиально упрощаемых выражений вроде (and 0 x), (xor 0 x), (xor x x), (if 0 ...), (if constant ...) и так далее. Кроме того, во всех выражениях вида (and x y) мы отсекали ветки, в которых размер первого аргумента был больше размера второго (т.к. мы сгенерируем оба варианта в процессе перебора, а результаты вычисления у них будут одинаковы).

В результате пространство перебора сократилось, скорость перебора увеличилась и мы взяли новые вершины :) Попутно обнаружилось, что большинство тренировочных задач мы решаем при помощи ответом гораздо меньшего рзмера - задачи с размером 25-27 стабильно решались выражениями размером 5-12.

Так как я был соня, Рома в этот момент уже вовсю писал параллельный генератор, а Саша

sorhed пробовал добится любви от SMT-солверов.

После короткого обсуждения я сел писать очередную ручную оптимизацию генератора: в каждом сгенерированном выражении мы будем хранить результат его вычисления на неком фиксированном значении аргумента (назовем его seed). В качестве seed было выбрано первое фиксированное число, которое мы посылаем на сервер в запросе eval. При составлении более сложных выражений из более простых мы будем сразу получать результат вычисления сложного выражения из результатов простых.

Таким образом мы сможем ускорить отфильтровывание ненужных сгенерированных выражений - как только мы получили ответ на eval от сервера, мы тут же узнаем значение угадываемой функции на аргументе seed, и можем выбрать из сгенерированного списка только те, которые дают на seed такой же результат.

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

Из чата:

xxx: запушь свой фикс? 
yyy: какой же он фикс, у меня test suite виснет 
xxx: а это я в testsuite глубину генерируемых выражений поднял до 12. Возможно это было зря :)
yyy: аааааа! уменьши обратно до 8-и :)

Новый генератор был очень быстр, но почему-то генерировал намного меньше выражений, чем мы ожидали. Планировалась, что генерация станет быстрее, но количество выражений останется тем же. Но Что-то Пошло Не Так(tm).

Битый час мы крутили новый генератор и так и эдак. Из чата:

xxx:
*Gen> isSimple $ expr (or_ mainArg one)
False 
А должно быть True 
Найди ошибку в 4 строчках 

yyy: бляяяяя! 

xxx: я тоже вижу! 

yyy: ... || a >= b = False 

xxx: п@@#@ц! 

yyy: оно использует instance of Ord 
но не тот 

xxx: ага, вижу 
напиши кастомный инстанс, чтобы игнорировал cached value

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

За всеми этими интересными событиями время пролетело, Америка уже проснулась, а я так и не дал Роме поработать над параллелизатором.

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

Так как в генераторе уже был набор правил вида (это глупое выражение, такое генерировать не надо), я взялся этот набор расширять, и меня никто не остановил :) (как оказалось впоследствии - зря).

Дальше, как я помню, мы до конца дня наперебой все улучшали и ускоряли.

Из чата:

xxx: чуваки, я такой хак сделал! если сработает, буду век гордиться 
     еще не пушил 
yyy: Рассказывай! 
xxx: если не сработает, не расскажу, чтоб не позориться!

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

Стало понятно, что мы близимся к тому, чтобы снова начать решать задачи "в продакшн". В честь этого был взят инстанс на амазоне с 8 ядрами и 60 гб памяти.

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

Параллельный генератор находился в состоянии "вот-вот и заработает".

Организаторы сказали, что 11-50 место имеют от 550 до 300 баллов соответственно - то есть мы по-прежнему в top 50! Правда, мы подозревали что многие придерживаются той же стратегии, что и мы - улучшать свое решение до самого последнего, и начинать засылать решения непосредственно перед концом соревнования.

Из Более Другого Чата:

Да вы все тут молодцы, я смотрю.

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

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

Казалось, что с обычными задачами у нас уже все более-менее ок, и мы начали бросать первые несмелые взгляды на бонусные задачи и заметили, что все они имеют вид (if (and 1 a) b c).

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

Финальный рывок

Пока Европа спала, вся Америка собралась вместе, и поэтому ночной лог чата был удивительно пуст :)

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

Было еще некоторое количество идей, которые не "выстрелили", и нам про них даже не рассказали :)

И тут в чате появилось такое сообщение:

xxx: есть ощущение, что у нас есть баги с оптимизацией...
     Я зафайлю багу 
     У меня голова не варит - Дима, попробуй плз разобраться с ней?

И Америка пошла спать. Рома стал добивать параллельный солвер, а я пошел смотреть на багу. Чтобы постараться набрать больше кейсов для тестирования я запустил в терминале цикл "получить тестовую задачу размера 12 и попробовать ее решить", и он совершенно неожиданно свалился с диагностикой "все пространство перебора исчерпано, решение не найдено". И так несколько раз подряд. Караул! Я запускаю цикл заново, и он снова падает... Собрав с десяток таких багов, я принялся их изживать, и понял, что всему виной правила отсечения тривиальных выражений, которые я добавлял вчера.

Мне стал помогать Макс и в конце концов пришлось убрать 80 процентов того, что я добавил вчера, чтобы закрыть все найденные баги :( Кроме того, совершенно случайно нашлось пару багов в коде, который мы еще не успели обвешать тестами. Результат радовал глаз, но обидно было то, что на это ушло неприлично много времени.

Как только баги были починены, мы тут же запустили решалку на амазоновской ноде. Было ощущение, что решалка сможет решить все до размера в 20-21 совершенно не напрягаясь (менее чем за 10-15 секунд), что и было вменено ей в задание.

Я в это время пытался что-то сделать с бонусными задачами, а Рома по-прежнему пытался "уговорить" распараллеленый генератор.

Сначала я пытался генерировать для бонусных задач решения в виде (if (and 1 a) b c), где a,b,c будут подвыражениями примерно одинакового размера (так как именно такую форму имели все тренировочные "бонусные" задачи). Генератор был написан и даже работал, но решений ни для одной тренировочной задачи найти не мог :(

Потом я сделал простейшую форму "ограничения допустимого значения". После выполнения первого запроса eval мы знаем, какое значение загаданная функция принимает на выбранном нами значении seed. Можно передать это значение в генератор и сделать так, чтобы он, насколько возможно, генерировал только выражения, дающие именно такой результат на значении seed. Там, где у нас симметричные или обратимые функции типа not, xor, plus, мы можем, зная один аргумент, вычислить ограничение на значение второго. Там же, где мы не можем это сделать, мы перебираем варианты так, как и раньше.

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

Из чата:

xxx: Я оцениваю итоговые шансы как top40.

В этот момент силы покинули меня :) Я передал ветку в репозитории со спец-кодом для решения бонусных задач на попечение Америки, а сам стал следить за амазоновской нодой с солвером, которая к тому моменту "накосила" где-то 750 очков.

Из чата:

xxx: client: guess error: Unable to decide equality 
     вот мы на это и наступили   
yyy: Это потому, что у нас в исходниках {-# LANGUAGE UndeciableEquality #-}

Героичискими усилиями Америки была добавлена еще одна оптимизация - анализ четности требуемого выражения для бонусных задач, т.к. к тому моменту мы уже начали ВНЕЗАПНО осознавать, что (if (and 1 a) b c) будет выдавать в качестве результата b или c в зависимости от четности "a". Забегая наперед скажу, что сделать финальный шаг, который, похоже, сделали все остальные команды, мы не смогли - у нас не появилось идеи _подбирать_ пару выражений b и c, в которых либо b, либо c дает нужный результат, а потом подбирать для них a такое, которе дает нужное чередование четности.

Процесс добавления всех специальных случаев для обработки бонусов сказался на количестве кода. Если раньше часть генератора, порождающая "if0" выглядела так, то в конце она стала выглядеть вот так.

В конце-концов после всех оптимизаций мы со скрипом стали решать хотя бы часть бонусных задач, и запустили 8 копий решалки обрабатывать все подряд.

Со скрипом и стоном, постоянно натыкаясь на таймауты, мы за 30 секунд до окончания соревнования переползли-таки через отметку в 1300 и получили на момент окончания соревнования 1301 бал :)

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

{"contestScore":1298, ... ,"numRequests":8553}
{"contestScore":1301, ... ,"numRequests":8822}

Тут организаторы написали, что

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.

И мы узнали, что попали в top 25. До сих пор мое лучшее место (в составе комадны) было 18-м. Посмотрим, что окончательно получится в этом году :)

Выводы

Команда собралась что надо.

Задание могло быть и лучше, но у меня не осталось впечатления, что тут все решали мегагерцы и гигабайты.

Я получил удовольствие, но ICFPC 2006 по-прежнему непревзойден.

PS
Так а почему же было важно одно очко? А потому, что я точно знаю, что есть команда, набравшая 1303 очка. Так что если бы не это "страченное" мной очко, глядишь, у нас было бы 1302, а там может и с 1303 подвезло бы. И были бы мы на одно место выше.

PPS
Про старые ICFPC у меня в журнале есть целая куча записей.

Flat | Top-Level Comments Only

From:

sorhed.livejournal.com

Эпиграф прекрасен! ;) Отчёт тоже замечательный.

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

From:

komarov.livejournal.com

Потрясно... пожалуй, сорхед имеет право быть таким снобом, какой он есть))

From:

sorhed.livejournal.com

А где я сноб-то? И я на хаскеле не программировал, а решал оргвопросы. :)

Я знаю Haskell, OCaml, GSM, эндофункторы и много других страшных слов

Эпиграф

Краткое содержание для тех, кому лень читать все

Условие задачи

Ничто не предвещало беды

Быстрее, выше, сильнее

Финальный рывок

Выводы

Page Summary

Style Credit

Expand Cut Tags