ICFP Contest 2010: день четвертый
День первый
День второй
День третий
В понедельник проснулся часов в 12. Пошел смотреть, что да как. Очки за ночь поднялись аж до 200 с копейками, и я был где-то в районе 55 места. Народ насабмитил кучу новых машинок. Выкачал новые машинки и скормил скрипту, решать и сабмитить топливо. В принципе уже можно было ничего нового не придумывать, ибо пока придумаешь, реализуешь, уже и финиш, но всё же решил чем-нибудь заняться. Решать матричные неравенства как-то было лениво. Сабмитить свои машины тоже было незачем, т.к. сложные я и сам не умел решать, а простые все остальные умеют, т.е. эффект от сабмита простой машины будет нулевой.
Решил попробовать пооптимизировать фабрики.
Первое, что пришло в голову, что при генерации последней цифры последовательности уже не надо повторять вход, а надо всего лишь выдать нужную цифру. Для генерации одной цифры 0, 1 или 2, блоки имели размер, соответственно, 1, 2 и 1 гейта. Да, а ведь если последняя цифра ноль, то можно вообще ничего не добавлять, а просто пустить вход -- он же и так с нуля начинается.
Кстати! Так вообще, если искомая последовательность заканчивается цифрами, с которых начинается вход, можно этот хвост вообще выкинуть. Отлично! Реализовал обе фишки. Поставил пересабмичиваться все решенные машины с новыми топливами! Сервер жутко тормозил, проходило по 2 машины в минуту. Тем не менее очки продолжали ползти вверх.
Следующим шагом решил попробовать вместо блоков "цифра-повтор входа" попытаться сделать блоки "две цифры-повтор входа" в надежде, что они получатся меньше чем на 6 гейтов. Брутфорс мои надежды не оправдал. Все комбинации из двух цифр генерились только шестью гейтами и никак не меньше...
И тут меня наконец осеняют две гениальные мысли!!! :-) За час до окончания :-(
Первая мысль.
А ведь фабрику из 6 гейтов для 17-тритового ключа удалось подобрать брутфорсом за 10 минут. Фабрики из 5 гейтов вообще перебираются мгновенно. Их всего то 10*10! = 36288000. Т.е. 5-гейтовую фабрику вполне можно быстро подобрать для log3(10*10!) ~= 15 тритовой последовательности! Т.е. вместо того, чтобы генерить цепочку из 3*15=45 гейтов для хвоста, можно запускать брутфорсер на 5 гейтов. Если не нашел, то еще один трит генерим основным алгоритмом и повторяем попытку брута для 14 тритов. И т.д. пока не получится.
Вторая мысль.
А зачем нам нужно, чтобы блоки повторители воспроизводили именно такую же последовательность как была на входе? Не нужно! Можно взять гейт, на левый вход ему пустить задержанный выход предыдущей части схемы (для этого блок лишь надо добавить наверх схемы и дуга к нему на вход будет обратной), на правый вход пустить его же правый выход, а левого выхода снимать результат. Тогда получается, что в момент времени 0 на выходе будет 0, а потом в зависимости от того, что мы хотим дальше получить на выходе, можно однозначно рассчитать вход! Т.е. получается что цифру ноль можно генерировать одним гейтом. С цифрами 1 и 2 чуть посложнее, но их можно генерить двумя гейтами...
С учетом обеих идей средний размер фабрик оценивался в (N-15)*1.66+5 гейтов. Реализовывать эти идеи я не стал -- уже не было смысла. Стало жаль, что бросил думать над фабриками в первый день и побежал реализовывать далеко не самый оптимальный вариант. Ну впрочем, так всегда и бывает.
В итоге финишировал 45-м.
После финиша еще немного подумал и понял, что константу 1.66 можно было еще уменьшить. Ведь например для генерации 0 можно использовать два варианта подключения: X0R0#X0R и 0RX0#X0L. При этом можно выбирать тот вариант, при котором вход тоже будет начинаться на ноль, который генерить проще. Например, если на выходе нужно получить 01..., то у первой фабрики вход должен будет начинаться с нуля! Если же на выходе нужна последовательность 02..., то выгоднее второй вариант подключения. Аналогично для цифр 1 и 2. Т.е. в результате коэффициент уменьшается где-то до 1.33 или даже меньше.
Вообщем это было КРУТО! Огромное спасибо организаторам за интересное задание.
Жаль, что ко мне не смогли присоединиться коллеги, а то, то что я делал три дня, мы бы сделали за день к утру субботы. :-)
Всем спасибо! Скорее бы уже ICFPC 2011!