И вновь, как и в прошлые годы, приближается финал конкурса Яндекс.Алгоритм. В этом году мы ввели новый раунд — марафонский. Он представляет из себя одну оптимизационную задачу без точного решения, которую участникам предлагалось «покрутить» в течение 48 часов. Такой формат похож на решение практических задач больше, чем популярные соревнования по спортивному программированию.

Особенностью большинства практических задач является отсутствие точного решения — или же алгоритмы его нахождения оказываются слишком медленными. Команде и отдельному разработчику нужно сделать хороший прототип решения, который будет внедряться в окончательный алгоритм. Задачи подобного рода давно встречаются в соревнованиях TopCoder, ежегодных соревнованиях Marathon24, Deadline24, Google Hash Code и других. Конкурс длится больше стандартных алгоритмических раундов, так что участники могут в спокойной обстановке и в удобное для себя время реализовать придуманный метод.

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

Мы попросили участников, показавших лучший результат, объяснить, как они его достигли.

Предлагаем и вам попробовать порешать задачу! Тому, кто покажет лучший результат до финала Алгоритма, мы подарим футболку с символикой конкурса. Финал состоится 18 июля. К участию приглашаются и те, кто решал раунд в рамках Алгоритма, и новые участники.

Условие задачи «Разделение страны»

4 6 3
0 0
1 3
3 0
3 5
2 4
2 2

aaabbc
aaabbc
aaabbc
cccccc

Константин Хадаев (Россия, 7 место по итогам раунда)

Сначала найдём какие-нибудь пути от одних источников к другим. Это стандартная задача на потоки. Некоторые участники здесь использовали min-cost max-flow, но в моём решении он не дал никакого прироста, и в последней версии я оставил алгоритм Диница.

Дальше надо как-то раздать все остальные клетки. Это я делал совсем примитивно. Проходимся по всем нераспределённым клеткам, выбираем случайного соседа. Если сосед отдан какому-то сыну, отдаём эту клетку ему же. Иначе оставляем неопределённой. И так итерируемся, пока не раздадим все клетки. Небольшая оптимизация: если три соседа отданы одному и тому же сыну, обязательно отдаём клетку ему.

Конечно, на оба предыдущих шага можно добавить случайности. Перемешать вершины для Диница, итерироваться по клеткам в случайном порядке.

Дальше у нас есть какая-то карта, будем её локально оптимизировать.

Тут у меня есть три случая:

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

Чтобы быстро понимать, что выгоднее делать в случаях 2 и 3, нужно поддерживать площади и периметры всех территорий. Но каждый случай давал довольно заметный прирост.

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

В таком виде решение уже набирает довольно много баллов, но часто скатывается в локальные минимумы. Возможный способ с этим бороться: в случаях 2 и 3, даже если изменение не приносит пользы, всё равно с некоторой вероятностью делать его, причём эта вероятность уменьшается с каждой итерацией. Это изменение увеличило результат почти на 200 баллов.

И про обратную связь:
Не понравилось, что с VK Cup'ом пересекается. Кстати, следующего раунда это тоже касается — он в один день с Russian code cup и Distributed code jam, я три контеста в один день точно не потяну. А задача очень приятная, да.

Eryx (Польша, 2 место по итогам раунда)

Спасибо за отличный конкурс и очень интересную задачу. Работать над ней было сплошным удовольствием. Единственное, что мне не понравилось, — немного непонятное описание генерации тестовых данных («некое случайное распределение» — но какое?). Возможно, стоило добавить «официальный» генератор данных (без начального значения), а нам оставить нетривиальную часть, где нужно «убедиться, что решение существует».

Версию моего решения с комментариями можно найти здесь:
https://www.mimuw.edu.pl/~erykk/yandex/solution.cpp

Я вижу, что часть финальных тестов упала (хотя с публичными тестами всё было нормально). У меня не возникло идеи использовать min-cost max-flow для построения путей. Думаю, если бы я задействовал это в качестве альтернативного подхода, то получил бы корректные ответы на указанных тестах, а возможно и улучшил бы другие результаты.

Илья Корнаков (Швейцария, 6 место по итогам раунда)

Я уже что-то написал в http://codeforces.com/blog/entry/51858?#comment-358766

Задача понравилась, по модулю тормозов Java. Решение устроено следующим образом:

• Сначала min-cost-max-flow ищет пути, соединяющие истоки и стоки.
• Потом пути расширяются жадно, пока поле не будет заполнено. Жадные шаги пробуют добавлять по одной клетке, а также по отрезку столбца/строки к существующей компоненте. Целевая функция — изменение скора / (количество добавленных клеток + 10).
• Полученное решение жадно оптимизируется, перекидывая клетки или отрезки столбцов/строк между компонентами (с той же целевой функцией).
• Описанный процесс запускается много раз, выбирается лучшее решение. В процесс добавлен рандом: рёбра в графе для потока перемешиваются, скоры в жадности умножаются на случайное число от 1 до 1,2.

Больше всего очков принесло переписывание решения с Java на C++ (~+150). Помимо этого, жадные улучшения после того как решение сгенерировалось — видимо, полезная идея. Из нереализованного — пробовать больше изменений в жадности (например, отрезать «углы» — пары сторон) и вместо потока сделать что-нибудь, что лучше приспособлено к целевой метрике (т. к. для потока длинный горизонтальный путь — сильно лучше, чем путь по диагонали с таким же горизонтальным смещением, а с точки зрения целевой метрики — сильно хуже). Ещё была идея попробовать simulated annealing вместо жадности, но на это не осталось времени.

https://habrahabr.ru/post/331482/