Разбор задач отборочного раунда RCC 2015

В воскресенье 14 июня прошел отборочный раунд RCC 2015. За звание финалиста RCC 2015 сразились 604 программиста, прошедших квалификацию в предыдущих трех раундах. Хотя бы одно правильное решение прислали 324 участника. А теперь герои раунда! Петр Митричев занял первую строчку турнирной таблицы, первым решив задачи B (Разбиение на команды) и F (Освещение сцены) за 20:32 и 1:31:41. Геннадий Короткевич идет вторым — он первым за 2 минуты и 30 секунд решил задачу A (Игра со строками) и раньше всех справился с задачей D (Декартовы деревья) за 14:16. Makoto Soejima из Японии — третий, судя по всему перед решением он переводил условия задач через онлайн-переводчик. Михаил Пядёркин первый решил задачу C (Карта) за 51 минуту и 4 секунды. Егор Куликов первым решил задачу E (Аллея) за 1 час 5 минут и 49 секунд. По итогам отборочного раунда в финал вышли 50 участников. 19 сентября в Финале определится сильнейший программист года! Все участники отборочного раунда получат онлайн-сертификаты, а 200 лучших из них получат футболки RCC 2015.
 

Задача A. Игра со строками

Идея: Григорий Шовкопляс
Реализация: Григорий Шовкопляс
Разбор: Григорий Шовкопляс

В задаче дана строка, с которой можно делать следующие операции:

• удалить три подряд идущих единицы;
• удалить два подряд идущих нуля;
• заменить подстроку «01» на подстроку «10»;
• заменить подстроку «10» на подстроку «01».

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

Для начала посмотрим на операции замен и поймем, что это не что иное, как swap. Таким образом, мы можем получить из данной строки любую, в которой содержится такое же количество нулей и единиц. Теперь с помощью этих операций получим из исходной строку, где все нули стоят в начале, а единицы в конце. Из получившейся строки мы можем получить строку новой длины, ничего не переставляя, так как все единицы и нули уже сгруппированы. Строку длины k можно получить из строки длины n, удалив 3x единиц и 2y нулей, где k = n - (3x + 2y). Значения x и y можно перебрать. И наконец, для каждой полученной строки нужной нам длины нужно учесть все перестановки. Их можно посчитать, например, как количество сочетаний из длины строки по количеству единиц в ней. Ответ будет равен сумме этих сочетаний для всех строк нужной длины, которые можно получить из данной.
 

Задача B. Разбиение на команды

Идея: Григорий Шовкопляс
Реализация: Дмитрий Филиппов
Разбор: Дмитрий Филиппов

В задаче дан граф, на каждом ребре которого написаны числа 0 или 1, означающие, что концы ребра одного цвета или разного соответственно. Также некоторые вершины графа покрашены в белый или черный цвет. Спрашивается, можно ли как-нибудь покрасить в черный и белый цвета остальные вершины, чтобы информация, написанная на ребрах, была верна, и количество вершин черного и белого цвета было одинаковым?

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

Несложно заметить, что мы свели нашу исходную задачу к задаче о рюкзаке: из каждой компоненты мы можем взять некоторое количество белых вершин, и всего их надо набрать n ⁄ 2 (если n нечетное, ответ на задачу — «NO»). А это уже можно решить с помощью динамического программирования за O(n²).
 

Задача C. Карта

Идея: Георгий Корнеев, Виталий Аксёнов
Реализация: Виталий Аксёнов
Разбор: Виталий Аксёнов

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

Рассмотрим сначала самую простую версию задачи. Дан прямоугольник, и нужно его сложить, получив минимальную площадь. Очевидно, что его нужно складывать по линии сетки, ближайшей к середине (если таких две, то можно сложить по любой). Рассмотрим функцию площади от позиции сгиба. Для прямоугольника с углами (x₁, y₁) и (x₂, y₂) эта функция имеет следующий вид:

• на отрезках (-∞; x₁] и [x₂; +∞) функция равна площади прямоугольника;
• на отрезке [x₁; (x₁ + x₂) / 2] функция линейно убывает с коэффициентом y₂ - y₁;
• на отрезке [(x₁ + x₂) / 2; x₂] функция линейно возрастает с коэффициентом y₂ - y₁.

Итого: функция меняет своё состояние только в трёх точках. Между двумя подряд идущими точками функция является линейной.

Заметим, что, так как наша задача дискретная, в случае, когда (x₁ + x₂) не делится на два, лучше бить функцию на пять участков между точками x₁, ⌊(x₁ + x₂) / 2⌋, ⌈(x₁ + x₂) / 2⌉ и x₂.

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

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

Задача D. Декартовы деревья

Идея: Артем Васильев
Реализация: Илья Збань
Разбор: Илья Збань

В задаче дано n чисел y_i, нужно было посчитать, сколько декартовых деревьев можно построить на множестве (i, y_i). Для начала заметим, что если все n чисел yi равны одному и тому же числу, то ответ — C_n, n-е число Каталана. Понять это можно, например, исходя из рекуррентной формулы: если в левое поддерево определить k вершин, то в правом окажется n-k-1 вершин, то есть C_n=Σ_k=0ⁿ C_k·C_n-k-1. Рассмотрим все вхождения максимального числа в массиве. Любая вершина с таким приоритетом может быть либо корнем, либо быть ребенком другой вершины с таким же приоритетом. Пусть вхождения максимума имеют индексы a₁, a₂, ..., a_k. Тогда мы должны построить какое-то декартово дерево на вершинах a₁, a₂, ..., a_k, и подвесить к нему какие-то декартовы деревья, построенные на вершинах (1, ..., a₁-1), (a₁+1, ..., a₂-1), ..., (a_k+1, ..., n). Заметим, что для соседних a_i и a_i+1 в любом декартовом дереве, построенном лишь на максимальных вершинах, одна из этих вершин будет предком другой, поэтому поддерево, построенное на вершинах (a_i+1, ..., a_i+1-1), мы сможем однозначно подвесить за одну из этих двух вершин.

Таким образом, число способов построить декартово дерево на вершинах с l по r равно cnt(l, r)=C_k · cnt(l, a₁-1) ·… · cnt(a_k+1, r). Ответом будет являться cnt(1, n).

Задача E. Аллея

Идея: Борис Минаев
Реализация: Борис Минаев
Разбор: Борис Минаев

С математической точки зрения, в задаче даны отрезки целочисленной длины. Необходимо разбить некоторые из них на более мелкие так, чтобы длина наибольшего отрезка была как можно меньше, а количество разбиений не превосходило заданного числа. Задача несколько усложняется тем, что суммарная длина всех отрезков может достигать 10⁹, а количество запросов, на которые необходимо дать ответ, может достигать 10⁶.

Рассмотрим, сколько необходимо сделать разбиений, чтобы ответ получился не более Ans. Для каждого отрезка длины Len необходимо сделать (Len - 1)/Ans разбиений (результат деления округляется вниз). Построим функцию количества необходимых разбиений от ответа для каждого отрезка. Сложим эти функции для всех отрезков. Для того чтобы найти минимальное значение Ans, которое можно достичь, сделав не более чем K разбиений, воспользуемся двоичным поиском.

Будем хранить функции в сжатом виде, а именно — сохраним значение функции для Ans только если f(Ans) ≠ f(Ans-1). Можно доказать, что для отрезка длины Len потребуется O(sqrt(Len)) памяти, чтобы сохранить его функцию. Позиции, в которых меняется значение функции, можно определить за время, пропорциональное их количеству. Максимальное суммарное число позиций изменения будет достигаться на тесте, в котором все отрезки имеют одинаковую длину. В случае ограничений, которые даны в условии задачи, их количество не может превышать 10⁶·sqrt(10³)=10^7.5.

Чтобы объединить несколько функций, которые сохранены в сжатом формате, необходимо отсортировать все моменты изменения функций. Для этого разобьем все позиции, в которых функции изменяются, на два класса. В первый класс отнесем все позиции, которые меньше 10⁶. Их можно отсортировать подсчетом за время, пропорциональное их количеству. Остальных же позиций будет немного, и для их сортировки можно использовать встроенные функции языка. Чтобы убедиться, что количество позиций, которые больше 10⁶, невелико, сделаем следующее. Для того, чтобы отрезок максимальной длины не превосходил 10⁶, достаточно сделать не более Len/10⁶ разбиений отрезков. Поскольку в условии задачи суммарная длина отрезков не превосходит 10⁹, то количество изменений функции, позиции которых превосходят 10⁶, будет меньше 1000.

Задача F. Освещение сцены

Идея: Артем Васильев
Реализация: Артем Васильев
Разбор: Артем Васильев

В этой задаче с довольно запутанным условием дан массив пар (мощность, множество выходов), и для каждой левой границы в массиве нужно найти минимальную правую границу, чтобы на этом подмассиве существовало подмножество пар со следующими условиями:

1. Сумма мощностей должна быть не меньше Z.
2. Множества выходов выбранных прожекторов попарно не пересекаются.

Подмассив с такими свойствами будем называть хорошим. Для начала решим задачу для одной фиксированной левой границы. Такую задачу можно решить при помощи динамического программирования по двоичным маскам: dp_mask — это максимальная стоимость прожекторов, для которых объединение множеств выходов является подмножеством mask. Формула пересчета для добавления одного элемента (p, m) выглядит так: dp'_mask = max(dp_mask, dp_{mask — m} + p), если m является подмаской mask, и dp_mask — иначе. Добавление одного элемента можно реализовать заO(2^k). Когда dp_{2^k - 1} становится больше или равно Z, надо выдать ответ.

Легко доказать, что при возрастании левой границы соответствующая правая граница не убывает. Это позволяет использовать технику двух указателей для нахождения ответа. Для реализации техники двух указателей необходимо реализовать структуру данных, которая поддерживает следующие операции:

1. Добавить элемент в конец.
2. Удалить элемент из начала.
3. Ответить на запрос: «Является ли текущее множество прожекторов хорошим?».

Решение данной задачи использует реализацию очереди на двух стеках с идеями из метода реализации очереди с минимумом. Аналогично очереди с минимумом, будем хранить в стеках не просто элементы, а пары (элемент; массив dp_i, в котором содержатся значения ДП для элементов с текущего и ниже). Добавление одного элемента в такой стек можно выполнить за O(2^k), удаление за O(1). Окончательно, используя такую модификацию стека в очереди, можно отвечать на запрос типа 3 за O(2^k): ответ на него положителен тогда и только тогда, когда max_{i = 0..2^k - 1} dp¹_i+dp²_{2^k - 1 - i} ≥ Z, где dp¹, dp² — массивы значений ДП на вершине первого и второго стека, соответственно.

В заключении, вспоминая, что каждый элемент в результаты работы очереди, реализованной на двух стеках, перемещается O(1) раз, получаем, что решение работает за O(n2^k) времени и использует O(n2^k) памяти.