И вновь, как и в прошлые годы, приближается финал конкурса Яндекс.Алгоритм. В этом году мы ввели новый раунд — марафонский. Он представляет из себя одну оптимизационную задачу без точного решения, которую участникам предлагалось «покрутить» в течение 48 часов. Такой формат похож на решение практических задач больше, чем популярные соревнования по спортивному программированию.
Особенностью большинства практических задач является отсутствие точного решения — или же алгоритмы его нахождения оказываются слишком медленными. Команде и отдельному разработчику нужно сделать хороший прототип решения, который будет внедряться в окончательный алгоритм. Задачи подобного рода давно встречаются в соревнованиях TopCoder, ежегодных соревнованиях Marathon24, Deadline24, Google Hash Code и других. Конкурс длится больше стандартных алгоритмических раундов, так что участники могут в спокойной обстановке и в удобное для себя время реализовать придуманный метод.
Мы, организаторы Алгоритма, очень хотим, чтобы разноплановые участники могли успешно себя проявить. Поэтому добавление марафонского раунда рассматриваем как путь к расширению аудитории и популяризации таких соревнований.
Мы попросили участников, показавших лучший результат, объяснить, как они его достигли.
Предлагаем и вам попробовать порешать задачу! Тому, кто покажет лучший результат до финала Алгоритма, мы подарим футболку с символикой конкурса. Финал состоится 18 июля. К участию приглашаются и те, кто решал раунд в рамках Алгоритма, и новые участники.
Условие задачи «Разделение страны»
| Ограничение времени: | Ограничение памяти: | Ввод: | Вывод: |
|---|---|---|---|
| 2 с | 256 МБ | стандартный ввод | стандартный вывод |
В одной эльфийской стране назрел раскол. Как это часто бывает, после смерти короля его сыновья долго не могли решить, кто из них будет править страной, и в итоге не придумали ничего лучше, чем разделить её на отдельные области.
Эльфийская страна представлена клетчатым прямоугольником из n строк и m столбцов. В k клетках находятся источники жизни, ещё в k клетках находятся источники магии, при этом все источники находятся в различных клетках. По счастливому совпадению, у умершего короля было ровно k сыновей, поэтому они хотят разделить страну на k связных областей таким образом, чтобы каждая область содержала ровно один источник жизни и ровно один источник магии. Область называется связной, если из любой её клетки можно попасть в любую другую клетку этой области, переходя только по клеткам, принадлежащим области и имеющим общую сторону. Каждая клетка должна относиться ровно к одной области. Области могут содержать «дырки», то есть одна из областей может быть со всех сторон окружена другой.
Формат ввода
- В первой строке содержится три целых числа n, m и k (3 ? n, m ? 50, 3 ? k ? 16) — размеры страны и количество источников жизни и магии.
- В следующих k строках содержатся пары целых чисел rli, cli (0 ? rli ? n?1, 0 ? cli ? m?1) — координаты источников жизни.
- В следующих k строках содержатся пары целых чисел rmi, cmi (0 ? rmi ?n?1, 0 ? cmi ? m?1) — координаты источников магии.
- Гарантируется, что все источники находятся в различных клетках, а также что для указанных входных данных существует хотя бы одно разделение на области, удовлетворяющее вышеописанным условиям.
Формат вывода
Выведите n строк по m латинских букв в каждой: разбиение страны на области. Участки, содержащие одинаковые буквы, будут отнесены к одной области. В качестве символов разрешается использовать строчные и прописные английские буквы. Всего должно быть использовано в точности k различных букв. Клетки с одинаковыми буквами должны образовывать связную область. Каждая область должна содержать ровно один источник жизни и ровно один источник магии.
Система оценки
Предоставленное разбиение будет оценено по следующей системе:
- Если разбиение некорректно (оно содержит несвязные области, либо области содержат неверное количество источников, либо не соблюдён формат вывода), ваше решение получит 0 баллов за этот тест;
- Иначе для каждой области определим её «выпуклость» как отношение площади к квадрату периметра области, где площадь — это количество клеток, входящих в область, а периметр — количество сторон клеток, смежных с другими областями либо с границей страны (см. пример для пояснения);
- Сумма баллов за тест — средняя «выпуклость» всех областей, умноженная на 160 000 и округлённая к ближайшему целому.
При отсылке во время соревнования ваше решение будет проверено на наборе из 50 предварительных тестов. Ваш предварительный результат будет равен среднему количеству баллов за все тесты. Обратите внимание на ссылку «отчёт» рядом с отосланным решением: она позволяет увидеть, на каких тестах ваша программа успешно отработала, а на каких выдала некорректный ответ или же не выдала его вовсе. Увидеть как входные, так и выходные данные для конкретного теста нельзя.
После окончания соревнования ваше последнее отосланное и скомпилированное решение будет проверено на полном наборе из 250 тестов (50 предварительных тестов не входят в полный набор). Среднее количество баллов по всем тестам из полного набора и будет вашим окончательным результатом.
Генерация тестов
- 40% тестов в каждом наборе являются полностью случайными: равновероятно выбраны n, m, k, после чего на поле некоторым случайным образом распределено соответствующее количество источников жизни и магии.
- 40% тестов в каждом наборе сгенерированы следующим образом: равновероятно выбраны n, m, k, после чего на поле некоторым случайным образом распределено k источников жизни. Рядом с каждым источником жизни некоторым случайным образом сгенерирован источник магии так, чтобы разность координат по каждой из осей не превышала d, где d — фиксированное для теста число от 1 до 4, выбранное равновероятно.
- 20% тестов в каждом наборе сгенерированы следующим образом: равновероятно выбраны n, m, k, после чего выбрано число s такое, что 2s ? min(n, m) и k ? 4(s ? 1). После этого на поле некоторым случайным образом выбраны два непересекающихся квадрата размером s?s, в одном из которых некоторым случайным образом распределены k источников жизни, а в другом k источников магии.
Если на очередном шаге генерации в любом из алгоритмов дальнейшие действия произвести невозможно, то весь процесс генерации начинается сначала.
Пример
| ввод | вывод |
4 6 3 0 0 1 3 3 0 3 5 2 4 2 2 |
aaabbc aaabbc aaabbc cccccc |
Примечания
В примере имеются три области:
- Область ‘a’: площадь 9, периметр 3 + 3 + 3 + 3 = 12, «выпуклость» 0.0625
- Область ‘b’: площадь 6, периметр 3 + 2 + 3 + 2 = 10, «выпуклость» 0.06
- Область ‘c’: площадь 9, периметр 4 + 6 + 1 + 5 + 3 + 1 = 20, «выпуклость» 0.0225
Тогда средняя «выпуклость» равна 0.048(3), а количество баллов за этот тест — 7733.
Вы можете отправлять решения не чаще одного раза в 5 минут.
Константин Хадаев (Россия, 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 для построения путей. Думаю, если бы я задействовал это в качестве альтернативного подхода, то получил бы корректные ответы на указанных тестах, а возможно и улучшил бы другие результаты.
Thanks for the great contest and the very interesting task! It was a pleasure to work on it. The only thing I did not like was a bit unclear
statement of the test case generation («some random distribution» — but what distribution?), possibly a 'official' test generator could be even included (with no seeds), with the non-trivial part «make sure that a solution exists» left for us to implement (or solve manually).
The commented version of my solution can be found at:
https://www.mimuw.edu.pl/~erykk/yandex/solution.cpp
I see that I have failed some final tests (the public tests were all okay). I did not get the idea to use min-cost-max-flow to generate paths; I think using this as an alternative approach could help me get positive scores on these few tests, and possibly improve the results on other tests.
Илья Корнаков (Швейцария, 6 место по итогам раунда)
Я уже что-то написал в http://codeforces.com/blog/entry/51858?#comment-358766
Задача понравилась, по модулю тормозов Java. Решение устроено следующим образом:
- Сначала min-cost-max-flow ищет пути, соединяющие истоки и стоки.
- Потом пути расширяются жадно, пока поле не будет заполнено. Жадные шаги пробуют добавлять по одной клетке, а также по отрезку столбца/строки к существующей компоненте. Целевая функция — изменение скора / (количество добавленных клеток + 10).
- Полученное решение жадно оптимизируется, перекидывая клетки или отрезки столбцов/строк между компонентами (с той же целевой функцией).
- Описанный процесс запускается много раз, выбирается лучшее решение. В процесс добавлен рандом: рёбра в графе для потока перемешиваются, скоры в жадности умножаются на случайное число от 1 до 1,2.
Больше всего очков принесло переписывание решения с Java на C++ (~+150). Помимо этого, жадные улучшения после того как решение сгенерировалось — видимо, полезная идея. Из нереализованного — пробовать больше изменений в жадности (например, отрезать «углы» — пары сторон) и вместо потока сделать что-нибудь, что лучше приспособлено к целевой метрике (т. к. для потока длинный горизонтальный путь — сильно лучше, чем путь по диагонали с таким же горизонтальным смещением, а с точки зрения целевой метрики — сильно хуже). Ещё была идея попробовать simulated annealing вместо жадности, но на это не осталось времени.
Bragaman
А есть возможность для тех, кто не участвует в конкурсе, проверять свои решения на Ваших тестовых данных?
altolstikov
Да, вы можете решать задачу до 17 июля в отдельном контесте.