Одна старая академическая конференция, International Conference on Functional Programming, уже больше двадцати лет организует соревнование по программированию своего имени. 1 задание, 72 часа, участвуют команды произвольного размера. На этом ограничения все. Задача может быть любой, решения — тем более.
Вас могут заставить писать ботов для игр или управлять марсоходом. Реализовывать виртуальные машины или разворачивать оригами. Искать кратчайшие маршруты в лабиринтах или разгадывать послания инопланетян. А в этом году мы пропихивали человечков в лямбды и клали песиков в гробы.
Под катом обзор контеста 2021 года и нашего участия в нем. А еще алгоритмы, теории, байки и разбор решений других команд.
Введение: задача и подготовка
В этом году задача была получилась довольно простой для понимания. Организаторы очень постарались: простая и понятная спецификация уместилась на пяти страницах, а на все непонятные вопросы они тут же отвечали в чате.
Задача
- Давайте обсуждать спеку!
- А может сначала прочитаем?
- Да не, давай сразу обсуждать. Читать — это для новичков.
Есть такая телевизионная забава японского происхождения, называется Brain Wall. На отечественном телевидении оно же шло под названием «Стенка на стенку». Суть проста и безумна: вот дыра в стене некоторой хитрой формы, вот человек, изгибающийся в смешные крокозябры. Цель изгибательства — поместиться в эту дыру. Так вот, контест 2021 года предложил нам подойти к этой проблеме алгоритмически.
Наши входные данные — это целочисленные координаты дыры и фигуры. Дыра задается как набор вершин, последовательно связанных между собой, фигура — как набор вершин и набор ребер. Визуально это добро можно представить вот так
Наша цель — изогнуть фигуру так, чтобы она поместилась в дыру. Звучит просто, но есть несколько дополнительных условий:
Единственное, что мы имеем право делать — перемещать вершины. Все связи между ними остаются на месте.
Перемещая вершины, мы не имеем права растягивать или сжимать ребра сильнее, чем на некоторый заданный процент. Допустимая деформация определяется параметром ε, который является частью задачи.
Результат этих манипуляций может выглядеть как-то так:
Однако это решение не оптимально. А показатель оптимальности решения называется дизлайки. Вычисляются они довольно просто: чем ближе к каждой из вершин дыры находится ближайшая вершина фигуры, тем меньше дизлайков получает решение. Иначе говоря, идеальное решение — это такое, где каждой из вершин дыры соответствует одна из вершин фигуры.
Дизлайки — это еще не все. За выполнение каждой задачи мы получаем баллы. Количество баллов, помимо дизлайков, зависит от сложности задачи (что ожидаемо) и лучшего на текущий момент решения (что уже неожиданнее). Формула выглядит так:
Если расшифровывать эту формулу, то во второй скобке описывается зависимость количества баллов от сложности задачи (количество вершин фигуры * количество ребер * количество вершин дыры), а последний член — зависимость от лучшего решения. Остановлюсь на нем чуть подробнее.
Допустим, у вас есть решение на 20 дизлайков. Это очень мало, близко к идеалу — в приблизительных счет дизлайков идет на тысячи. Однако лучшее решение на текущий момент как раз идеальное, с нулем дизлайков. По этой формуле вы получите в 5 раз меньше баллов, чем текущее лучшее решение. Что, очевидно, делает ваше решение достаточно бесполезным. А значит, для задач с существующим решением на 0 дизлайков вы должны найти аналогичное решение, иначе пользы от него будет мало.
Напоследок еще раз перечислю ключевые моменты:
Задача — перемещать вершины фигуры так, чтобы все вершины и ребра оказались внутри дыры.
Есть максимальное возможное растяжение-сжатие ребер, оно индивидуально для каждой задачи, вылезать за него нельзя.
Чем ближе вершины фигуры к вершинам дыры — тем меньше вы получаете дизлайков.
Чтобы принести максимальное количество баллов, ваше решение должно набрать меньше дизлайков, чем лучшее среди всех команд.
Как мы готовились
Во-первых мы выбрали название. Здесь все было единогласно, Team Pegovka с отсылкой к прошлогоднему контесту. На это же имя завели репозиторий и создали организацию. Pegovka Team в этом году собрала аж 11 участников:
Леша Кирпичников;
Паша Егоров;
Иван Дашкевич;
Андрей Костоусов;
Юра Фрейберг;
Игорь Луканин;
Илья Цуп;
Анастасия Ронжина;
Дима Стуков;
Тимофей Белов;
Матвей Казайкин.
Впрочем, состав постоянно менялся — кто-то не мог участвовать все дни, а кто-то помогал дистанционно. В любом случае, команда собралась большая и классная.
Дальше мы подсуетились и организовали себе кластер Kubernetes аж на 400 ядер. Сути задания мы на тот момент еще не знали, но ядра для вычислений лишними никогда не бывают. Для этой инфраструктуры мы заранее написали некоторый код и положили его в репозиторий, чтобы не тратить время на настройку кластера во время контеста.
Инструменты готовы, команда собрана, пора в бой!
Глава первая: алгоритмы и творческий поиск
Обсудив немного задачу и варианты решения, мы взялись за разработку стартового инструментария. А что нам было нужно, кстати?
Основные инструменты — хранилка для решений, автоматический отправитель решений через API, визуализатор (совмещенный с ручной решалкой), а еще доменная модель и базовые математические методы для решения задачи. Плюс нужно было написать простенький код, который выгрузит с сайта организаторов все задачи и сложит их в базу.
Что мы использовали:
C# для всей основной логики.
JS для визуализатора.
MongoDB для хранения решений.
И кластер Kubernetes для вычислений, как упоминалось ранее.
В общем, ничего особенного. Из интересного только MongoDB, но он выглядит достаточно очевидным выбором, когда нужно быстро вносить изменения в структуру данных (а на контесте это часто случается).
Из забавного — нам удалось немного сэкономить время, взяв часть математических методов из решения одного из прошлых контестов, 2016 года. В том году мы разворачивали оригами, восстанавливая максимально простую развертку в рациональных координатах, и используемая математика во многих местах была похожа.
В результате через девять часов у нас уже были все перечисленные выше инструменты (кроме визуального решателя, с ним возникли проблемы) и первая, самая базовая версия алгоритма. Никакой магии, простая оптимизация основанная на поиске восхождением к вершине.
Первым делом для алгоритма потребовались функция оценки. Нам нужно было оценивать:
Насколько хорошо мы сейчас попадаем в дыру;
Насколько сильно деформированы ребра;
Сколько дизлайков набрало текущее решение.
При оценке мы в первую очередь учитывали попадание в дыру, затем деформацию ребер, и только после этого проверяли количество дизлайков.
Далее мы двигали случайные вершины, оценивали результат и отменяли изменения, если ситуация ухудшилась. Если же ситуация улучшалась, то мы продолжали двигаться в том же направлении. Важный момент: функция оценки не просто показывала, улучшился ли результат, но и говорила, насколько он улучшился. Это позволяло понимать, насколько правильно мы движемся и как необходимо скорректировать изменения.
Итого,через девять часов после начала контеста у нас был базовый алгоритм, способный решать самые простые задачки. На сложные его пока не хватало — все же пока он умел только двигать одну вершину — но это была хорошая точка для старта.
К этому моменту в Екатеринбурге уже было три часа ночи. Кто-то уехал спать домой, кто-то прилег на диванчике, а самые упорные остались придумывать улучшения к алгоритму на всю ночь.
Когда я вернулся утром, команда продолжала с энтузиазмом изучать задачи. Помимо осознания грустного смысла 73-ей задачи, мы также поняли, что многие задачи решаются на 0 дизлайков.
Что это значит? Как я говорил выше, количество дизлайков зависит от дистанции между вершинами дыры и ближайших к ним вершин фигуры. Чтобы получить ноль дизлайков, вы должны разместить на каждой из вершин дыры одну из вершин фигуры. И судя по количеству таких решений, находить их вполне реально.
Вооруженные этим знанием, мы написали брутфорсилку для таких решений. Никакого rocket science и хитрых алгоритмов, простой перебор всех возможных решений такого типа. Разумеется, пространство для перебора выходило огромное, но на некоторых задачах с небольшим количеством вершин это сработало.
Одновременно с этим все остальные члены команды продолжали экспериментировать и разрабатывать всяческие улучшения. Леша Кирпичников допиливал загрузчик решений, Игорь Луканин улучшал визуализатор, а все остальные экспериментировали с разнообразными алгоритмами. Илья Цуп, например, занимался мутаторами.
Что еще за мутаторы? Идея простая. Вот смотрите, сейчас наш основной алгоритм на каждом шагу своей работы передвигает какую-то одну точку. У этого есть целая куча проблем. Например, шаг изменений слишком маленький. А еще такие передвижения вершин постоянно растягивают ребра. Поэтому Илья изобретал другие способы изменять фигуру, которые мы называли мутаторами.
Идеи для некоторых из них лежали на поверхности: например, передвижение или поворот всей фигуры целиком не деформировали ребра и позволяли быстро приблизить ее к дыре. Другие были похитрее. Так у нас был специальный мутатор для решения проблем с деформацией, который шевелил группы соседних точек. А еще мы написали два мутатора, позволяющих сильно изменять форму без деформации ребер.
Первый искал у фигуры отдельно торчащие ребра, у которых один из концов не связан ни с одним другим ребром. Как можно понять по гифке, такая отделенность позволяет спокойно вращать эти ребра вокруг одной из вершин. Так мы подгоняли их под форму дыры.
Другой мутатор развил эту идею эту идею и сворачивал целые сектора фигуры. Он искал участки фигуры, которые можно отразить, не влияя на растяжение. Как можно заметить на гифке, такие участки основывались на двух вершинах и идущей от них конструкции, которая связана с остальной фигурой только этими двумя точками. В простейшем варианте это просто отдельная вершина, но частенько встречались и более хитрые конструкции.
Угадайте, почему ребра все же деформировались?
Потому что координаты у нас были целочисленные. Так что какие умные схемы не придумывай — округление беспощадно. В любом случае, таким образом деформации сводились к минимуму.
Со всеми мутаторами находить приблизительные решения стало куда проще. Например, вот так выглядело решение алгоритмом самой первой задачи.
В общем, все шло хорошо. Пусть у нас все еще не получалось находить идеальные решения для больших задач, мы нашли много приблизительных решений, создали хороший базовый инструментарий и совместными усилиями алгоритма и ручной решалки выдавали отличные решения для многих задач.
А потом добавили бонусы.
Глава вторая: бонусы и сломанные ноги
Есть у ICFPC добрая традиция — постоянно усложнять задание. Так, например, в 2020 году мы в своем контесте напрочь перевернули задание, превратив реализацию виртуальной машины в космические бои. В этом году изменения были не такие жесткие, к задаче просто добавили дополнительную фичу — однако нам этого хватило.
Итак, бонусы. В данные каждой из задач добавилось поле bonuses, представляющее собой массив объектов. Поля этого объекта — тип бонуса, координаты и номер связанной задачи.
Координаты это точка в задаче. Разместив на этой точке одну из вершин вашей фигуры, вы упростите связанную задачу. Соответственно, номер связанной задачи говорит, для какой задачи вы получаете бонус, тип бонуса — как именно упрощается задача.
Выглядело это все прикольно, но сильно усложняло нам жизнь. Теперь, помимо простого поиска оптимальных решений, нам нужно было искать:
Оптимальные решения, берущие бонусы;
Оптимальные решения, использующие бонусы.
Отдельного веселья добавляло то, что bonuses — это массив. А значит, каждая задача могла давать больше одного бонуса. То, что на текущий момент ни в одной задаче не было больше одного бонуса, еще ничего не значило. Раз спецификация позволяет, наверняка такие ситуации появятся в будущем.
Итого, общая схема следующая: захватываешь одной из вершин определенную точку — упрощаешь решение другой задачи. Причем не произвольной, а заданной в условии.
Бонусов было два типа: GLOBALIST и BREAK_A_LEG.
GLOBALIST делает максимальную растяжимость глобальной, а не отдельной для каждой линии. Это позволяет очень сильно растянуть/сжать некоторые ребра, пожертвовав растяжимостью других.
BREAK_A_LEG позволяет выбрать одно ребро и сломать его напополам. То есть вы добавляете дополнительную вершину, получая возможность модифицировать выбранное ребро.
И если с Глобалистом все было более-менее понятно, то BREAK_A_LEG порядочно сломал нам мозги.
- Ваня второй раз переписывает стейт, очень удобно (будет)
- Как переписывает? Мы же написали идеальный!
Для начала — совершенно непонятно, как этот бонус использовать. Даже без всяких алгоритмов, просто глядя на задачу — неизвестно, что с этим делать. Наверняка у него есть какое-то клевое применение, наверняка новые задачи (а организаторы периодически добавляли новые задачи) не будут идеально решаться без использования этого бонуса, но…
Но как это алгоритмизировать у нас не было никаких идей.
С нашим основным алгоритмом этот бонус сочетался совсем плохо. На момент начала решения мы не знаем, какое из ребер будет максимально выгодно сломать, а принимать это решение на одном из шагов слишком сложно — сам по себе слом никак не улучшает решение, а оценивать последствия на много шагов вперед наш алгоритм не умел.
Впрочем, это все ожидаемые проблемы, а были и неожиданные. Внезапно оказалось, что наша великолепная, блистательная, восхитительная доменная модель никак не рассчитана на то, что количество ребер может меняться. Как-то не пришла нам эта идея в голову. В результате переписывать пришлось чуть ли не всю доменную модель — параллельно внося разнообразные мелкие улучшения в другие части системы.
В общем, с BREAK_A_LEG все было сложно. А ведь на этом наши проблемы не заканчивались!
Чтобы бонусы использовать — их нужно сначала взять. Чтобы бонус взять — нужно наступить вершиной на определенную точку. А это непростая задача для нашего алгоритма, даже если внести соответствующие решения изменения в функцию оценки. Все-таки оптимизации предназначены для поиска приблизительного решения, а нам нужно не приблизительно попасть в точку, нам нужно оказаться точно на ней.
Как видите, наши проблемы очень сильно упирались в саму суть основного алгоритма — он не мог просчитывать ситуацию на много шагов вперед, а решения вроде «какое из ребер поделить пополам» или «какой из вершин захватывать точку с бонусом» требуют именно такого расчета. В итоге решали мы такие проблемы все тем же перебором — выбирали при запуске алгоритма случайную вершину и закрепляли ее за точкой с бонусом. Получалось найти достойное решение — хорошо, не получалось — убиваем решалку, запускаем заново с другой вершиной. Просто, надежно, малоэффективно.
- У нас какой-то ужасный Time to Market — мы фичу написали пять часов назад, а баллы она начала приносить только сейчас
- Да ладно! Прикинь у продуктов в Контуре был бы такой Time to Market?
А эта фраза прозвучала по поводу нашего неожиданного взлета на двенадцатое место (до этого мы болтались где-то в районе восемнадцатого). Той самой фичей оказалась последняя, самая прокачанная версия нашего базового алгоритма — принципиально не поменявшегося, но изрядно пофикшенного, оптимизированного и обросшего дополнительными мутаторами. А еще ему добавили возможность запуска с фигурой, уже «натянутой» на дыру — без учета максимального растяжения, просто чтобы стартовая позиция была поудобнее для оптимизаций. В результате он взял да и порешал сам целую кучу задач — далеко не идеально, но баллов нам это прибавило.
Пока мы подпиливали алгоритм, разработчики продолжали выкатывать обновления. Обновления принесли новые бонусы — две штуки, WALLHACK и SUPERFLEX. Первый позволял разместить одну вершину и прилегающие к ней ребра за границами фигуры, второй — выбрать одно из ребер (организаторы использовали формулировку up to one, заставляющую вспомнить анекдот про математика и камерный оркестр) и деформировать его сколь угодно сильно. И все эти прекрасные бонусы все еще не особо сочетались с нашим основным алгоритмом.
А еще увеличилось количество бонусов в каждой из задач — сначала до двух, а потом и до трех. Ну то есть теперь у каждой задачи было три точки, каждая из которых давала бонус для некоторой задачи. И пространство перебора увеличилось совсем уж неприлично. Теперь мы могли решить задачу...
Без бонусов;
Взяв первый бонус;
Взяв второй бонус;
Взяв третий бонус;
Взяв второй и третий бонусы;
Взяв все бонусы;
С использованием первого бонуса;
С использованием первого бонуса, взяв второй бонус…
А могли бы просто забить на бонусы, но эту идею мы как-то с порога отвергли. Нам же их дают, а значит — надо использовать! Так что мы до последнего перебирали все возможные варианты решений с бонусами, равно как и варианты взятия этих самых бонусов. А полученные решения сохранялись в базу, но пока не заливались на сервер контеста.
Мы стабильно держались в районе 13-14 места, решения с бонусами понемногу копились, а до конца контеста оставалось 24 часа.
Глава 3: самые умные нейросети и другие хитрости
- Так, тут одно ребро неправильное осталось.
- Может выпилим...?
- Ся.
Пошли последние сутки контеста. Мы понимали, что текущий алгоритм развивать особо некуда и потому отчаянно штурмили. Придумывались идеи разной степени безумности, поспешно доделывались фичи к визуальному решателю, велись долгие дискуссии у доски. Все немного тупили и засыпали, но желание добить уже эту проклятую задачу было сильнее.
Вариантов было много. Генетический алгоритм, алгоритм на базе beam search, поиски идеального решения с помощью триангуляции, думали об использовании SAT solvers — чего только не было, но самым эффективным решателем оказались нейросети.
Естественные, разумеется. Пока одна часть команды штурмила алгоритмы, наши стажеры с ФИИТ решали задания с помощью визуализатора. Концепция максимально простая — берешь найденное восхождением приблизительное решение, загружаешь его в визуализатор и начинаешь последовательно двигать вершины в правильном направлении. Потом снова запускаешь алгоритм. Снова двигаешь вершины. Снова запускаешь алгоритм...
Может звучать просто, но огромное количество вершин и ребер превращало эту задачу в очень тонкую и монотонную. Для понимания масштабов проблемы я покажу вам 93-ю задачу, с которой наш алгоритм без человеческой помощи справиться не мог.
Вот эта прекрасная композиция, например, отняла у команды стажеров целых пять часов. Проблема была не только в трудности задачи — где-то не хватало возможностей визуализатора (их доделывали на лету, причем код новых фич в те самые пять часов скидывался в мессенджере), где-то не вытягивал алгоритм, а где-то происходила мистика с появляющимися из ниоткуда дизлайками.
Полная история превозмоганий
Итак, дыра в виде птички, фигура в виде краба, девяносто третья задача и гарантированно существующее решение на ноль дизлайков. Это значит, что получившаяся фигура должна идеально вписаться в дырку, разместив на каждой вершине дыры по одной вершине фигуры. Это… непросто. Для алгоритмического решателя так и вовсе невозможно.
Поэтому задачей в ручном режиме занялся один из членов нашей команды, Дима. За последние несколько часов он уже справился с несколькими похожими задачами и был полон оптимизма. Задача выглядела грандиозно и обещала много баллов.
⁃ «Как-то туго идет. А давайте запилим отображение оригинальной длины ребра?»
Через час стало понятно, что дело движется идет как-то медленно и хорошо бы немного подтюнить визуализатор. Подтюнили, визуализатор теперь умел отображать не только текущую длину ребра, но и ожидаемую. Новую функцию для визуализатора скидывали в телеге, потому что, ну… Ой, как будто вы никогда не перекидывали код в мессенджерах.
Обновление на лету прошло успешно, но глобально ситуацию не исправило. Поэтому ребята по ходу дела написали еще несколько улучшений для визуализатора. И вот после этого…
И после этого мучения продолжались. Дима все больше мрачнел, визуализатор все больше тормозил, но задача все же двигалась к решению. Часа так через четыре осталось всего несколько неправильно установленных вершин и загадочные 3 дизлайка, непонятно откуда берущиеся. Автоматическая решалка не справлялась, Дима не справлялся, а еще через несколько минут не справился ноутбук и намертво завис.
Всем резко стало грустно. На решение потрачена куча времени, сохранить его не выходит, все зависло, а время работы над задачей потихоньку подкатывало к пяти часам. Придумывались разнообразные варианты спасения ситуации, перезапуска всего на свете, какого-то сохранения решения. Был сделан отчаянный скриншот, по которому можно было попробовать восстановить решение — но это заняло бы кучу времени, а на чертову птицу уже и смотреть не хотелось. Впрочем, пока все эти варианты придумывались, ноутбук таки отвис.
Угроза нового зависания сделала алгоритмический решатель недоступным (память отъедал именно он) и потому началось долгое-долгое двигание вершин. Три дизлайка в какой-то момент превратились в четыре («нам что, уже сервер дизлайк поставил?»), а последние ребра никак не желали встать соответственно требованиям по максимальному растяжению.
Закончилось все благополучно и через полчаса перебора Дима таки добил задачу, потратив на нее больше пяти часов. Ноль дизлайков, оптимальное решение, но чертова птица теперь навечно будет символом боли и страданий.
Пока кто-то штурмил алгоритмы, а кто-то воевал с визуализатором, Леша Кирпичников сделал Дашборд. Вот прям так, с большой буквы. С информацией по всем задачам, логами, програссбаром (заливать решения можно быть раз в пять минут), анимациями и великолепным логотипом Pegokva Solutions. И все это в консоли.
У дашборда есть семь колонок:
Номер задачи;
Лучшее решение по миру;
Лучшее решение наше (без бонусов);
И колонки под решения с каждым из бонусов (GLOBALIST, WALLHACK, SUPERFLEX и BREAK_A_LEG).
Дальше — цвета. Красная цифра в колонке BEST означает, что наше решение хуже. Зеленая — что у нас есть лучшее решение. А желтая цифра это «у нас есть лучшее решение, но только при использовании бонуса». В колонках с бонусами желтым выделяется самое результативное из бонусных решений. Если решения с бонусами хуже текущего — они останутся серыми.
Недолгое залипание в табличку привело к неутешительному выводу — наши решения с бонусами не слишком-то эффективны. В большинстве случаев они дают совсем небольшую выгоду, которая едва ли окупит затраты на взятие этих бонусов. Тем не менее, мы ждали последних часов контеста и копили решения. А параллельно Юра писал код, подсчитывающий потенциальную выгоду от решений с бонусами.
Разумеется, помимо дашбордов, визуализаторов и прочего инструментария мы сделали и несколько прототипов алгоритмов разной степени удачности. Была попытка разработать генетический алгоритм — все еще случайные изменения, но на этот раз у нас было бы сразу несколько веток-мутаций, из которых мы бы эволюционно получали лучшие варианты. С мутациями мы справились, а вот придумать, как выделять из разных вариантов фичи и сливать их в один лучший мы не смогли.
Была попытка сделать поиск решений на ноль дизлайков на базе beam search. Заполняли дерево вариантами размещения сегментов, которые претендовали на идеальное решение, а дальше пытались искать лучшие по некоторой хитрой эвристике. С хитрой эвристикой ничего не вышло и beam search превратился в поиск в ширину.
Впрочем, идея пошла дальше. Основной нашей задачей в этот момент был поиск идеальных решений — приблизительные приносили совсем мало баллов. Мы действовали примерно следующим образом:
Искали границы дыры, которые однозначно совпадали с некоторыми границами фигуры.
Найдя такие участки, мы искали правильные размещения для соседних вершин. Они должны были лечь на одну из вершин фигуры или стать «мостиком» для своего соседа, который ляжет на вершину фигуры.
В этом варианте алгоритма мы рассматривали только самые простые мосты между двумя точками — треугольники. По сути, каждая следующая точка на пути либо ложилась на вершину фигуры, либо размещалась над ней так, чтобы ее сосед мог лечь на вершину фигуры.
Этот алгоритм легко решал первую пачку задач (которые, впрочем, мы и без того решили на ноль), но с самыми сложными и дорогими задачами все было не так радужно — замостить границу удавалось лишь отчасти. И мы бы развивали его дальше, у нас уже были планы по оптимизации поиска и поиску более сложных мостов между вершинами дыры, но к этому моменту контекст закончился.
Интермедия: что делали другие?
Одно из самых интересных занятий после контеста это разбор чужих решений. Люди традиционно делятся своими результатами на Реддите, но в этот году хвастаться все начали в чате и сразу после конца контеста. Ведь в этот раз команды сделали чудовищно красивые визуализаторы.
Например, вот такой UI был у команды Snakes, Monkeys and Two Smoking Lambdas. Чего там только нет: и симуляция физики, и разные алгоритмические упрощения, и прикрученный дашборд с результатами, не говоря уж о красоте и удобстве использования. Наш визуализатор смотрелся куда скромнее.
В первый день большая часть команд занималась именно визуальными решателями и разнообразными усовершенствованиями для них. Какие-то помогали «встряхнуть» фигуру и удобнее разместить вершину (о таких рассказывал в своем блоге Serokell), какие-то упрощали перемещение групп точек, какие-то внедряли частично алгоритмические решения.
Собственно, теперь поговорим про алгоритмические решения. Многие начали с брутфорса идеальных решений — перебора всех возможных совмещений вершин дыры с вершинами фигуры. Например, этим путем пошли ребята из команды Rotten Lambdas (да и у нас был аналогичный алгоритм). Частенько первые решатели даже не проверяли, не выходит ли ребро за границу дыры — написание всей нужной математики занимало много времени, так что подобные ошибки правились руками.
Результат предсказуемый: на простых задачах вроде двенадцатой (на скрине ниже) перебор работал отлично, но чем больше становилось вершин, тем сложнее становилось перебрать все варианты. А количество баллов, напомню, зависело именно от количества вершин.
Дальше команды пошли по двум разным путям: либо начали искать более оптимальные способы подбора идеальных решений, либо двинулись в сторону эвристических алгоритмов. Самыми же лучшими оказались решения, которые смогли объединить оба пути. Из попавшихся мне вариантов больше всего в этом преуспела команда Unagi, многократные чемпионы ICFPC.
Для поиска оптимальных решений они использовали back-tracking search, обрезая заведомо неэффективные ветки по некоторым метрикам. Это сильно похоже на наш последний алгоритма — как мы позже постановили в чате, «это почти наш алгоритм, только мы зачем-то сделали его сложным, а надо было простым». Основа та же — строим дерево из наиболее оптимальных вариантов, ищем по нему.
Как и в нашем случае, найти идеальные решения получалось далеко не для всех задач, и тогда решение передавалось эвристическому алгоритму. Таких у Unagi было два.
Первый использовал Simulated annealing. Он начинал с позиции, переданной искавшим идеальное решение алгоритмом. Общая схема была сильно похожа на наш базовый алгоритм — постоянные случайные перемещения точек с оценкой результата. Однако, в отличие от условного градиентного спуска, stimulated annealing реже попадает в локальные минимумы, что обеспечивало лучшую оптимизацию результата.
Другая эвристика использовала SAT Solver, конвертируя задачу «улучши результат, соблюдая требования задачи» в SAT формулу и постоянно запуская ее с помощью Glucose. На вход этому алгоритму шли задачи, которые уже не мог улучшить stimulated annealing. В результате получалась цепочка из трех алгоритмов, каждый из которых последовательно улучшал решение. Ну и вручную некоторые задачки решали, разумеется.
С этим подходом они смогли занять второе место. А обогнала их команда RGB Team, состоящая из наших соотечественников. И один из членов этой команды, разумеется, Геннадий Короткевич, он же tourist. Как прокомментировали в нашем чатике, «чувак просто выигрывает все, что шевелится». RGB Team пошла своим путем и решала проблемы в основном вручную, но с огромным количеством сложных хелперов. Впрочем, у них нашлось место и для simulated annealing, и для брутфорса простых задач. Не буду подробно на этом останавливаться, о своем решении они рассказали сами в отчете организаторов ICFPC 2021.
Что же до бонусов, то серьезного их использования я практически не нашел. Кое-что было в решении Unagi (но, как я понял, им удалось внедрить только GLOBALIST в свои эвристики), RGB Team же от бонусов отказалась («except for a few cases»). Единственное найденное мной решение, серьезно использовавшее бонусы, было сделано командой Manarimo, получившей за это Judges’ Prize. Они смогли автоматизировать собирание алгоритмов, внедрили GLOBALIST в свой эвристический алгоритм и использовали остальные бонусы в ручном решателе.
Эпилог и выводы
Я укладывал в гроб песика, человечка и какую-то женщину.
Я просто специалист по укладыванию в гробы.
После контеста мы собрались обсудить результаты. В общем зачете мы заняли 23-е место — неплохо, но хотелось бы повыше. Все-таки потенциал у многих наших идей был отличный и мы могли бы набрать куда больше баллов. Что можно было сделать лучше?
Во-первых, в этот раз все было слишком хаотично. Какой-то общий план у нас был только в самом начале, а дальше каждый ковырял собственные идеи, изредка присоединяясь к другим и что-то обсуждая. Никаких общих синхронов и планов у нас толком не было, только хардкор и импровизация.
Это привело к ошибкам планирования. За некоторые идеи мы взялись слишком поздно (например за наш последний алгоритм), а некоторые стоило отбросить сразу. Так, больше всего времени у нас заняла разработка поддержки для бонусов и она же оказалась самым бесполезным, что мы делали. Ради бонусов нам пришлось переписать всю доменную модель и подтюнить каждый из алгоритмов, а по результатам подсчета все решения с бонусами могли бы принести нам дополнительно 3 000 баллов. При общем результате почти в миллион.
А еще большее количество баллов нам мог бы принести фокус на ручном решателе. Многие команды пошли путем использования ручных решателей с ассистом от алгоритмов и именно это стало для них основным источников баллов. Мы же разрабатывали визуальную решалку по остаточному принципу и не делали на ней основной фокус.
Впрочем, как раз это я ошибкой не считаю. Вместо визуализатора мы занимались усовершенствованиями алгоритма, которые тоже приносили нам дополнительные баллы. А еще штурмить бесконечные идеи для алгоритмов и много экспериментировать с ними было попросту весело.
И это, пожалуй, главное. Мы отлично повеселились, поигрались с разными алгоритмами, пошевелили мозгами и сделали много неплохих решений. Ведь ICFPC именно про это — веселый безостановочный мозгоштурм, хаос и эксперименты. Спасибо организаторам и до встречи в следующем году!
