Отборочный раунд Russian Code Cup 2014: итоги и разбор задач

В прошедшее воскресенье состоялся отборочный раунд Russian Code Cup 2014. В нем участвовало 802 программиста, показавшие лучшие результаты в четырех квалификациях. В этом этапе участникам предстояло за 3 часа решить шесть задач, что на один час и на одну задачу больше, чем в квалификационных раундах. Да и задачи были существенно сложнее, чем предыдущие. За время соревнования из 802-х только 444 участника смогли решить хотя бы одну задачу. Всего было отправлено 3271 решения, из них правильных 1402.

Больше всего решений на GNU C++ — 1516.
Решений на Java 7 — 333.
Решений на Java 8 — 106.

Первым задачу A решил Геннадий Короткевич (tourist) за 2:52 минуты. Геннадий так же быстрее всех решил задачи В, С и D на 7:05, 24:29 и 13:05 минутах соответственно. Задачу E первым решил Дмитрий Егоров (Dmitry_Egorov) на 40:59 минуте. Задача F стала одной из самых сложных за всю историю Russian Code Cup — из всех участников ее решили правильно только три человека, и первым задачу F решил победитель RCC 2013 Петр Митричев (Petr) за 2:25:46.

Первым со всеми задачами справился Павел Кунявский (PavelKunyavskiy) за 2 часа 47 минут. Всего 6 задач решило 3 человека, 5 и больше задач решили 100 человек. Последним в заветные top 50 попал Роман Билый (RomaWhite), сдавший пятую задачу через 2 часа 30 минут после начала.

За волю к победе отметим Егора Куликова (Egor), который вошел в топ 50, сдав одну из задач с 7 попытки. А также Петра Митричева (Petr), который, не придумав как решить задачу C, отказался от попыток ее решить, первым решил самую сложную задачу F. А потом, вернувшись к задаче C, сдал ее за 4 минуты до конца и занял в итоге 3 место.

Территориальное распределение участников в этом раунде было следующим:

Россия	515
Украина	112
Беларусь	77
Казахстан	26
США	17
Армения	8
Узбекистан	8
Швейцария	6
Германия	4
Латвия	4
Австрия	2
Болгария	2
Великобритания	2
Грузия	2
Молдова	2
Польша	2
Республика Сингапур	2
Азербайджан	1
Аргентина	1
Ирландия	1
Канада	1
Кипр	1
Литва	1
Республика Корея	1
Словакия	1
Турция	1
Швеция	1
Япония	1

При этом впервые в Russian Code Cup были участники, не знающие русского языка из Австрии, Аргентины и Японии! Как признался один из них, условия задач раунда он переводил через сервисы онлайн перевода.

Борьба в отборочном раунде была напряженной. В итоге в финал вышли 50 сильнейших программистов. Подробно о них мы расскажем позже.

Задача A. Разбор задач

Идея: Анна Малова
Реализация: Андрей Комаров
Разбор: Андрей Комаров

В задаче требуется составить план разбора задач так, чтобы суммарная продолжительность разбора была минимальной. Задачи должны разбираться в порядке с первой до m-й. Время разбора одной задачи составляет t секунд. Замена разбирающего задачу члена жюри — c секунд. Если один и тот же член жюри разбирает несколько задач подряд, то замена не требуется. Про каждого члена жюри известно, какие задачи он хочет разбирать, а какие — нет.

Эта задача решается жадным алгоритмом. Выберем члена жюри, который умеет решать максимальное число задач, начиная с первой. Пусть он умеет решать k задач. Затем, выберем того, кто умеет решать максимальное число задач, начиная с k-й. Будем продолжать так, пока не будут разобраны все задачи. Тогда ответом на задачу будет m · t + q · c, где q — число произведённых замен.

Почему это является оптимальным ответом? Пусть в какой-то момент был выбран член жюри, желающий проводить разбор не максимального числа задач. Тогда, от того, что его заменят на того, кто умеет разбирать больше и дать ему разобрать больше, ответ может только улучшиться.

Данное решение работает за O(n·m).

Также можно было написать простое решение с помощью динамического программирования. dp[i][j] равно минимальному времени, которое тратится, если разобрали i задач и i-ю разбирал j-й член жюри. Данный массив можно легко посчитать за O(n²m).

Задача B. На далекой Амазонке

Идея: Виталий Аксенов
Реализация: Демид Кучеренко
Разбор: Демид Кучеренко

В данной задаче необходимо построить ориентированный граф, состоящий из n вершин, в котором выполняются следующие условия:

• в графе не должно быть циклов;
• в каждую вершину ведёт максимум одно ребро;
• в графе должно быть ровно a вершин, из которых существуют исходящие ребра;
• в графе должно быть ровно b вершин, в которые существуют входящие ребра.

Для начала разберем случаи, когда ответ «IMPOSSIBLE». Это случаи, когда выполняется хотя бы одно из условий:

• матерей больше, чем дочерей;
• матерей больше, чем n-1 (все матерями быть не могут);
• дочерей больше, чем n-1.

Если такой граф возможно построить, то сначала построим цепочку из a ребер. Таким образом у нас будет задействованы a+1 женщина, и будет a матерей и a дочерей. После чего, дополним дочерями любых матерей, чтобы дочерей стало ровно b. Может получиться так, что некоторые женщины не будут ни матерями, ни дочерями, но это не противоречит условию задачи.

Задача C. Лабораторная по физике

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

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

Запишем формулу температуры воды, если мы смешиваем холодную воду из сосуда объёмом c_i и горячую воду из сосуда объёмом h_j: T = p / q = (C·c_i + H·h_j) / (c_i + h_j) Преобразовав эту формулу, получим, что (H·q — p) / (p — C·q) = c_i / h_j Таким образом, мы свели задачу к следующей: задана несократимая дробь и множество числителей и знаменателей, можно ли выбрать числитель и знаменатель так, чтобы получилась заданная дробь?

Введем обозначения A_x — множество всех c_i / x, где c_i делится на x. Аналогично, B_y — множество всех h_i / y, где h_i делится на y. Тогда несократимую дробь p / q можно представить тогда и только тогда, когда A_p и B_q пересекаются. Стоит отметить, что суммарный размер всех множеств A_x и B_y равен O(M log M), где M — ограничение на объем сосудов (в данной задаче M равно 10⁵).

При представлении A_x и B_y в виде отсортированных списков один запрос можно выполнить за O(M / max(x, y)). Если представлять A_x и B_y как битовые множества, то получается решение за O(M / 64) на запрос.

Самое быстрое решение получается, если не считать ответы для одной и той же дроби несколько раз. В этом случае можно доказать более точную оценку на время работы решения. Докажем оценку O((M +k) sqrt(M)), где k — количество запросов. Если максимум из p и q больше, чем sqrt(M), то запрос можно выполнить за O(sqrt(M)), просмотрев все элементы меньшего из множеств. Оценим сумму времен выполнения всех остальных запросов. Запросов, выполняющихся за O(M / x) не больше, чем 2x. Cуммируя по всем x, и учитывая, что x не больше, чем sqrt(M), получаем оценку O((M + k) sqrt(M)) Суммарное время работы решения: O((M + k) sqrt(M)).

Задача D. Конструирование пил

Идея: Николай Ведерников
Реализация: Николай Ведерников
Разбор: Николай Ведерников

В задаче требуется посчитать количество перестановок, таких что:

• a_2·i-1 ≤ a_2·i
• a_2·i ≥ a_{2·i + 1}

Для всех i от 1 до n ⁄ 2. Назовём такую перестановку возрастающей пилообразной.

Заметим, что количество таких перестановок равно количеству перестановок, у которых на нечётных позиция стоят числа, больше своих соседей. Биективное соответствие: b_i = n — a_i. Назовём такую перестановку убывающей пилообразной. Это нам пригодится дальше для решения задачи.

Очевидно, что если длина перестановки равна 0 или 1, то ответ — 1.

Пусть мы знаем ответ для всех длин от 0 до n, найдём ответ для n+1. Будем считать общее количество пилообразных последовательностей. Для того чтобы получить количество возрастающих, нужно общее число последовательностей разделить на 2, так как количество возрастающих равно количеству убывающих.

Пусть n+1 поставили на позицию 2·k, тогда сначала у нас идёт возрастающая пилообразная длиной 2·k−1, а после возрастающая длиной n−2·k+1. На первые 2·k−1 позиций мы можем выбрать любые из n чисел. Итого, получаем, что количество перестановок длины n+1, у которых число n+1 на позиции 2·k: ans_2·k−1 · ans_n−2·k+1 · Binom(n, 2·k−1).

Пусть n+1 поставили на позицию 2·k+1, тогда сначала у нас идёт убывающая пилообразная длиной 2·k, а после возрастающая длиной n−2·k. На первые 2·k позиций мы можем выбрать любые из n чисел. Итого получаем, что количество перестановок длины n+1, у которых число n+1 на позиции 2·k+1: ans_2·k · ans_n−2·k · Binom(n, 2·k).

Итого, общее число пилообразных последовательностей длины n+1: ans_n+1 = ∑ⁿ_{k = 0} ans_k · ans_n−k · Binom(n, k).

Задача E. Зарплата

Идея: Анна Малова
Реализация: Павел Кротков
Разбор: Павел Кротков

В данной задаче дан ориентированный граф. Все ребра можно было классифицировать на три части:

• при любой расстановке окладов и бонусов в вершинах этого ребра условие руководства будет выполняться;
• для выполнения условия руководства необходимо или поменять оклад с бонусом в обеих вершинах этого ребра, или не менять ни на одной;
• для выполнения условия руководства необходимо поменять оклад с бонусом ровно в одной из вершин этого ребра.

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

Для получения минимального количества вершин, в которых нужно поменять местами оклад с бонусом, модифицируем этот поиск в глубину. После обхода и раскраски в два цвета очередной компоненты связности, посчитаем количество вершин (исходного графа, до объединения по ребрам второго типа), раскрашенных в тот и в другой цвет, и, при необходимости, инвертируем раскраску.

Задача F. Робот

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

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

Для начала найдем количество способов добраться из одной клетки в другую без условия, что нельзя посещать конечную клетку раньше последнего хода. Такую задачу можно решать независимо по координатам, а потом перебрать, сколько ходов было совершено по одной координате, а сколько по другой. Как решать задачу в одномерном случае? Пусть изначально робот имеет координату x₁, а в конце должен иметь координату x₂. Пусть a=|x₂-x₁|, а всего было совершено t ходов. Тогда количество различных способов будет равно количеству сочетаний из t по (t-a)/2 (при этом t-a должно быть неотрицательным и четным). Однако нужно учесть, что робот может иметь только положительную координату в процессе путешествия. Для этого необходимо просто вычесть из полученного результата количество способов добраться из клетки -x₁ в x₂. Это справедливо, так как между путями из x₁, которые нарушают требование положительности координаты, а также всеми путями из -x₁ можно показать взаимно однозначное соответствие. Соответствующие друг другу пути будут иметь зеркальные первые части (до момента входа в клетку 0) и общие вторые части.

Вернемся к рассмотрению двумерной задачи. Пусть мы уже посчитали количество способов добраться по каждой координате от одной клетки до другой (для каждой фиксированной длины путешествия). Чтобы посчитать аналогичные значения для двумерной задачи, необходимо перебрать количество времени, которое потрачено на каждую координату, а потом перемножить соответствующие значения в уже посчитанных массивах, а также умножить на количество различных способов выбрать какие именно ходы будут соответствовать каким координатам. Чтобы посчитать эти значения быстро, можно воспользоваться преобразованием Фурье. Чтобы свести задачу к перемножению полиномов, необходимо избавиться от присутствия в формуле количества сочетаний. Для этого распишем его через факториалы. Сгруппировав слагаемые, получим, что можно i-е элементы исходных массивов поделить на i!, перемножить получившиеся полиномы, а потом значение в i-м разряде умножить на i! В задаче модуль, по которому необходимо выполнять все операции, был подобран таким образом, что по нему можно выполнять быстрое преобразование Фурье.

Теперь рассмотрим, как учесть то, что робот не может заходить в конечную клетку до последнего хода. Будем считать ответ с помощью динамического программирования. Пусть уже посчитано количество способов дойти до клетки за меньше чем t ходов. Чтобы посчитать это значения для t ходов, рассмотрим общее количество способов сделать это за t ходов и вычтем из него все способы, которые заходят в конечную клетку до хода t. Для этого переберем номер первого хода, в который робот посетит конечную клетку и умножим соответствующее ему количество способов на количество способов выйти из клетки (x₂, y₂) и вернуться в нее за оставшиеся время. При этом, робот может сколько угодно раз посещать конечную клетку (во второй части).

Заметим, что изложенное решение работает пока за t². Для более быстрого решения следует рассуждать в терминах производящих функций. Обозначим f(x) = f₀ x⁰ + f₁ x¹ +… + f_t x^t + ..., где f_i — ответ не задачу. Аналогично определим count(x) — производящая функция для количества путей, без учета условия первого захода в конечную клетку на последнем ходу, cycle(x) — производящая функция для количества путей из конечной клетки в саму себя. Из рекуррентных соотношения для f_i, можно вывести соотношение на производящие функции: f(x) = count(x) — f(x) cycle(x), откуда f(x) = count(x) / (cycle(x) + 1) = count(x) (cycle(x) + 1)^-1. Для вычисления f необходимо посчитать первые t + 1 членов дроби в правой части. Это можно сделать, вычислив обратный к cycle(x) + 1 многочлен по модулю x^t+1, и перемножив count(x) с результатом. Взятие обратного многочлена по модулю x^t+1 можно выполнить за время O(t log t) с использованием быстрого преобразования Фурье. Итоговое время работы: O(t log t).