Thursday, November 11, 2010

Topcoder MM DigitsPattern

Подошел к концу очередной Topcoder MM, задачка DigitsPattern, что ж этот матч был пожалуй самым неоднозначным из всех что мне доводилось видеть. Здесь было всё, и бурный старт большого числа участников в начале и осознание того, что что-то не так в середине и озарение уже ближе к концу. Концовка же была самой знаменательной. Такого еще не бывало, аж 46 участников разделили между собой первое место.
Видя такое единодушие среди участников невольно задумываешься, а нет ли здесь случайно точного решения. Какого-нибудь динамического или жадного алгоритма. На поиски этого точного решения я и потратил чуть меньше недели. Скажу сразу, не нашел. Может быть оно и есть, вот только мое решение было далеко от идеального когда оно тоже поднялось на первое место. Что же это, слабость тестовых данных или сама задачка такова, что её способны решить столь большое число участников. Я надеюсь, что первое, но лучше подождем финальных результатов, они либо опровергнут либо подтвердят мою гипотезу.
Задачака звучала так (за полной формулировкой обращайтесь к исходникам): Вам требуется последовательно заполнить поле в клетку различными цифрами. Когда вы зполняете некоторую свободную клетку, она получает значение 1, все соседние с ней клетки получают +1 к своему значению, если они заполнены. В качестве входного параметра вам дается целевой шаблон и ваша цель заполнить как поле как можно ближе к этому шаблону. Близость к шаблону определяется как сумма абсолютной величины отклонения значения клетки в шаблоне от значения полученного в результате заполнения. Есть еще особые правила формирования шаблона, задаются размеры поля и способ кодирования ответа и входных параметров, все это интересующиеся могут почитать в исходном тексте.
Первая идея которая пришла мне в голову заключалась в том, чтобы нумеровать клетки в порядке обратном их величине в шаблоне. Это очевидное и безумно простое решение дало бы в итоге ~200-ое место. Любые попытки перебора, перестановок и прочих манипуляций с этим подходом едва ли вывели бы даже в первую сотню.
Озарением стало, что можно просто последовательно отбирать клетки с минимальным значением разности «максимально возможное значение клетки» - «требуемое значение клетки». Максимально возможное значение для данной клетки равно количеству не заполненных на данный момент времени соседей + 1. Очень простая формула и на уливление хороший результат. Это решение подняло меня в топ 100. Следом была простое и очевидное изменение: немного менять порядок выбираемых клеток, решение за решением, это дало мне 50-ое место.
Остаток времени я посвятил нежному и внимательному тюнингу решения: добавил кэш, чтобы отслеживать состояния в которых уже был. Добавил дополнительную сортировку для выбираемых клеток (теперь уже они выбирались не просто с минимальным значением разности но и с учетом соседних клеток). Эти манипуляции вывели меня на 1-ую строчку предварительного рейтинга.
Выход на первую строчку охладил интерес к дальнейшему решению, наверное зря. Ведь на собственной базе данных из 1000 тестов, увеличив время решения в 10 раз, я легко убедился, что мое решение не оптимально как минимум в 17 случаях. Но желания что-то подкручивать и искать дальнейшие оптимизации уже не было.

Интересные находки:
Класс java.util.BitSet, когда-то я о нем читал в книжках, но до сих пор на практике не приходилось использовать. В этой задачке он пригодился для кэширования. BitSet служил ключем для кэша. К сожалению, вскоре по результатам профайлинга мне пришлось сделать собственную реализацию FastBitSet потому что скорость работы стандартной была явно не удовлетворительной. Конечно это связанно с расширенным функционалом стандартной реализации и с ограниченными требованиями в моем случае.

No comments:

Post a Comment