Разбор задач четвертого квалификационного раунда Russian Code Cup 2014

В воскресенье, 1 июня, прошел четвертый, заключительный, квалификационный раунд Russian Code Cup 2014.

На участие в раунде зарегистрировалось 5428 человек. Как минимум одно решение прислали 730 участников. Всего за раунд было прислано 4793 решения, из них правильных — 1531.

Больше всего решений на GNU C++ — 1786.
Решений на Python — 307, из них правильных 86.
Решений на PHP — 93, из них правильных 15.
Решений на Perl — 6, из них правильных 2.

Первым задачу А решил Филиппов Дмитрий (DimaPhil) за 2:42 минуты, он же первым решил и задачу В за 12:09. Задачи С и D первым решил Обедников Александр (AOb) на 12:25 и 37:44 минуте соответственно. Первым задачу Е решил Фефер Иван (Fefer.Ivan) на 45:22 минуте. Иван также первым справился со всеми задачами за 1 час 8 минут. Всего 5 задач решило 12 человек. 10 участников были дисквалифицированы судьями.

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

Задача А. Соцопрос
Идея: Андрей Станкевич
Реализация: Николай Ведерников
Разбор: Николай Ведерников

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

Так как по условию задачи её решат только те, кому она не противна и умеют решать, то количество тех, кто попытается решить задачу, будет равен или менее n−b. То есть если среди всех, кто попытается решить задачу, будут те, кто это умеет, то это будет максимум из тех, кто решит. Это min(a, n−b).

Минимум же достигается, если все, кому противна задача, будут уметь решать задачу, тогда ответ max(0, a−b).

Задача B. Сто
Идея: Виталий Аксёнов
Реализация: Павел Кротков
Разбор: Павел Кротков

Решением задачи является программа, аккуратно рассматривающая несколько несложных случаев. Самым простым случаем является ситуация, когда количество цифр в числе x равно k+1. В этом случае необходимо вывести −1, если число не содержит ни одного нуля, и ноль — если в числе присутствует хотя бы один ноль.

Если же количество чисел в числе x превышает k хотя бы на три, эту ситуацию необходимо обрабатывать более аккуратно. Найдем в числе второй ноль с конца. Убедимся, что за ним стоит не более, чем k+1 цифра. Вычеркнем из числа все ненулевые цифры, стоящие за вторым с конца нулем, а также вычеркнем необходимое количество цифр, стоящих сразу перед вторым с конца нулем. Заметим, что первая цифра никогда не вычеркивается, а значит, в итоговом числе не будет ведущих нулей.

Важно было не забыть о том, что операция вычеркивания цифры не должна выполняться за длину числа — решения с такой ошибкой получили превышение предела времени на третьем тесте.

Задача C. Поход в гости
Идея: Георгий Корнеев
Реализация: Борис Минаев
Разбор: Борис Минаев

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

Задача D. СНМ
Идея: Артем Васильев
Реализация: Артем Васильев
Разбор: Артем Васильев

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

Хоть массив rank и не задавался во входных данных, легко понять, что без сжатия путей rank_i — это высота поддерева с вершиной i в корне. Также отметим, что алгоритм устроен так, что rank_i каждый раз увеличивается не более, чем на единицу, а после того, как вершина подвешивается к другой, ее parent и rank не изменяются, поэтому можно строить от листьев к корню.

Рассмотрим поддерево с корнем в вершине u. Если rank_u = r, то у вершины u должны существовать дети с рангом 0, 1, ..., r-1. Легко показать, что это условие является достаточным: если провести операции union в порядке увеличения ранга сына, все операции пройдут корректно.

Отсюда следует решение для одного дерева:

1. Рекурсивно построим решение для всех детей корня дерева.
2. Проверим, что для всех h от 0 до rank_root — 1 существует сын с рангом h.
3. Проделаем операции union(root, child_i) в порядке увеличения ранга child_i.

Также возможно реализовать СНМ и непосредственно проделать все операции, проверив, что получившийся массив parent совпал с нужным.

Время работы решения — O(n log (n)).

Задача E. Нанороботы
Идея: Виталий Аксёнов
Реализация: Андрей Комаров
Разбор: Андрей Комаров

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

Будем решать эту задачу при помощи динамического программирования. Обозначим за dp[w][x][y] минимальное число шагов, за которое можно довести робота массой w из клетки (x, y) до финальной клетки (n, m). Начальные значения dp[w][n][m] = 0 говорят о том, что из целевой клетки идти никуда не надо. После того, как dp будет посчитано, ответ будет содержаться в ячейке dp[w][1][1].

Научимся считать dp. Чтобы посчитать dp[w][i][j], сделаем одно из двух:

• Дойдём до финиша, не разбивая робота на части. Для этого, с помощью обхода в глубину, найдём кратчайший путь до финиша по выдерживающим клеткам.
• Либо дойдём до какой-то клетки, разобьёмся на две части и дойдём ими оттуда.

Чтобы не было проблем с пониманием того, в каком порядке считать значения динамики, можно считать её лениво. Итоговая сложность алгоритма: O(w²n²m²).