Итоги Russian Code Cup 2014 и разбор задач
4 октября прошел финальный раунд крупнейшей в России ежегодной олимпиады по спортивному программированию Russian Code Cup. Победителем Russian Code Cup 2014 и обладателем главного приза — $10000 — стал Геннадий Короткевич. Второе место занял Петр Митричев — он получил $5000. Третьим финишировал Егор Куликов, его денежный приз составил $3000. Также в этом году впервые были награждены все участники, вошедшие в первую десятку: обладатели 4–10 мест получили по $1000.Финал прошел в новом для чемпионата онлайн-формате. В отличии от оффлайнового финала прошлого года, участникам сейчас не пришлось приезжать в Москву, а все предложенные задачи финалисты решали онлайн, в комфортной для них атмосфере. За звание лучшего программиста сражались 50 финалистов, преодолевших квалификацию и отборочный тур. 23 человека из финалистов этого года, участвовали в финале RCC 2013 года.
Самая простая задача — A, ее решили 45 финалистов. Самая сложная — F, по ней не было ни одной попытки. Если рассматривать только решенные задачи, то самой сложной была задача E, ее решили только 3 финалиста, причем первым это сделал Евгений Капун. А Алексей Шлюнкин решил только эту задачу.Финалисты использовали для решения задач только 2 языка программирования! C++ — 254 решения, из них 91 принятоJava — 52 решения, их них 24 принято
Первое правильное решение — Петр Митричев на 23 минуте, это самый сложный финал по этому показателю.
Победитель — Геннадий Короткевич — сдал пятую задачу за 1 минуту 51 секунду до конца контеста и вышел на первое место. Сдав пятую задачу, его могли бы опередить Петр Митричев, Егор Куликов или Дмитрий Джулгаков.
Яков Длугач сдал 3 задачи за последний час, две за последние 16 минут и ворвался в десятку на 7 место.
Задача A. ИграИдея: Анна МаловаРеализация: Анна МаловаРазбор: Анна Малова
Рассмотрим двудольный граф — первая команда, вторая команда. На ребре написано, какими подсказками владеет участник второй команды, которые еще не знает участник первой, то есть разность множеств подсказок участников. Оставим только те ребра, на которых записано одно число. Среди таких ребер оставим только те, на которых записано только одно число.
Используя построенный граф, составим другой двудольный граф: вершинами первой доли являются участники первой команды, вершины второй доли — те подсказки, которые еще неизвестны первой команде. Между двумя вершинами есть ребро, если было ребро в предыдущем двудольном графе, выходящее из той же вершины, на котором была записана эта информация. Если в полученном графе найдётся максимальное паросочетание, значит, первая команда может выиграть. Иначе, первая команда выиграть не может.
Чтобы уложиться в заданные ограничения по времени, для нахождения разности множеств нужно использовать битсет. Кроме этого, перед запуском алгоритма Куна для поиска максимального паросочетания, нужно сравнить размеры долей, если размер доли с подсказками превышает размер доли участников, то сразу выдается ответ 2. Без этой проверки, решение не укладывается в ограничения по времени.
Видеоразбор:
[embedded content]
Задача B. Покраска здания
Идея: Виталий АксёновРеализация: Николай ВедерниковРазбор: Николай Ведерников
В задаче требовалось покрасить полоску в два цвета. Мы умеем красить любой подотрезок в какой-то цвет. Требовалось посчитать количество способов раскрасить полоску за минимальное число покрасок.
В данной задаче есть два случая: концы полоски покрашены в один цвет или в разные. Рассмотрим первый случай.
Концы покрашены в один цвет, значит, всего отрезков 2k + 1. Покажем сколько минимум покрасок надо. Рассмотрим конечную раскраску полоски, если последним отрезком мы покрасили отрезок в середине, то общее количество отрезков увеличилось на два (мы разбили какой-то отрезок на два и добавили новый). Таким способом мы можем извлечь k отрезков и в конце останется 1. Итого мы потратили k + 1 ходов. Если в какой-то момент мы взяли отрезок не из середины, а с края, мы потратим больше ходов, чем надо.
Теперь посчитаем количество способов. Рассмотрим конечную раскраску и последним ходом мы красили отрезок в середине, тогда количество способов выбрать этот отрезок равно общему число отрезков минус крайние, итого 2k — 1. Тем самым мы свели задачу к задаче меньшего размером. Продолжая таким способом, мы получим итоговый ответ (2k — 1) · (2k — 3) ·… · 3 · 1, что равно (2k — 1)!…
Рассмотрим случай, в котором концы покрашены в разные цвета, тогда всего отрезков 2k. Рассмотрим конечную раскраску полоски. Пусть в начале мы l раз извлекали отрезки из середины, а потом извлекли отрезок с краю. Тогда мы потратили l + 1 и у нас осталось 2k-2l-1 отрезков, причём концы оказались одинакового цвета. По предыдущим рассуждениям мы не сможем раскрасить это быстрее, чем за k-l. Итого: k+1 ходов. Кроме того, отсюда следуют факт, что мы первым ходом красим, отрезок с одного из концов.
Теперь посчитаем количество способов. Назовём первый отрезок черным. Пусть первым ходом мы покрасили отрезок с левого края. Переберем докуда он покрасит, а всё, что справа от него, надо будет покрасить в белый, по нашим рассуждениям. Заметим, что теперь у нас получились две предыдущие задачи, у которых концы покрашены в один цвет. Пусть в левом отрезке l черных отрезков, тогда ответ на этом отрезке будет ((2l — 1) — 2)!, а на правом ((2k — (2l — 1)) — 2)!… Кроме того, мы можем можем красить отрезки из левой половины и из правой в любом порядке. То есть произведение отрезков надо ещё умножить на choose (l — 1, k), так как мы уже один отрезок покрасили, значит нам осталось сделать ещё k покрасок, а в левой осталось сделать l — 1 покрасок. Кроме того, первый отрезок мы могли красить и дальше, потому что мы поверх всё равно покрасим правым отрезком. А таких вариантов равно длина правой части. Итого, для фиксированого числа l ответ будет равен ((l — 3)!) · ((2k — 2l -1)!) · choose (l — 1, k) · (suff_lenl). Таким образом переберем l и просуммируем. Аналогично посчитаем для другого конца.
Если предподсчитать факториалы и обратные факториалы по модулю, то для одного l мы сможем отвечать за O (1). Итоговое время работы — O (n).
Видеоразбор:
[embedded content]
Задача C. Задача о рюкзаке
Идея: Борис МинаевРеализация: Артем ВасильевРазбор: Артем Васильев
В данной задаче требуется найти такой тест для задачи о рюкзаке, что количество способов набрать вес W делится на число M.
Далее будем считать W равным 500. Основная конструкция авторского решения основывается на генерации такого набора n вещей небольшого веса так, чтобы их сумма была меньше W/2. Подсчитаем для этого набора количество способов набрать подмножество вещей с суммарным весом k для всех k от 0 до W/2 и обозначим это число за ck. Потребуем, чтобы для нашего набора любое число от 1 до 1018 представлялось как сумма не более, чем 200 — n чисел ck.
Предположим, что существует такой набор вещей, чтобы для каждого x было такое k, что ck = 2x, то такое свойство было бы очевидно: для каждого x, если двоичная запись M содержит единицу на позиции x, мы добавим вещь с весом W — x в наш набор. Поскольку сумма вещей, добавленных до этого шага, была меньше W/2, то легко видеть, что количество способов получить вес W равно M. Заметим, что такой процесс можно описать следующим жадным алгоритмом: пока M больше нуля, мы находим максимальное ck ≤ M, добавляем вещь с весом W — k и вычитаем из M число ck.
К сожалению, такой набор вещей получить трудно, поэтому необходимо придумать какой-то другой набор вещей, обладающий тем свойством, что вышеописанный жадный алгоритм находит решение для любого M. Для этого возьмем набор вещей со случайным небольшим весом и суммой меньше W/2. Можно проверить и убедиться, что если мы выберем наш набор таким образом и посчитаем для него числа ck, то жадный алгоритм с большой вероятностью вернет корректное разбиение любого числа M на слагаемые ck. Таким образом, можно построить набор вещей, удовлетворяющий этому свойству, и с помощью жадного алгоритма добавить вещей таким образом, чтобы количество способов собрать W стало равным 0 по модулю M.
Видеоразбор:
[embedded content]
Задача D. Организация сети
Идея: Борис МинаевРеализация: Андрей КомаровРазбор: Андрей Комаров
В задаче было дано дерево и требовалось пометить минимально возможное число вершин так, чтобы вектора расстояний от каждой вершины до выбранных были различны.
Рассмотрим отдельно случай, когда заданное дерево является цепочкой: вершины можно упорядочить так, что первая связана только со второй, последняя только с предпоследней, а остальные только с двумя соседями. Если дерево является цепочкой, то, очевидно, в качестве ответа можно взять один из концов этой цепочки: все вершины будут удалены от него на различные расстояния.
Иначе, в дереве есть вершина степени больше двух. Подвесим дерево за эту вершину. Посчитаем следующую динамику для каждого поддерева: минимальное число меток, которое необходимо поставить в этом поддереве, чтобы вектора расстояний для каждой пары вершин этого поддерева были различны, при условии, что где-то выше корня поддерева есть хотя бы одна помеченная вершина. Назовём значение этой динамики min↑. Заметим, что это не совсем то, что нужно посчитать в задаче, но это совпадёт с задачей, если убрать ограничение на существование выше корня помеченной вершины. Назовём эту динамику min. Заметим, что min↑ ≤ min. Значит, если мы сможем предъявить ответ размера ровно min↑, то это будет ответом на задачу. Решим задачу в два этапа — сначала посчитаем значения min↑, а затем получим ответ такого размера.
Пусть мы хотим посчитать min↑ для какой-то вершины v. Посчитаем эти значения для её поддеревьев. Получили, что в некоторых из них есть хотя бы одна метка, а в остальных меток нет. Пусть количество поддеревьев, в которых меток нет, равно k. Тогда в ответ для v нужно добавить хотя бы k − 1 помеченную вершину (по одной в каждое непомеченное поддерево, кроме одного). Пусть мы добавили меньше. Тогда осталось хотя бы два непомеченных поддерева. Тогда корни этих поддеревьев будут неразличимы: в их поддеревьях помеченных вершин нет, а до всех остальных расстояния одинаковы. Теперь покажем, что этих добавлений хватит. Рассмотрим любые две вершины из разных поддеревьев. Они могут быть либо на одинаковой, либо на разной глубине. Пусть они на разной глубине. Тогда расстояния от них до предполагаемой помеченной вершины над корнем различны (различны длины путей до корня). Пусть они на одинаковой глубине. Тогда, по построению, хотя бы в одном из поддеревьев, в которых эти вершины лежат, есть помеченная вершина. Тогда расстояния до неё от этих двух выбранных вершин будут различны: от той, из чьего поддерева выбрана помеченная вершина, расстояние будет меньше.
Построим теперь ответ размера min↑. У выбранного нами корня хотя бы три ребёнка. Значит, по построению min↑, хотя бы в двух поддеревьях корня есть помеченная вершина. Значит, для каждого поддерева есть помеченная вершина вне этого поддерева. Возьмём её в качестве требуемой min↑ помеченной вершины выше. Тогда ответом будет являться объединение ответов min↑ для всех детей корня.
Все рассмотренные операции можно сделать с помощью одного обхода в глубину. Значит, итоговое время работы — O (n).
Видеоразбор:
[embedded content]
Задача E. Булево дерево
Идея: Борис МинаевРеализация: Демид КучеренкоРазбор: Виталик Аксенов
Для начала сведём нашу задачу к задаче об одной переменной. Заведём по дереву на каждую переменную, в которых в изначальном состоянии будут находиться корень изначального дерева и ссылка на него. Ссылка в дереве у нас всегда будет указывать на вершину, в чьём поддереве мы сейчас находимся. Обойдём наше дерево обходом в глубину. Если мы заходим в вершину, в которой выставлена какая-то переменная, то мы создаём у вершины в соответствующем дереве нового ребёнка и переставляем ссылку на него. Если мы выходим из вершины, то мы переставляем ссылку в соответствующем дереве на её предка. Мы сжали деревья. Нужно ещё не забыть хранить в каждой вершине количество листьев в её поддереве.
Мы теперь будем решать задачу на дереве для одной переменной. Будем обрабатывать все запросы на данную переменную последовательно. Нам нужно уметь делать две вещи:
на сколько листьев влияет только эта вершина; найти ближайшего предка, в котором выставлено какое-то значение для данной переменной. Если мы реализуем это, обрабатывать запрос не очень сложно: находим количество листьев, на которые влияет эта вершина — x; находим ближайшего предка, в котором выставлено какое-то значение для данной переменной — p; если в p такое же значение, что и в нашей вершине, то количество не меняется; если в p другое значение, нежели в нашей вершине, то количество меняется на x; если p не существует, то количество меняется на x* то количество «неизвестных» листьев уменьшается на x; в p нужно уменьшить количество влияемых листьев на x Чтобы реализовать запросы нужно развернуть дерево в дерево отрезков, где можно делать запрос на поддереве. Тогда запросы первого вида очень легко обрабатывать с помощью суммы в поддереве. Для поиска правильного предка сделаем следующее: когда делаем запрос в вершину, мы прибавляем ко всем вершинам в поддереве, кроме неё, единицу, то есть говорим, что они покрыты ещё одной вершиной. Тогда чтобы найти предка, мы будем искать двоичным подъёмом первую позицию, в которой значение отличается на единицу — она и будет искомым предком.Итоговое время работы: O (mlog2n), где n — размер дерева, m — количество запросов.
Видеоразбор:
[embedded content]
Задача F. Робот
Идея: Борис МинаевРеализация: Борис МинаевРазбор: Борис Минаев
В задаче необходимо было посчитать количество клеток, которые достижимы из первой строки поля. Основная сложность заключается в том, что размеры каждой стороны поля могут достигать 109 клеток.
Во-первых, из-за того, что робот совершает ходы по диагонали, удобно отдельно рассматривать клетки разной чётности. Робот может достичь все клетки первой строки поля. Будем увеличивать y и пересчитывать достижимые клетки. Удобнее всего хранить множество достижимых клеток для строки в виде объединения непересекающихся отрезков. Тогда можно легко пересчитывать множество при переходе к следующей строке. А именно, к каждому отрезку добавится по одной клетке с каждой стороны. Некоторые отрезки, возможно, объединятся в один, а некоторые пересекутся с границами поля или преградами.
Научимся эффективно изменять это множество отрезков. Лучше всего хранить его в структуре данных, которая позволяет за O (logn) находить отрезок, который пересекает заданную координату. Дополнительно, у каждого отрезка будем хранить информацию о том, может ли отрезок увеличится влево и вправо. Давайте аккуратно рассмотрим все события, которые могут происходить:
Два отрезка объединились. Это самый простой случай. Необходимо просто объединить их в структуре данных. Отрезок расширился до такой степени, что пересекся с краем поля или преградой. Тогда необходимо поставить пометку в описании отрезка, что он не может больше расти в некоторую сторону. Началась преграда. Необходимо рассмотреть все отрезки, которые пересекаются с преградой. Некоторые из них нужно полностью удалить, некоторые обрезать, а некоторые разделить на две части. Также необходимо создать события, которые произойдут, когда соседние отрезки разрастутся настолько, что пересекут текущую преграду. Преграда закончилась. Необходимо найти два соседних отрезка и поставить им пометку о том, что они могут расти в направлении прямоугольника. Также необходимо добавить событие, которое должно произойти между соседями. Например, если два соседа являются отрезками, то они могут в некоторый момент объединиться. Если один из них отрезок, а другой — преграда, то они могут пересечься. В остальных случаях ничего добавлять не надо. Также заметим, что все отрезки необходимо хранить лениво. То есть изменять их размер, а также пересчитывать общее количество достижимых клеток, необходимо только тогда, когда происходит некоторое событие, которое затрагивает данный отрезок.Время работы решения — O (n log (n)), где n — общее число преград.
Видеоразбор:
[embedded content]
