В субботу, 19 сентября, состоялся финальный раунд RCC 2015. Победителем и обладателем главного приза в 300 000 рублей стал Петр Митричев, который уже завоевывал кубок RCC дважды: в 2011 и 2013 годах. Второе место и приз в 150 000 рублей получил победитель RCC прошлого года — Геннадий Короткевич. Третье место, как и в прошлом году, занял Егор Куликов. Его приз составил 90 000 рублей. Также призы по 30 000 рублей получили участники, занявшие с 4 по 10 места — Павел Марин, Владислав Епифанов, Сергей Копелиович, Юрий Писарчик, Константин Семенов, Михаил Тихомиров и Николай Калинин.
Герои раунда:
- Первым за 6 минут и 8 секунд решил задачу A (Сгибание ленточки) Геннадий Короткевич (tourist), он же раньше всех — за 45 минут и 29 секунд — справился с задачей D (Правильный сад).
- Финалист из Японии Kawai Ryuta (anta) раньше всех решил задачу B (Сбор монет) — за 16 минут и 20 секунд.
- Петр Митричев (Petr) первым решил задачу С (Топологическая сортировка и дети) — за 45 минут и 29 секунд.
- Задачу F (Робот на дереве) не смог решить ни один из финалистов.
Как мы говорили, в этом году финал проходил в уникальном для IT-чемпионата формате: он сопровождался четырёхчасовым онлайн-шоу, которое транслировалось на нашем сайте. Мероприятие в прямом эфире вели популярный российский шоумен Антон Комолов (выпускник МГТУ им. Баумана) и руководитель Центра олимпиадной подготовки программистов Саратовского Государственного Университета Михаил Мирзаянов. Гостями студии стали Николай Никифоров — министр связи и массовых коммуникаций РФ, представители ведущих IT-компаний и ключевые эксперты отрасли. Запись трансляции можно посмотреть на https://it.mail.ru/rcc/.
А теперь перейдем к разбору задач.
Задача А. Сгибание ленточки
Идея: Владимир Смыкалов
Реализация: Дмитрий Филиппов
Разбор: Дмитрий Филиппов
В задаче дана полоска 1×2n, которую сначала n раз сложили ровно пополам, а потом развернули обратно. Складывания возможны двух способов: левую половину наложить на правую или правую половину наложить на левую. Требуется отвечать на запросы: по номеру сгиба узнать, ориентирован он вверх или вниз.
Научимся отвечать на запрос за O(log 2n), то есть за O(n). Суммарное количество запросов не превосходит 105, поэтому этого вполне достаточно. Будем эмулировать процесс сгибания для каждого запроса. Зная текущие длину ленточки и номер сгиба, легко понять, в какой половине этот номер находится, а затем, зная, в какую сторону произойдет сгиб пополам, можно найти и новое положение сгиба в укороченной в два раза ленточке. Для ответа на запрос одновременно с положением поддерживаем, в какую сторону сейчас ориентирован сгиб. Итого, получаем решение за O(qn), где q — суммарное количество запросов.
Задача B. Сбор монет
Идея: Виталий Аксенов
Реализация: Борис Минаев
Разбор: Борис Минаев
В задаче дана лента, разбитая на клетки, по которой ходит игрок. Каждую секунду в каждой клетке дополнительно появляется некоторое число монет, фиксированное для каждой клетки. Игрок за секунду может перейти в соседнюю клетку или остаться в текущей. Каждый раз, когда игрок находится в некоторой клетке, он собирает все монеты, которые в ней находятся. Необходимо посчитать, какое максимальное число монет может собрать игрок за t секунд.
Заметим, что для каждой клетки важно знать только последний момент, когда игрок в ней находился. Рассмотрим путь игрока с конца. В каждый момент времени про некоторый непрерывный отрезок клеток уже известен последний момент их посещения, а для остальных клеток нет. Поэтому можно воспользоваться методом динамического программирования, состоянием которого будет отрезок посещенных клеток и текущее время. Кроме того, необходимо хранить текущую позицию игрока. Заметим, что можно хранить только те позиции, когда игрок стоит на одном из концов отрезка посещенных клеток. Из каждого состояния существует не более чем два перехода: игрок может посетить клетку слева или справа от уже посещенных. Таким образом, время работы алгоритма составляет O(n2t).
Задача C. Топологическая сортировка и дети
Идея: Артем Васильев
Реализация: Виталий Аксёнов
Разбор: Виталий Аксёнов
В задаче дан граф и его топологическая сортировка, некоторые элементы которой были стёрты. Нужно корректно её восстановить топологическую сортировку.
Рассмотрим сначала алгоритм, а потом докажем его корректность. Вершины, для которых дан порядок, будем называть помеченными, остальные — непомеченными. Мы знаем, какие числа не использовались в топологической сортировке, будем выставлять их по одному от больших к меньшим в соответствие вершинам. У нас есть очередное нерасставленное число. Первым делом удалим все уже помеченные стоки. Далее для каждого непомеченного стока узнаем максимальное значение в помеченной вершине, достижимой по обратным рёбрам. Для каждой вершины это число можно предподсчитать заранее: находим какую-либо топологическую сортировку графа и решаем задачу динамического программирования. В качестве соответствующей вершины нерасставленному числу выбираем любой сток, у которого предподсчитанное число наибольшее, и удаляем его из графа.
Предподсчёт чисел выполняется за O(V+E). Каждую итерацию нужно выполнять как можно быстрее, поэтому в каждой вершине мы храним количество оставшихся из неё исходящих рёбер. Когда мы удаляем сток, у всех вершин, из которых есть в него ребро, уменьшается исходящая степень, и, если эта степень становится нулём, помещаем эту вершину в сет по предподсчитанному значению. Тем самым в нашем сете хранятся все стоки, и для выбора нужного нам достаточно взять самую последнюю вершину из сета. Каждая вершина кладётся в сет и вытаскивается ровно один раз. Итого время работы алгоритма: O(V·log(V) + E).
Теперь докажем корректность нашего алгоритма. Заметим, что нам достаточно доказать правильность первого шага алгоритма, далее используем метод математической индукции. Рассмотрим корректно заполненную топологическую сортировку p, предварительно выкинув все помеченные стоки. Далее рассмотрим сток s, который мы выбрали нашим алгоритмом для максимального числа, и сток, которому оно соответствует в топологической сортировке p. Если мы все числа в перестановке большие p(s) уменьшим на единицу, а выбранному нами стоку s выдадим максимальное число, перестановка останется корректной. Операция произошла корректно: мы сохранили свойство топологической сортировки для непомеченных вершин, а для помеченных вершин значение топологической сортировки не поменялось, так как по свойству выбора вершины sp(s) больше, чем значение топологической сортировки любой помеченной вершины.
Задача D. Правильный сад
Идея: Артем Васильев
Реализация: Артем Васильев
Разбор: Артем Васильев
В этой задаче дано множество точек на плоскости и введено понятие хорошего множества точек. Хорошим множеством точек называется такое множество точек, что любой невырожденный прямоугольник со сторонами, параллельными осям координат, и с противоположными углами в заданных точках содержит хотя бы одну другую точку из этого множества внутри или на границе. Требуется проверить, обладает ли заданный набор точек таким свойством.
Для начала докажем эквивалентное свойство: множество точек хорошее тогда и только тогда, когда для каждого угла такого прямоугольника существует точка на смежной с этим углом стороне. Очевидно, если выполняется это свойство, то выполняется и свойство, описанное в условии задачи. Однако верно и следствие в противоположную сторону: рассмотрим произвольный прямоугольник с углами в точках A и B. По предположению, внутри или на границе этого прямоугольника существует другая точка из множества, назовем ее C. Если эта точка уже лежит на стороне, смежной с A, то наше утверждение верно. Иначе рассмотрим прямоугольник, построенный на точках A и C. Его площадь строго меньше, чем площадь исходного прямоугольника, а точек в множестве конечное число, значит когда-нибудь мы выберем точку, лежащую на стороне, смежной с A.
Сформулированное свойство помогает дойти до решения: для точки (xi, yi) обозначим за lefti такой максимальный x < xi, что в заданном наборе существует точка (x, yi). В случае, когда это значение не определено, считаем его равным минус бесконечности. Аналогичным образом введем величины righti, downi и upi. Рассмотрим область (lefti, righti) × (downi, upi). Если в этой области есть другая точка из заданного набора, то можно найти две точки, для которых построенный прямоугольник нарушает свойство. Стоит заметить, что подходит не любая точка из этой области. В качестве второй точки всегда подходит, к примеру, ближайшая по евклидовому или манхэттенскому расстоянию. Когда в этой области находится только точка (xi, yi), все прямоугольники содержат другую точку на стороне, смежной с ней. Таким образом, решение свелось к проверке n прямоугольников на наличие более одной точки внутри.
Реализовать такую проверку можно с помощью любой структуры данных, которая позволяет считать количество точек в прямоугольнике на плоскости: двумерное дерево отрезков (онлайн решение) или офлайн решение со сканирующей прямой и одномерным деревом отрезков. Такое решение можно реализовать за O(n log(n)).
Задача E. Междуречье
Идея: Виталий Аксёнов
Реализация: Илья Збань
Разбор: Илья Збань
В задаче даны n непересекающихся монотонных ломаных и выпуклый многоугольник. Нужно узнать, какое минимальное число раз нужно приложить многоугольник, чтобы каждая ломаная имела хотя бы одну общую точку с одним из приложенных многоугольников (на границе или внутри многоугольника).
Заметим, что, поскольку многоугольник выпуклый, а ломаные монотонны и не пересекаются, верен следующий факт: если многоугольник пересекает ломаные i, k, то для любого j, что i ≤ j ≤ k, этот многоугольник пересечет и j-ю ломаную. Используя этот факт, будем решать задачу жадно: найдем максимальное i1, такое, что существует многоугольник, пересекающий все ломаные с 1-й по i1-ю, добавим его к ответу, и продолжим: найдем максимальное i2 такое, что существует многоугольник, покрывающий ломаные с i1+1-й по i2-ю, и так далее. Число многоугольников, которые пришлось использовать, и будет ответом.
Научимся для ломаной ik находить значение ik+1. Это максимальный индекс, такой, что существует многоугольник, покрывающий ik+1-ю и ik+1-ю ломаную. Решим сначала более простую задачу: есть точка A и отрезок BC, нужно проверить, существует ли многоугольник, содержащий внутри себя и данную точку, и какие-то точки отрезка. Для этого построим сумму Минковского этого многоугольника и его самого же, инвертированного относительно (0, 0) (то есть, с противоположными по знаку координатами всех точек). Это какой-то новый многоугольник, назовем его P, с O(n) вершин, содержащий внутри себя точку (0, 0). Сдвинем его так, чтобы точка (0, 0) перешла в точку A, и проверим, что отрезок BC пересекается со сдвинутым многоугольником P — несложно убедиться, что это необходимое и достаточное условие.
Научившись проверять, существует ли многоугольник, пересекающий точку и отрезок, проверить то же самое для двух ломаных совсем несложно: перебираем отрезок на одной ломаной, строим его сумму Минковского с многоугольником P и проверяем, пересекается ли новый выпуклый многоугольник с каким-нибудь отрезком второй ломаной.
Пусть k — суммарное число вершин на всех ломаных. Найдём асимптотику используемых нами операций — O(n) на построение многоугольника P, O(n) на построение суммы Минковского P и отрезка ломаной и O(log n) на проверку пересечения выпуклого многоугольника и отрезка. Так как многоугольников нужно построить максимум k, а пересечь в худшем случае нужно каждый многоугольник с каждым отрезком, итоговая асимптотика времени работы равна O(nk + k2log n).
Задача F. Робот на дереве
Идея: Борис Минаев
Реализация: Борис Минаев
Разбор: Борис Минаев
В задаче дано неориентированное дерево из n ≤ 10 вершин. Про каждое ребро известна его прочность wi, которая не превышает 15. По дереву перемещается робот, который изначально находится в случайной вершине. Каждый раз робот равновероятно выбирает ребро из тех, по которым он может пройти, и перемещается по нему. Каждый раз, когда робот проходит по ребру, его прочность уменьшается на единицу. Если прочность становится равна нулю, то ребро удаляется. Если у робота нет ребер, по которым он может пойти, он останавливается. Необходимо посчитать математическое ожидание длины пути робота.
Для начала решим более простую задачу. Предположим, что необходимо посчитать не математическое ожидание длины пути, а количество различных путей, по которым мог пройти робот. Представим, что мы зафиксировали вершины, в которых робот начал и закончил свой путь, а также количество раз, которые робот прошел по каждому ребру. Рассмотрим, какие существуют ограничения на эти количества. Во-первых, ребра, по которым робот прошел положительное число раз, должны образовывать связный подграф исходного дерева. Во-вторых, рассмотрим некоторую вершину и количество раз, которые робот прошел по всем ребрам, которые являются смежными с этой вершиной. Если эта вершина является концом пути, то каждое смежное с ней ребро должно использоваться ровно wi раз. Максимум два ребра смежных с вершиной должны быть использованы нечетное число раз. Причем, если эта вершина лежит на пути из стартовой в конечную, то ровно два ребра должны быть использованы нечетное число раз. Для стартовой и конечной вершины (если они не совпадают) должно быть ровно одно ребро, которое используется нечетное количество раз, либо ноль, если вершины совпадают. Для всех остальных вершин все смежные ребра должны быть использованы четное число раз.
Если все эти условия выполнены, научимся считать количество путей, которые удовлетворяют условию задачи и используют ребра фиксированное количество раз. Для каждой вершины рассмотрим все смежные с ней ребра. Мы знаем количество раз, которое робот прошел по каждому из них. Мы можем легко посчитать, сколько раз робот прошел по ребру в направлении от заданной вершины. В каком порядке робот мог проходить по этим ребрам? Во-первых, по ребру, которое лежит на пути к вершине, в которой робот закончил путешествие, робот должен пройти в последнюю очередь. По всем остальным ребрам он может идти в любом порядке. Подсчет количества таких способов является стандартной задачей. Чтобы посчитать общее количество путей, по которым может пройти робот, необходимо перемножить посчитанные значения для каждой вершины.
Заметим, что для подсчета общего количества путей можно воспользоваться методом динамического программирования. Посчитаем количество путей, которые проходят по некоторому ребру заданное число раз и каким-либо образом проходят по поддереву, которое ограничено этим ребром. При этом считается, что каждый раз, когда путь идет вверх по ребру, он сразу же возвращается назад по нему. Чтобы посчитать значение динамического программирования необходимо зафиксировать количество раз, которые робот прошел по каждому из ребер, которые идут в поддеревья, умножить на уже посчитанные значения для поддеревьев, а также на количество способов расположить переходы в поддеревья. Будем рассматривать поддеревья вершины по очереди и фиксировать количество раз, которые суммарно робот пойдет во все рассмотренные поддеревья. Рассматривая очередное поддерево переберем количество раз, которые робот перейдет в это поддерево. Домножим ответ на значение динамического программирования от поддерева, а также на количество способов расставить переходы в поддерево среди других переходов.
Вернемся к первоначальной задаче. Теперь вместо количества способов будем хранить вероятность выбрать такой путь, а также математическое ожидание его длины. Подсчет вероятности отличается от подсчета количества способов только тем, что при каждом переходе по ребру необходимо поделить значение на количество ребер, которые инцидентны данной вершине. Единственная проблема, которая возникает при этом, заключается в том, что степень вершины не является константой, так как ребра удаляются во время путешествия робота. Чтобы посчитать значения динамического программирования для ребра воспользуемся следующей идеей. Зафиксируем все поддеревья, ребра в которые будут удалены, а также общее количество раз, которое робот будет идти из вершины по некоторому ребру. Будем восстанавливать путь с конца. Существует два возможных варианта, которые необходимо различать. Либо робот идет по ребру, которое не будет удалено, тогда нужно уменьшить количество ребер, по которым еще необходимо пойти роботу и перейти к меньшей задаче. Либо робот идет по ребру, которое будет удалено, тогда к общему количеству ребер, по которым роботу необходимо пройти, нужно добавить количество раз, которые он пройдет по данному ребру, а также увеличить количество существующих инцидентных ребер на единицу.
Всего существует O(2children∑wi) состояний в динамическом программировании для заданного ребра, и переход между ними осуществляется за O(1). Так как необходимо посчитать значение динамического программирования для каждого количества раз, в которых было использовано ребро, общее время работы алгоритма получается равным O(2n(∑wi)2).
