Pull to refresh
VK
Building the Internet

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

Reading time 4 min
Views 6.6K


В воскресенье, 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 участникам задача противна.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Также возможно реализовать СНМ и непосредственно проделать все операции, проверив, что получившийся массив 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(w2n2m2).
Tags:
Hubs:
+22
Comments 7
Comments Comments 7

Articles

Information

Website
vk.com
Registered
Founded
Employees
5,001–10,000 employees
Location
Россия
Representative
Миша Берггрен