Задача А. Соцопрос.

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

В задаче требуется найти минимальное и макимальное возможное количество участников, которые решат задачу. Если всего участников 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 в порядке увеличения ранга сына, все операции пройдут корректно.

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

• Рекурсивно построим решение для всех детей корня дерева.
• Проверим, что для всех h от 0 до rank_root — 1 существует сын с рангом h.
• Проделаем операции 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²).