7. Придорожная оптимизация
Для каждого теста нужно вывести число рёбер в лесе: количество вершин — число компонент связности. Поскольку в условии дана матрица достижимости (уже транзитивно замкнутая матрица смежности), то ответ можно найти проходом по матрице. Например, посмотреть на значения в позиции i, j над главной диагональю: если стоит 1 и индекс j ещё не использован, то увеличить ответ на 1 и пометить индекс j как использованный.
6. Дробь
Задача сводится к тому, что для запроса (знаменателя) $$$X$$$ нужно найти ближайшее $$$X_0$$$ ($$$X_0$$$ >= $$$X$$$) такое, что в системе счисления $$$B$$$ дробь $$$1/X_0$$$ конечная. Введем функцию $$$F(a)$$$ — множество различных простых чисел в факторизации числа $$$a$$$. Тогда, $$$X_0$$$ подходит к ответу, если $$$F(X_0)$$$ является подмножеством $$$F(b)$$$, то есть в разложении $$$X_0$$$ используются только те простые, которые используются в разложении $$$b$$$.
Предпосчитаем для заданного $$$B$$$ всевозможные $$$X_0$$$ в массив $$$V$$$, отсортировать их. Дальше для ответа на запрос нам нужно найти ближайшее число, которое больше или равно числу из запроса. Это можно сделать либо бинарным поиском, либо двумя указателями.
Всевозможные $$$X_0$$$ ищутся рекурсивным перебором. Следует заметить, что нужно аккуратно проверять при домножении на очередное простое, что произведение не превысит $$$M$$$.
5. Починка кучи 32-бит
Заметим, что всегда можно записать в первую и последнюю ячейки N-2, получив правильную кучу с 2 изменениями. Значит надо лишь определить, является ли куча корректной, и можно ли получить корректную за одно изменение.
Запустим два прохода по блокам кучи, предполагая кучу корректной. При проходе вперёд читаем слово из следующей ячейки, и прыгаем вперёд на это число плюс 2. При проходе назад симметрично. Если ошибок нет, тогда оба прохода закончатся за 25K шагов, и блоки будут одинаковые в обе стороны. Если ошибка одна, тогда один проход пройдёт по корректной куче, показав, какими должны быть блоки.
Когда сделаем оба прохода (с ограничением 25К на количество шагов), каждый успешный проход надо провалидировать. То есть проверить размеры с другой стороны — если ошибка только одна, то печатаем решение.
9. Плащ и ружьё
Допустим, мы влетаем в некоторую клетку сверху. Найдём ближайшую к ней клетку с почвой слева и справа. Отрезок между ними является для нас рабочим: мы можем убить всех монстров на нём, и вылететь из отрезка вниз в любой его точке.
Разобъём весь уровень на такие горизонтальные отрезки. Отрезок с буквой S — начальный, с буквой E — конечный. Из произвольного отрезка можно перейти в любой отрезок на следующей горизонтали, который граничит с текущим по стороне хотя бы одной клетки.
Так можно построить граф отрезков: вершины — монстры, рёбра — как можно переходить в следующему отрезку. В каждой вершине запишем количество монтров на отрезке. Нужно найти путь, на котором сумма чисел максимальна. Это легко решается динамическим программированием, т.к. граф без циклов:
- R[s] — какую максимальную сумму можно набрать, пролетев из начала в отрезок s.
Время работы — линейное от площади карты.
10. Остап и стулья
Каждая функция под суммой в зависимости от k и b — выпуклая и кусочно-линейная. Значит и функция полного расстояния будет тоже выпуклой и кусочно-линейной. То есть если её нарисовать как график D(k, b), то это будет низ некоторого выпуклого многогранника. Рёбра многогранника — это линии излома, вдоль которых верно Xi = k * Yi + b. Очевидно, минимум такой функции достигается в какой-то вершине, а любая вершина получается на пересечении двух рёбер.
Получается простое решение за O(N^3): берём все линии Xi = k * Yi + b и пересекаем их попарно, находя точки в (k, b)-плоскости. Делается это очень легко, т.к. никаких параллельностей и совпадений в этой задаче быть не может. Каждую точку проверяем, вычисляя функцию влоб.
Альтернативное решение — написать двумерный тернарный поиск. Грубо и кода больше, но при достаточном количестве итераций работает.
4. Починка кучи 8-бит
Будем решать задачу динамикой:
- R[p] — минимальное количество исправлений, чтобы сделать префикс в p ячеек правильной кучей.
Обозначим массив ячеек памяти через A. Получается рекуррентная формула:
- R[p] = min{x=2..257} (R[p-x] + (A[p-x] != x-2) + (A[p-1] != x-2))
Здесь неравенства в скобках дают единицу, когда они верны, и ноль иначе.
Ускорим решение следующим образом. Нарисуем из каждой ячейки:
- ребро вперёд i -> i + A[i]
- ребро назад i -> i — A[i-1]
Заметим, что при стоимость перехода (p-x -> p) в описанной выше ДП равна: 2 минус количество рёбер между p-x и p. Если между состояниями нет рёбра ни в одну сторону, то стоимость 2. Если ребро есть в обе стороны, то стоимость 0. Если только в одну, то стоимость 1. К счастью, рёбер всего только 2N.
Тогда при вычислении R[p] будем сначала считать минимум, предполагая переходы стоимости 2:
- R[p] = ( min{x=2..257} R[p-x]) + 2 //вычисляется за O(1)
Минимум обновляется за O(1), если хранить в очереди все элементы, которые могут стать минимумом в будущем. Далее будем явно перебирать рёбра из p (оно одно), и рёбра в p (надо заранее сложить развёрнутые рёбра назад), и вычислять переход влоб. Всего таких особенных переходов будет 2 N штук.
Получается решение за O(N). В задаче также требуется использовать мало памяти. Достаточно хранить входные данные, а также обратный ход динамики как массив байтов — это требует 2 N байтов памяти. Все остальные данные можно хранить только для текущего окна из 256-512 элементов, так что затраты памяти на них пренебрежимо малы.
3. Бомбы
Разрешим закладывать сколько угодно бомб перед детонацией. Можно доказать, что тогда минимальное требуемое количество детонаций будет таким же, как минимальное требуемое количество бомб в исходной задаче.
В решении потребуется выполнять операцию, которая в обработке изображений называется dilate. Формулируется она так: допустим есть множество клеток X, в которые мы заложили бомбы. Какие клетки будут затронуты взрывами?
В ходе решения будем поддерживать достижимое множество клеток, постепенно расширяя его. Сначала найдём все достижимые из S клетки (обход по пустым клеткам). Затем заложим в них всех бомбы, и расширим множество с помощью операции dilate. Далее из всех клеток, освобождённых взрывами, снова запустим обход и найдём всё новые достижимые по пустоте клетки. Теперь заложим бомбы во всех клетках, которые освобождены предыдущим взрывом, и в клетках, найденных обходом после этого. Сделаем dilate, далее снова расширим множество по достижимости по пустым клетками, и так далее.
В общем случае, на каждой фазе мы закладываем бомбы во всех клетках, которые достижимы, и в которых не закладывали бомбу раньше. После этого запускаем поиск новых достижимых клеток, причём запускаем его только из тех клеток, которые были освобождены от земли последним взрывом. Благодаря этому в каждой клетке бомба закладывается не более одного раза, а обход по пустым клеткам запускается максимум один раз. В таком виде решение работает за O(M N * R^2), и большую часть времени съедает операция dilate.
Благодаря специальной форме взрыва, можно выполнить операцию dilate быстрее, разбив её на несколько шагов. Допустим, бомбы заложили в множестве X. Тогда можно заметить, что множество затронутых взрывом клеток — это все клетки, достижимые из X после:
- R переходов первого типа (переход разрешён в соседнюю по стороне клетку) и
- P/2 переходов второго типа (переход разрешён в любую из восьми соседних клеток)
Поэтому при выполнении операции dilate в алгоритме можно делать R + P/2 шагов. После каждого шага будет "волна" новых достижимых клеток — как в "волновом" алгоритме, который иногда рассказывают вместо аналогичного BFS.
Изначально есть волна X — те клетки, где мы заложили бомбу. На каждом шаге мы перебираем все клетки последней волны, и просматриваем их соседей нужного типа. Если соседняя клетка ещё не достижима в алгоритме, тогда помечаем её как достижимую и добавляем в следующую волну. За R + P/2 таких шагов мы расширим достижимое множество на общую область взрыва.
Заметим, что в таком алгоритме каждая клетка просматривается O(1) раз. Тогда общее время работы O(M N).
8. Деревянный трубопровод
Если c(f) — минимальная стоимость потока размера f в сети, то известно, что c(f) — некоторая выпуклая кусочно-линейная функция. Мы будем запускать обычную динамику по дереву, и для каждого v-поддерева вычислять функцию c(f) для потока из корня поддерева v в листья поддерева.
Раз c(f) является ломаной (выходящей из начала координат), будем хранить её как ломаную. Чтобы это работало быстро, будем хранить последовательность отрезков (в порядке слева направо). Для каждого отрезка будем хранить:
- "длину" отрезка вдоль координаты f (т.е. вдоль оси абсцисс)
- "наклон" — т.е. производную dc/df вдоль отрезка
Более того, будем хранить эти отрезки в дереве поиска, ключ = наклон.
Чтобы пересчитывать динамику, надо уметь делать две вещи.
- Если известна функция c(f) для v-поддерева, надо уметь добавлять ребро vp, идущее из корня наверх. Для этого нужно сначала обрезать c(f) по capacity(pv) — больше поток быть никак не может. Это делается выбрасыванием всех вершин с бОльшим f, и добавлением вершины с f = capacity(pv) с бесконечным наклоном. Далее надо прибавить к функции c(f) линейную функцию cost(pv) * f — это делается добавлением cost(pv) к наклону всех вершин.
- Если известна функция c(f) для двух поддеревьев с общим корнем v, нужно суметь их объединить. Легко заметить, что результат можно получив, слив две функции c(f) как упорядоченные последовательности (сравнивая по наклону), однако это медленно. Вместо этого, надо взять функцию с меньшим количеством отрезков, и вставить все её отрезки по одному в бОльшую функцию.
Как добавлять сразу к наклонам всех отрезков дерева? Видимо, достаточно хранить одно значение "добавка к наклону всех отрезков" вместе с каждым деревом.
Изменение 1 делается за O(K log N), где K — количество удалённых вершин. Заметим, что вершины добавляются только при обрезании по проп. способности ребра, это делается N-1 раз. Значит в сумме это даёт O(N log N). Изменение 2 делается за O(A log B), где A — меньший размер, а B — больший размер при слиянии. Известно, что в таком случае по всему дереву будет время O(N log^2 N).
Альтернативное решение — найти всё, что нужно, методом дополняющих путей — как обычно. Каждый дополняющий путь идёт из корня в лист. Можно их все выписать, отсортировать по стоимости, брать по одному и проталкивать.
Чтобы протолкнуть по пути, надо:
- Найти минимум проп. способностей рёбер от листа до корня.
- Вычесть из всех проп. способностей рёбер от листа до корня заданное число (найденное в п.1).
Это можно сделать с помощью heavy/light декомпозиции. На каждом heavy-отрезке надо хранить дерево отрезков на минимум с возможностью прибавления на отрезке. Получается тоже O(N log^2 N)
