Технологии в Контуре

2021-07-10 16:46:24 Пятый мутатор играется с «усиками» фигур. Это торчащие отдельно линии, у которых один из концов не привязан ни к одной из вершин.

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

2021-07-10 16:45:56 Пока команда пытается придумать, что же делать со свалившимися на нее новыми условиями, я еще немного расскажу вам про наш основной алгоритм.

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

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

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

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

А последние два хитрее, о них с примерами. Открыть/Комментировать

2021-07-10 15:48:17 Выглядят обновленные задачи вот так.

Бонусов, кстати, может быть и несколько — по крайней мере, хранятся бонусные точки в массиве. Но случаев, когда в массиве больше одного элемента, я пока не нашел. Открыть/Комментировать

2021-07-10 15:47:44 Breaking News, все резко стало сложнее и страннее!

А все потому что правила несколько обновились. Ладно, новость не такая-то и breaking, добавлять новые условия раз в день это добрая традиция ICFPC.

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

Бонусов сейчас есть два — GLOBALIST и BREAK_A_LEG.

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

Звучит интересно, но что со всем этим делать — загадка. Открыть/Комментировать

2021-07-10 13:12:46 А вот собачка Открыть/Комментировать

2021-07-10 13:12:38 - «А все же заметили, что в 73-ей задаче нужно положить собачку в гроб?»

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

А еще, помимо алгоритма с небольшими итеративными улучшениями, ночью у нас появился отдельный алгоритм для задач с существующим решением на 0 дизлайков. Дизлайки, напоминаю — это штраф к результату, начисляемый за удаленность вершин фигуры от вершин дырки. А если кто-то решил задачу с нулем дизлайков — в этом решении каждой вершине дырки соответствует некоторая вершина фигуры.

На этом алгоритм и играет — он попросту перебирает все подобные варианты, проверяя разные совмещения вершин. Работает медленно, перебирать ему порой нужно жуть как много, но свои результаты приносит. А мы пока думаем над новыми алгоритмическими решениями и двигаем вершины. Открыть/Комментировать

2021-07-10 00:49:38 Впрочем, пока все не слишком хорошо. Движение одной вершины — это слишком мало, количество возможных изменений огромно и частенько просто не считается за сколько-то разумное время.

Так что запустить его и бесконечным потоком решать задачи пока не получается. Теперь вот развлекаемся поисками оптимизаций и способов массово двигать точки, которые приведут нас к правильным результатам. Будем держать вас в курсе! Открыть/Комментировать

2021-07-10 00:48:54 Напоминаю — у нас есть фигура и есть дыра, с которой эту фигуру нужно как можно точнее совместить (не растягивая и не сжимая ее сильнее разрешенного). В целях совмещения мы можем двигать вершины нашей фигуры.

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

Звучит просто, вот только для начала придется ответить на вопрос: а как определить, стало ли лучше? А что если фигура стала ближе к дыре, но слишком сильно растянулась? Или с длиной ребер все поправилось, но наша фигура слишком далеко от вершин дыры и с таким решением мы заработаем слишком много дизлайков?

Для этих целей у нас есть функция оценки. Она учитывает все три критерия: степень деформации, поместилась ли фигура в дырку и сколько дизлайков мы при этом заработали. Важный момент: функция оценки не бинарна. Она не просто отвечает на вопрос «лучше-хуже», но и показывает, насколько именно мы приближаемся к цели. Что позволяет пропорционально управлять изменениями.

Критерии учитываются в следующем порядке: сначала функция оценки смотрит на критерий «помещается ли фигура в дырку», затем на деформацию, и после этого на количество дизлайков. В результате фигура сначала упихивается в рамки дыры (хоть как-нибудь!), затем алгоритм пытается исправить проблемы деформации, и уже после этого приступает к поискам максимально оптимального по дизлайкам решения. Открыть/Комментировать

2021-07-10 00:48:37 Вот вам фото с места событий, а ниже — описание алгоритма. Открыть/Комментировать

2021-07-10 00:48:21 Прошло чуть больше девяти часов с начала контеста. Что там у нас?

А у нас масса гипотез, красивый экран со всеми задачками, доска с расчетами позади экрана, инфраструктура по хранению и загрузке решений, куча полезных математических функций и некоторый иногда работающий алгоритм. И скромное 38-е место в рейтинге. Открыть/Комментировать