Разбор задач четвертого квалификационного раунда 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 и не задавался во входных данных, легко понять, что без сжатия путей ranki — это высота поддерева с вершиной i в корне. Также отметим, что алгоритм устроен так, что ranki каждый раз увеличивается не более, чем на единицу, а после того, как вершина подвешивается к другой, ее parent и rank не изменяются, поэтому можно строить от листьев к корню.
Рассмотрим поддерево с корнем в вершине u. Если ranku = r, то у вершины u должны существовать дети с рангом 0, 1, …, r-1. Легко показать, что это условие является достаточным: если провести операции union в порядке увеличения ранга сына, все операции пройдут корректно.
Отсюда следует решение для одного дерева:
Рекурсивно построим решение для всех детей корня дерева. Проверим, что для всех h от 0 до rankroot — 1 существует сын с рангом h. Проделаем операции 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).
