Ры (pbl) wrote,
Ры
pbl

ICFPC '10, или Былинный wobble всех полимеров

Для меня ICFPC уже фактически закончился, потому немного напишу о.

Примечательнее всего вышел контраст с прошлым годом. В две тысячи девятом на момент начала конкурса у меня были только g++, несколько отломанных деталей Универсальной Машины '06 and my fanatical devotion to the Pope. В результате я никакими частями анатомии не блеснул, но закончил с ~1060 очками в середине турнирной таблицы, примерно на сто пятидесятом месте.

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

Всю инфраструктуру я тоже заготовил заранее (см. ранее в бложике), и к старту сидел уже весь такой ready and eager.

В результате - ноль очков и ощущение порядочной потерянности.

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

- - -

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

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

Эн времени пробовал различные простые схемы без особого эффекта, пока не запустил:

0L:
X0R0#X0R:
0L


Это (вроде бы) дало самый первый тривиальный результат: входящую последовательность на живом сервере. Тут я немного задумался о том, что же делать при живом использовании фабрик - последовательность вроде бы повторяется, но не очень понятно, как это подтвердить? Можно писать фабрики так, чтобы для любого конечного результата они не зависели от входящей последовательности, но это будет довольно громоздко. Отложил мысль на потом (на никогда :-) в силу неактуальности.

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

(На самом деле в самых простых экспериментах обнаруживается вот такая фишка у одной из схем с одним гейтом:

0000
xabb
0221


...откуда следует, что не все так просто. Но это я заметил уже позже.)

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

Нарисовав, наконец, полную таблицу, я принялся потрясать ею, как Арагорн сломанным мечом; а еще через эн времени нарисовал на хаскеле эмулятор фабрик и принялся потрясать уже префиксом. Вернее, тем, что я принимал за префикс. Хвала олафу, у меня хватило соображения сравнить результаты эмулятора с серверными.

Они, конечно, не совпадали.

Я опечаленно сел.

Получалось все-таки так, что у гейтов есть какое-то состояние.

Положение в фабрике? Возможно, но не объясняет результаты.

Итерация по модулю три? Или не по модулю три. Вполне вероятно.

Некий остаток от последней операции? Ояебу.

Or any combination thereof. Ояващеебу.

От этих мрачных мыслей я испытал мощный прилив DO NOT WANT и пошел спать в глубокой печали.

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

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

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

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

Ну. М-да.

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

Очень, однако, интересуюсь почитать отчеты тех команд, которые добились результатов. Ну, интересно ж, что там все-таки было внутри. Не говоря уж о, собственно, самой задаче с машинками™.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 16 comments