SRM 433

Как известно, на топкодере довольно часто проводятся алгоритмические соревнования высокого уровня, называемые SRM-ами (Single Round Match). Каждый SRM, или попросту матч, длится примерно два часа. Первые 75 минут (называемые Coding Phase) участники занимаются непосредственно решением предложенных задач, затем идёт пятиминутный перерыв (Intermission), затем в течение пятнадцати минут (Challenge Phase) у соревнующихся есть возможность посмотреть на решения, присланные своими противниками, и попытаться их "зачеленджить", т.е. придумать такие данные, для которых решение не будет работать правильно. Потом некоторое время люди ждут окончательных результатов, болтают о том - о сём, сетуют на всё повышающееся количество китайских участников, и расходятся.

Учитывая, что уровень участников очень неоднородный, каждый матч проводится в двух дивизионах. Люди, имеющие более высокий рейтинг, соревнуются в первом, более низкий - соответственно, во втором дивизионе. Главное отличие между дивизионами - это предложенные задачи. В обоих дивизионах их по три. В рамках одного дивизиона задачи делятся на лёгкую, среднюю и сложную. Тем не менее, задачи первого дивизиона на порядок сложнее задач второго (лёгкая задача в первом дивизионе часто используется как средняя для второго). Так или иначе, для проведения матча всегда нужно от 4 до 6 более-менее оригинальных задач разного уровня сложности.

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

Провести свой собственный матч уже давно было моим заветным желанием, и ещё осенью у меня были готовы задачи, так что я терпеливо ждал своего шанса. И он появился примерно в то же время, когда мне предложили поработать на сборах. То есть в то время за мной закрепили SRM 433, дата которого была 21 января.

Процесс получения SRMа выглядит примерно так. Сначала человек делает наброски своих задач в специальном приложении MPSQAS, иначе говоря пишет условия, и необязательно оконченные. Потом надо написать администратору, ответственному за выбор задач, с просьбой посмотреть на плоды своих мучений. Рано или поздно ему приходится взглянуть на задачи, и тогда по каждой он или задаёт дополнительные вопросы, потому что наброски часто слишком далеки от совершенства, или сразу отклоняет, чаще всего потому, что она слишком неоригинальная и уже была на топкодере пару десятков раз, или утверждает её. Имея утвержденные задачи всех уровней для обоих дивизионов (в принципе, пару лёгких могут и простить для начала), можно смело просить SRM. Я не уверен, чем админы руководствуются, отдавая тот или иной матч в чьи-то руки, но могу сказать, что лично меня до сих пор не обижали.

Получив SRM, надо доводить его до ума. То есть если не хватало какой-либо задачи, надо её придумать, все условия надо максимально отточить, надо написать авторские решения - причём обязательно на Java, и на всех возможных тестах решение не должно работать больше 1 секунды, и надо добросовестно составить эти самые тесты. Потом за дело берутся люди, на которых возлежит ответственность за то, чтобы всё было максимально точно, правильно и понятно. По моему опыту, таких бывает трое: администратор, ответственный за выбор задач, тестер и PabloGilberto, который занимается исключительно английским языком. Выбор тестера происходит сразу после утверждения матча.

На моём первом SRMе координатором по задачам был OlexiyO, а тестером выступал Иван Метельский. Особо много нам мучаться не пришлось (разве лишь что меня заставили рисовать дополнительные картинки в div1 Medium), и день матча подошел довольно быстро. Перед матчем автору дают специально сгенерированный пароль от ника writer, который обладает разными прикольными функциями. Этот ник в арене обладает администраторскими привилегиями, и позволяет читать все чаты в арене, в том числе шепот. Хотя часто это становится просто проклятием, потому что чата чрезвычайно много. Также во время Coding Phase можно видеть коды любых участников. Вообщем, во время матча не соскучишься.

Что касается моих задач, бегло пройдусь по основным идеям:

Div2 Easy - RoyalTreasurer. Довольно стандартная задача - очевидно, что минимальная сумма достигается, когда наибольшие элементы первого массива сгруппированы с наименьшими элементами второго.

Div2 Medium / Div1 Easy - MagicWords. Несмотря на низкие ограничения, просто перебрать все возможные перестановки слов и проверить каждую тривиальным алгоритмом не получалось, или по крайней мере не должно было получаться. Есть множество методов, с помощью которых можно ускорить эту проверку: хеширование, KMP, технические оптимизации. Авторский вариант основывался на следующем наблюдении: если строка длины L повторяется в своих shift-ах ровно K раз, то она является периодической с периодом, равным L/K - и наоборот. Таким образом, надо было проверять периодичность строки для периодов, равных делителям L.
Ещё одно решение, которое я сначала не заметил, но потом мне очень понравилось, основывалось на том, что сместив последнее слово в нашей перестановке в начало, мы получаем строку с таким же множестов shift-ов. Таким образом, можно было перебирать все перестановки первых (N-1) строк, а последнюю всегда ставить в конец - тогда итоговый ответ получается при умножении полученного количества магических строк на N.

Div2 Hard - MakingPotions. Идеей решение похоже на алгоритм Дейкстры - на каждом шагу помечать полученным то снадобье, которое ещё не получено и имеет наименьшую цену. Если таким образом мы дойдём до LOVE, то получим его за наименьшую возможную цену, если нет - оно не достаётся. Проблемы могли возникнуть при парсировке входных данных, или с теми ситуациями, когда цены становились слишком большими.

Div1 Medium - SettingTents. Задача, которую решили, к моему удивлению, меньше ста человек, что для Medium в принципе маловато. На самом деле в ней проходил даже алгоритм сложности O(N^5), т.е. перебрать обе координаты обеих вершин диагонали ромба, а затем пройти одним циклом по длине второй диагонали и проверить, попадают ли её концы в целочисленные точки. От этого цикла можно было избавиться несложными математическими вычислениями. Во время матча большей частью были имплементированы более быстрые алгоритмы. Недавно я натолкнулся на довольно старый пост в блоге Petr-а, в котором были рассмотрены методы решения подобной задачи - советую посмотреть.

Div1 Hard - BarbarianInvasion. "Праздник потока", как её потом обозвали. Действительно, задача требовала нахождение минимального вершинного разреза, только при условии, что в первую очередь должно быть минимизировано количество вырезанных вершин, а потом их суммарная стоимость. В таком случае применяют следующий фокус: весом вершины делаем её стоимость + некую большую константу X, которая заведомо больше любой возможной суммарной стоимости вырезанных вершин при данных в задаче ограничениях. Тогда, найдя величину минимального разреза ANS между столицей и граничными клетками, мы будем иметь минимальное количество вырезанных вершин как ANS/X и минимальную стоимость этих вершин (при условии минимизации их количества) как ANS%X.

Можете также посмотреть editorial этого матча и его результаты.