Контест начался! Спецификация уже на сайте, разбираемся и обсуждаем
https://icfpcontest2021.github.io
- А может сначала прочитаем?
- Да не, давай сразу обсуждать. Читать — это для новичков
https://icfpcontest2021.github.io
- А может сначала прочитаем?
- Да не, давай сразу обсуждать. Читать — это для новичков
Дыра и фигура представлены как координаты вершин и информация о том, как эти вершины соединены друг с другом. Дыра — это невыпуклый многоугольник без пересечения линий. Фигура же состоит из линий, которые могут соединяться с другими линиями в вершинах.
Итак, наша цель — изменить координаты вершин таким образом, чтобы фигура поместилась в дыру. Например, как на картинке ниже:
Итак, наша цель — изменить координаты вершин таким образом, чтобы фигура поместилась в дыру. Например, как на картинке ниже:
Изменения фигуры ограничиваются следующими условиями:
- Если линии соединялись в оригинальной фигуре, они также должны соединяться и в решении задачи;
- Линии не могут растягиваться или сжиматься произвольным образом. Максимальное допустимое сжатие/растяжение определяется по приложенной в спецификации формуле, использующей расстояние между вершинами и некоторое константное число ε, которое является частью задачи.
Задача считается выполненной, если каждая точка фигуры находится внутри дыры или на ее границах.
- Если линии соединялись в оригинальной фигуре, они также должны соединяться и в решении задачи;
- Линии не могут растягиваться или сжиматься произвольным образом. Максимальное допустимое сжатие/растяжение определяется по приложенной в спецификации формуле, использующей расстояние между вершинами и некоторое константное число ε, которое является частью задачи.
Задача считается выполненной, если каждая точка фигуры находится внутри дыры или на ее границах.
После того, как минимальные требования выполнены, производится подсчет очков за решение. Наибольшее количество очков получает то решение, в котором каждая вершина фигуры находится на минимальном возможном расстоянии от некоторой вершины дыры.
Иначе говоря — фигура должна занять собой максимальную площадь внутри дыры.
Иначе говоря — фигура должна занять собой максимальную площадь внутри дыры.
Что ж, со спецификацией все уже разобрались и работают.
Кто-то пишет доменную модель, кто-то скачивает все доступные задачи, кто-то функции подсчета расстояния между вершинами и проверки пересечений, а кто-то думает, что со всем этим добром делать дальше.
Кто-то пишет доменную модель, кто-то скачивает все доступные задачи, кто-то функции подсчета расстояния между вершинами и проверки пересечений, а кто-то думает, что со всем этим добром делать дальше.
Кстати, у ICFPC есть официальный канал в дискорде. Там можно спросить разработчиков о неочевидных моментах в спецификации, поделиться решением или пожаловаться на болезненные флешбеки.
https://discord.com/invite/7cV9VgMbYb
https://discord.com/invite/7cV9VgMbYb
Прошло чуть больше девяти часов с начала контеста. Что там у нас?
А у нас масса гипотез, красивый экран со всеми задачками, доска с расчетами позади экрана, инфраструктура по хранению и загрузке решений, куча полезных математических функций и некоторый иногда работающий алгоритм. И скромное 38-е место в рейтинге.
А у нас масса гипотез, красивый экран со всеми задачками, доска с расчетами позади экрана, инфраструктура по хранению и загрузке решений, куча полезных математических функций и некоторый иногда работающий алгоритм. И скромное 38-е место в рейтинге.
Вот вам фото с места событий, а ниже — описание алгоритма.
Напоминаю — у нас есть фигура и есть дыра, с которой эту фигуру нужно как можно точнее совместить (не растягивая и не сжимая ее сильнее разрешенного). В целях совмещения мы можем двигать вершины нашей фигуры.
Пусть наш алгоритм слегка подвинет случайную вершину в случайном направлении и проверит — стало ли лучше? Приблизились ли мы к цели? Если ответ положительный, продолжаем в том же духе. Если стало хуже — попробуем как-нибудь иначе.
Звучит просто, вот только для начала придется ответить на вопрос: а как определить, стало ли лучше? А что если фигура стала ближе к дыре, но слишком сильно растянулась? Или с длиной ребер все поправилось, но наша фигура слишком далеко от вершин дыры и с таким решением мы заработаем слишком много дизлайков?
Для этих целей у нас есть функция оценки. Она учитывает все три критерия: степень деформации, поместилась ли фигура в дырку и сколько дизлайков мы при этом заработали. Важный момент: функция оценки не бинарна. Она не просто отвечает на вопрос «лучше-хуже», но и показывает, насколько именно мы приближаемся к цели. Что позволяет пропорционально управлять изменениями.
Критерии учитываются в следующем порядке: сначала функция оценки смотрит на критерий «помещается ли фигура в дырку», затем на деформацию, и после этого на количество дизлайков. В результате фигура сначала упихивается в рамки дыры (хоть как-нибудь!), затем алгоритм пытается исправить проблемы деформации, и уже после этого приступает к поискам максимально оптимального по дизлайкам решения.
Пусть наш алгоритм слегка подвинет случайную вершину в случайном направлении и проверит — стало ли лучше? Приблизились ли мы к цели? Если ответ положительный, продолжаем в том же духе. Если стало хуже — попробуем как-нибудь иначе.
Звучит просто, вот только для начала придется ответить на вопрос: а как определить, стало ли лучше? А что если фигура стала ближе к дыре, но слишком сильно растянулась? Или с длиной ребер все поправилось, но наша фигура слишком далеко от вершин дыры и с таким решением мы заработаем слишком много дизлайков?
Для этих целей у нас есть функция оценки. Она учитывает все три критерия: степень деформации, поместилась ли фигура в дырку и сколько дизлайков мы при этом заработали. Важный момент: функция оценки не бинарна. Она не просто отвечает на вопрос «лучше-хуже», но и показывает, насколько именно мы приближаемся к цели. Что позволяет пропорционально управлять изменениями.
Критерии учитываются в следующем порядке: сначала функция оценки смотрит на критерий «помещается ли фигура в дырку», затем на деформацию, и после этого на количество дизлайков. В результате фигура сначала упихивается в рамки дыры (хоть как-нибудь!), затем алгоритм пытается исправить проблемы деформации, и уже после этого приступает к поискам максимально оптимального по дизлайкам решения.
Впрочем, пока все не слишком хорошо. Движение одной вершины — это слишком мало, количество возможных изменений огромно и частенько просто не считается за сколько-то разумное время.
Так что запустить его и бесконечным потоком решать задачи пока не получается. Теперь вот развлекаемся поисками оптимизаций и способов массово двигать точки, которые приведут нас к правильным результатам. Будем держать вас в курсе!
Так что запустить его и бесконечным потоком решать задачи пока не получается. Теперь вот развлекаемся поисками оптимизаций и способов массово двигать точки, которые приведут нас к правильным результатам. Будем держать вас в курсе!
- «А все же заметили, что в 73-ей задаче нужно положить собачку в гроб?»
Как видите, мы продолжаем разбираться с задачками. Алгоритмических успехов у нас не очень много, зато написали визуальный решатель, позволяющий двигать вершины самостоятельно и всячески подсказывающий, где у нас проблемы. Где-то им дорабатываем алгоритмические решения, но чаще придумываем совсем отдельные.
А еще, помимо алгоритма с небольшими итеративными улучшениями, ночью у нас появился отдельный алгоритм для задач с существующим решением на 0 дизлайков. Дизлайки, напоминаю — это штраф к результату, начисляемый за удаленность вершин фигуры от вершин дырки. А если кто-то решил задачу с нулем дизлайков — в этом решении каждой вершине дырки соответствует некоторая вершина фигуры.
На этом алгоритм и играет — он попросту перебирает все подобные варианты, проверяя разные совмещения вершин. Работает медленно, перебирать ему порой нужно жуть как много, но свои результаты приносит. А мы пока думаем над новыми алгоритмическими решениями и двигаем вершины.
Как видите, мы продолжаем разбираться с задачками. Алгоритмических успехов у нас не очень много, зато написали визуальный решатель, позволяющий двигать вершины самостоятельно и всячески подсказывающий, где у нас проблемы. Где-то им дорабатываем алгоритмические решения, но чаще придумываем совсем отдельные.
А еще, помимо алгоритма с небольшими итеративными улучшениями, ночью у нас появился отдельный алгоритм для задач с существующим решением на 0 дизлайков. Дизлайки, напоминаю — это штраф к результату, начисляемый за удаленность вершин фигуры от вершин дырки. А если кто-то решил задачу с нулем дизлайков — в этом решении каждой вершине дырки соответствует некоторая вершина фигуры.
На этом алгоритм и играет — он попросту перебирает все подобные варианты, проверяя разные совмещения вершин. Работает медленно, перебирать ему порой нужно жуть как много, но свои результаты приносит. А мы пока думаем над новыми алгоритмическими решениями и двигаем вершины.
Breaking News, все резко стало сложнее и страннее!
А все потому что правила несколько обновились. Ладно, новость не такая-то и breaking, добавлять новые условия раз в день это добрая традиция ICFPC.
Обновление принесло нам систему бонусов, которая работает следующим образом:
- К каждому заданию добавляются координаты точки, расположенной внутри дыры.
- Если мы построим решение так, чтобы одна из вершин нашей фигуры располагалась в этой точке — мы разблокируем бонус.
- Бонус упрощает решение другой задачи (какая это будет задача и какой бонус описывается в условии).
Бонусов сейчас есть два — GLOBALIST и BREAK_A_LEG.
Первый делает максимальную растяжимость глобальной, а не отдельной для каждой линии. Это позволяет очень сильно растянуть/сжать некоторые ребра, пожертвовав растяжимостью других.
Второй позволяет выбрать некоторое ребро и сломать его напополам. То есть вы добавляете дополнительную вершину, получая возможность модифицировать выбранное ребро.
Звучит интересно, но что со всем этим делать — загадка.
А все потому что правила несколько обновились. Ладно, новость не такая-то и breaking, добавлять новые условия раз в день это добрая традиция ICFPC.
Обновление принесло нам систему бонусов, которая работает следующим образом:
- К каждому заданию добавляются координаты точки, расположенной внутри дыры.
- Если мы построим решение так, чтобы одна из вершин нашей фигуры располагалась в этой точке — мы разблокируем бонус.
- Бонус упрощает решение другой задачи (какая это будет задача и какой бонус описывается в условии).
Бонусов сейчас есть два — GLOBALIST и BREAK_A_LEG.
Первый делает максимальную растяжимость глобальной, а не отдельной для каждой линии. Это позволяет очень сильно растянуть/сжать некоторые ребра, пожертвовав растяжимостью других.
Второй позволяет выбрать некоторое ребро и сломать его напополам. То есть вы добавляете дополнительную вершину, получая возможность модифицировать выбранное ребро.
Звучит интересно, но что со всем этим делать — загадка.
Пока команда пытается придумать, что же делать со свалившимися на нее новыми условиями, я еще немного расскажу вам про наш основной алгоритм.
Как вы я уже говорил, в основе лежат постоянные изменения фигуры. И изменять фигуру мы можем несколькими способами, для этого у нас есть шесть мутаторов.
С первым вы уже знакомы — он случайным образом двигает точку, оценивая эффективность с помощью функции оценки.
Второй занимается похожими изменениями, но несколько с другой целью — он двигает точки так, чтобы фигура проходила требования по максимальной деформации. А еще он умеет шевелить группы соседних точек.
Третий и четвертый двигают или поворачивают всю фигуру целиком. Таким образом, мы можем улучшить наш результат, нисколько не растягивая и не сжимая фигуру.
А последние два хитрее, о них с примерами.
Как вы я уже говорил, в основе лежат постоянные изменения фигуры. И изменять фигуру мы можем несколькими способами, для этого у нас есть шесть мутаторов.
С первым вы уже знакомы — он случайным образом двигает точку, оценивая эффективность с помощью функции оценки.
Второй занимается похожими изменениями, но несколько с другой целью — он двигает точки так, чтобы фигура проходила требования по максимальной деформации. А еще он умеет шевелить группы соседних точек.
Третий и четвертый двигают или поворачивают всю фигуру целиком. Таким образом, мы можем улучшить наш результат, нисколько не растягивая и не сжимая фигуру.
А последние два хитрее, о них с примерами.
This media is not supported in your browser
VIEW IN TELEGRAM
Пятый мутатор играется с «усиками» фигур. Это торчащие отдельно линии, у которых один из концов не привязан ни к одной из вершин.
Такая отдельность этих линий позволяет нам вращать их отдельно от всей остальной фигуры, подгоняя ее под дыру и укладывая концы этих линий поближе к вершинам.
Такая отдельность этих линий позволяет нам вращать их отдельно от всей остальной фигуры, подгоняя ее под дыру и укладывая концы этих линий поближе к вершинам.