Задача А. Соцопрос.
Идея: Андрей Станкевич.
Реализация: Николай Ведерников.
Разбор: Николай Ведерников.
В задаче требуется найти минимальное и макимальное возможное количество участников, которые решат задачу. Если всего участников 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.
Время работы решения — 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], сделаем одно из двух:
- Дойдём до финиша, не разбивая робота на части. Для этого, с помощью обхода в глубину, найдём кратчайший путь до финиша по выдерживающим клеткам.
- Либо, дойдём до какой-то клетки, разобъёмся на две части и дойдём ими оттуда.