SRM 443

Примерно в начале апреля был объявлен конкурс на составление задач для onsite-раунда TCO 2009 - ежегодного чемпионата, проводимого топкодером. Вплоть до начала мая авторы могли засылать свои задачи, из которых должны были выбрать лучшие 12. Потом в течение мая их тестили и отбирали лучшие шесть - 3 для полуфинала и 3 для финала.

Я тоже решил испытать судьбу и предложил пару задач - один Easy и один Medium. В итоге в 12 кандидатов ни одна не попала. Во время моего второго SRMа я пообщался с Иваном по их поводу, и он сказал, что Easy была слишком сложной, а Medium - слишком лёгкой :) Тем не менее, он считал, что первую можно использовать как Div1 Medium для обычного матча, а вторую - как Div2 Hard. Так что я вскоре состряпал ещё 3 задачи и попросил на них взглянуть.

Сразу после окончания TCO, то есть в первых числах июня, Иван действительно посмотрел на задачи. Более того, он сразу предложил мне выбрать дату матча - честно говоря, проведя SRM только за месяц до этого, я этого не ожидал. На календаре значился только SRM 443, а остальные ещё не были прописаны, поэтому особо выбирать мне не пришлось.

В процессе тестирования я пару раз заменил Div2 Easy, а также придумал другой Div1 Hard. Наконец задачи были утверждены в том комплекте, который и попал на матч. Но вот по поводу распределения очков за задачи довольно долго шел спор. Вернее, главным образом спорили по поводу задачи BinaryFlips - той, что я задумывал как Easy для TCO. Мне она представлялась не такой уж сложной, и я требовал за неё чуть ли не 450 очков. Тестер и Метельский же, напротив, настаивали на 600. В итоге я сдался, и результаты ясно показывают, что я был неправ.

Что касается решений, в каком-то виде они лежат в editorialе на топкодере, но я всё же опишу свои варианты.

Div2 Easy - SoccerLeagues. Как и подобает задаче этого уровня, никаких особых знаний или оригинальных подходов в ней не требуется. На самом деле задача была даже легче обычного: правильно написать два вложенных цикла умудрились почти все участники.

Div2 Medium / Div1 Easy - CirclesCountry. Тут я ещё в условии прикольнулся, правда без знания грузинского языка этого всё равно не понять. Так вот, к этой задаче есть два подхода. Первый, более сложный - построить граф (а собственно дерево) из окружностей и найти в нём длину пути между окружностями, содержащими требуемые точки. Честно говоря, моё решение было именно таким, и я был довольно удивлён, когда в процессе тестирования нашлось намного более лёгкое: просто посчитать количество окружностей, которые содержат ровно одну из требуемых точек. Таким образом, для многих опытных участников проблемой стало то, что они сразу начали реализацию первого подхода и потеряли минут десять относительно людей, имплементировавших подоход №2.

Div2 Hard - Polygons2. Учитывая, что многие кодеры во втором дивизионе справились с первыми двумя задачами за 20-25 минут, по этой задаче было много (92) submission-ов. Тем не менее, большинство из них было просто перебором. В итоге правильными было только 5 решений, и самое быстрое из них заняло 42 с лишним минуты. Это меня хоть немного успокоило, потому что для меня задача была совсем не лёгкой. А решать её надо с помощью динамического программирования: ответ можно легко вычислить, если знать, сколькими способами можно получить (K-1)-угольник с наибольшей стороной длины A и периметром P. Эту начальную идею нужно было несколько оптимизировать, но в итоге код получался длиной в несколько строк.

Div1 Medium - BinaryFlips. В отличии от подходов, описанных на топкодере, моё решение имеет сложность O(1). Я бы его и туда добавил, но боюсь, что не смогу нормально объяснить. По крайней мере, пока здесь попытаюсь.
Давайте каким-либо образом проиндексируем все A+B чисел. В конечном итоге нам нужно изменить ровно A индексов по отношению к их начальному состоянию. Очевидно, что за один ход мы можем изменить ровно K индексов. За два же хода можно изменить любое четное количество индексов в пределах от 2 до 2*min(K,N-K). Например, чтобы изменить ровно 2 индекса за 2 хода (при K>1), мы можем флипануть за первый ход некоторое множество индексов {i1,i2,...,i(K-1),j1}, а за второй - множество {i1,i2,...,i(K-1),j2}. Таким образом, относительно начального положения изменятся только индексы j1 и j2. Аналогично, для изменения большего количества индексов, надо брать меньше общих элементов для изменяемых на каждом ходе множеств. Именно поэтому невозможно изменить больше, чем 2*(N-K) индексов.
Так что мы имеем? Мы должны выразить число A в виде суммы чисел K и четных чисел между 2 и 2*min(K,N-K), причём цена числа K равна 1, цена остальных чисел равна 2, и сумма должна быть как можно дешевле. Вот тут уже надо рассмотреть несколько случаев:
1) A=0 => ANS=0
2) A=K => ANS=1
3) Если ни одно не выполняется, то K>=N => ANS=-1
4) (A%2=1) AND (K%2=0) => ANS=-1. В этом случае мы пытаемся получить нечётное число суммой четных.
Обозначим теперь Z=2*min(K,N-K) и функцию ceil(X)=наименьшее целое, большее или равное X.
5) (A%2=1) AND (K%2=1) => ANS=1+2*ceil(abs(A-K)/Z).
6) (A%2=0) AND (K%2=1) => ANS=2*ceil(A/Z).
7) (A%2=0) AND (K%2=0) => min(1+2*ceil(abs(A-K)/Z), 2*ceil(A/Z)).
Вдумавшись в каждое из этих выражений, можно (я надеюсь) понять, какая логика за ним стоит. Правда, написав всё это, я уже не думаю, что задача была такая уж и лёгкая :D

Div1 Hard - ShuffledPlaylist. Я снова написал задачу про музыку, правда, много наврал - никогда я ничего не shuffle-ю. Так или иначе, задачу можно было решать двумя методами. Для обоих общей частью является построение матрицы переходов из одного положения в другое. Положением в задаче описывается, песня какого стиля в данный момент проигрывается и сколько минут осталось до её окончания, плюс желательно иметь одно положение для начального момента.
Более сложный метод на этом останавливается и далее работает следующим образом. Если возвести начальную матрицу в степень X и посчитать сумму элементов, обозначающих переход от начального положения в конец песни для каждого стиля, мы получим количество плейлистов длины ровно X. Если мы как-то умудримся посчитать сумму таких элементов S(X) для всех степеней матрицы от 1 до X, мы получим количество плейлистов длины от 1 до X. Тогда ответом задачи будет S(maxLength)-S(minLength-1). А считать суммы в непрерывном интервале можно по формуле: S(1)+S(2)+...+S(X) = (S(X/2)+1)*[S(1)+S(2)+...+S(X/2)] (это при чётном X, при нечётном соответственно придётся отдельно прибавить элемент S(X)). Короче говоря, возни много.
Обойтись без суммирования матриц можно, если несколько видоизменить матрицу переходов, а конкретно - добавить в вершину, соответствующую концу плейлиста, из которой будут переходы только в саму себя. Тогда количество плейлистов длины от 1 до X будет храниться в элементе матрицы, соответствующем этой самой вершине.

В итоге SRM выдался довольно тяжелым, со всеми задачами в первом дивизионе справилось лишь 3 человека. Хотя в наших краях была глубокая ночь, и многие могут сослаться на это, оправдывая свои неудачи. Так или иначе, я снова получил удовольствие и до Нового года попытаюсь опять собраться с мыслями и выдать ещё один проблемсет ;)