Привет, Codeforces!
Вчера закончился длинный тур Открытой олимпиады этого года, который проходил с 21.11 по 15.01. В нём было много интересных задач, которые мне хотелось бы разобрать и обсудить в этом посте.
Я постараюсь описать свои мысли в ходе решения как можно подробнее, но я не гарантирую, что начинающим спортпрогерам всё будет понятно ;)
Собственно, ниже мои решения + реализации (прощу прощения, если код трудночитаем):
Заметим тот факт, что для любого $$$1 < i \le n$$$ будет выполняться $$$max(p_{0:i}) \ge i$$$. Назовём хорошей позицией такое $$$i$$$, что $$$max(p_{0:i}) = i$$$.
Понятно, что если закончить очередной подотрезок не на хорошей позиции, то само число $$$i$$$ не войдет в этот подотрезок -> оно точно встретится в результирующей перестановке позже $$$max(p_{0:i})$$$, противоречие. То есть, концы отрезков могут совпадать только с хорошими позициями -> перестановку можно разбить на $$$k$$$ отрезков с необходимым свойством только тогда, когда количество хороших позиций в этой перестановке $$$\ge k$$$. Построение ответа достаточно тривиально — сделаем концами отрезков $$$k$$$ последних хороших позиций.
Асимптотика: $$$O(n)$$$.
Условие задачи можно переформулировать так — найти количество чисел $$$\le a_i$$$, таких, что сумма двух соседних цифр в их записи не превышает $$$10$$$. К этому можно придти кукареком (перебирая первые числа и находя закономерности) или через математику.
В любом случае, переформулированную задачу можно решать с помощью ДП по цифрам, а именно по первой половине записи числа (потому что вторая половина будет зеркальна первой). Состоянием будет последняя рассмотренная позиция и цифра, которую на неё записали.
Асимптотика: $$$O(log_{10}(a_i))$$$ для одного запроса.
В решениях ниже я буду считать, что $$$n = m$$$, поскольку в максимальных тестах это действительно так.
Разобьём решение на 4 части: для групп 1-2, для группы 3, для группы 4 и для групп 4-5.
Группы 1-2: запустим алгоритм Дейкстры на графе. На каждой итерации переберём ребро, исходящее из вершины, и если у него есть продолжение, то прорелаксируем все рёбра, достижимые из текущего по продолжениям. Иначе, релаксируем только рассмотренное ребро.
Асимптотика: вроде бы $$$O(n^2 log n)$$$, но я не умею строго пруфать это.
Группа 3: то же решение, что и для групп 1-2, но поскольку в этой группе рёбра не имеют продолжений, прийти к этому решению гораздо проще + асимптотика лучше.
Асимптотика: $$$O(m log n)$$$.
Группа 4: в этой группе можно написать 0-1 BFS (поскольку все ребра будут иметь вес либо 0, либо 1) или решение для группы 5.
Асимптотика решения с 0-1 BFS: $$$O(n + m)$$$.
Группа 5: представим, что вместо каждого ребра $$$v$$$ у нас есть $$$max(w) + 1$$$ его копий с весами от $$$0$$$ до $$$max(w)$$$. В таком случае, если приходим в $$$v$$$ из копии ребра $$$u$$$ с весом $$$x$$$, то:
$$$v$$$ является продолжением $$$u$$$ -> обновим ответ для копии $$$v$$$ с весом $$$max(0, x — 1)$$$
$$$v$$$ не является продолжением $$$u$$$ -> обновим ответ для копии $$$v$$$ с весом $$$w_v$$$
Можем и здесь запустить Дейкстру, но нужно сделать важную оптимизацию, не перебирая те ребра, которые точно не можем прорелаксировать. А именно, если находясь в ребре $$$v$$$, мы не можем прорелаксировать хотя бы одно ребро, в которое можно придти из $$$v$$$ и которое не его продолжение, то мы аналогично не сможем прорелаксировать другие не-продолжения ребра $$$v$$$.
Асимптотика: $$$O(m * max(w) * log(m))$$$.
В этой задаче существует масса вариаций с решениями на сетах, но я рассмотрю не совсем обычное, но более простое для меня решение с использованием техники Segment Tree Beats.
Будем считать, что какая-то позиция обновлена в момент времени $$$x$$$, если после $$$x$$$-ой операции на ней появился снег, до $$$x$$$-ой операции на ней не было снега, и если этот снег не убрали до текущей операции. Если на позиции сейчас нет снега, то можно считать, что эта позиция была обновлена в момент $$$INF$$$.
Будем хранить дерево отрезков с тремя параметрами для каждой вершины: min_prev_time, max_prev_time и total_time, где min_prev_time — минимальный момент времени, в который обновили какую-то позицию на отрезке; max_prev_time — аналогично предыдущему, но на максимум; total_time — сумма всех total_time на этом отрезке.
Если операция в момент времени $$$t$$$ имеет тип +, делаем min= $$$t$$$ для всех позиций с $$$l$$$ по $$$r$$$.
Если операция в момент времени $$$t$$$ имеет тип -, делаем total_time += $$$t$$$ — prev_time и prev_time = $$$INF$$$ для всех позиций с $$$l$$$ по $$$r$$$.
Теперь определимся, какие-же tag/break условия нужно взять. Понятно, что делать min= $$$x$$$ на отрезке, на котором максимум меньше $$$x$$$, не имеет смысла, поэтому break-condition для операции +: max_prev_time < $$$x$$$. Аналогично, tag-condition: min_prev_time > $$$x$$$.
Break-condition для операции -: min_prev_time == $$$INF$$$, tag-condition: min_prev_time == max_prev_time.
Строгого доказательства времени работы не будет, потому что не силён в методе потенциалов :( Буду очень рад, если кто-то в комментариях найдёт асимптотику данного решения.
В этой задаче можно сделать корневую декомпозицию с идеей разбиения объектов по тяжести.
Скажем, что число $$$x$$$ является тяжелым, если оно встречается $$$\ge k$$$ раз в массиве. Отсюда понятно, что тяжёлых чисел не больше $$$n / k$$$.
Предподсчитаем ответ для всех различных пар чисел в массиве, в которых есть хотя бы одно тяжелое число. Понятно, что таких пар будет не больше $$$n * (n / k)$$$. Это можно сделать одним проходом по массиву, храня для каждого тяжелого числа количество уже рассмотренных его копий. Асимптотика: $$$O(n * (n / k))$$$.
После предподсчета начнем обрабатывать запросы. Если в текущем запросе нет ни одного тяжелого числа, можно найти ответ методом указателей за $$$O(k)$$$. Иначе, мы уже посчитали ответ в предподсчете.
Таким образом, получаем сложность решения $$$O(n * (n / k) + q * k)$$$. Если предположить, что $$$n = q$$$, то выгоднее всего будет взять $$$k = \sqrt{n}$$$, получим $$$O((n + q) * sqrt(n))$$$.
Первые 4 группы достаточно легко сдаются склейкой различных простых идей, мы же приступим сразу к 5 группе.
Есть один интересный способ проверки на то, является ли отрезок статической строки ПСП. А именно, если посчитать стеки для всех префиксов строки, то $$$[l; r]$$$ будет являться ПСП тогда и только тогда, когда стеки для префиксов $$$[0; l - 1]$$$ и $$$[0; r]$$$ равны. Разумеется, сравнивать стеки поэлементно очень долго, поэтому захешируем их.
Получаем решение для 5 группы, которое работает за $$$O(n + q)$$$.
В 6 группе всё уже не так просто, поскольку появляются изменения в точке. Если мы хотим и дальше использовать хеширование в решении, то полиномальное нам точно не подойдет, поскольку наше хеширование должно быть ассоциативным (чтобы не считать хеш поэлементно) и некоммутативно (чтобы порядок элементов имел значение). Вспоминаем, что умножение матриц выполняет оба этих свойства!
Значит, можно каждой открытой скобке сопоставить матрицу 2x2 из случайных чисел от $$$0$$$ до $$$MOD - 1$$$, а каждой закрытой скобке — матрицу, обратную матрице открытой скобки такого же типа. В таком случае, если подотрезок является ПСП, то произведение матриц на нём является единичной матрицей.
Чтобы добавить обновления в точке, построим дерево отрезков с операцией умножения матриц, обновление в таком случае делается тривиально.
Взломать такой хеш гораздо труднее, чем полиномиальный хеш, поэтому матрицы 2x2 будет достаточно.
Итоговая асимптотика: $$$O(d^3 * n * log(n))$$$, где $$$d$$$ — выбранный размер матрицы для хеширования.
Определим ПСП немного иначе: ПСП называется такая строка, что для любого $$$0 \le i < n$$$ на суффиксе $$$[i:n]$$$ находится ровно $$$(n - i) / 2$$$ открытых скобок (поскольку при большем или меньшем количестве не будет подходящего баланса).
Из этого определения гораздо легче вывести жадное решение задачи.
Будем рассматривать все позиции по уменьшению их стоимости и параллельно для каждой позиции хранить количество открытых скобок, которое мы можем поставить на суффиксе этой позиции. Если текущая позиция — p и на префиксе $$$[0:p + 1]$$$ мы в любую позицию ещё можем поставить одну открытую скобку, сделаем это и обновим количества на префиксе. Если же не можем сделать, то переходим к следующей позиции.
Для поддерживания количеств открытых скобок, которые можем поставить на суффиксе, удобнее всего использовать дерево отрезков на массовые операции. Получаем решение с асимптотикой $$$O(n log n)$$$.
Получившееся решение отдалённо напоминает алгоритм построение миностова. Однако, я не умею строго доказывать корректность этого алгоритма, то есть это кукарек (впрочем, как и в большинстве жадных решений ;)).
Переформулируем задачу в более формальный вид. Обозначим за $$$f(l, r)$$$ ответ для отрезка $$$[l; r]$$$. В таком случае, если $$$a_l \ne a_r$$$, нетрудно доказать, что $$$f(l, r) = max(f(l + 1, r) + 1, a_{r - 1} - a_l)$$$ (случай $$$a_l == a_r$$$ тривиален).
Эту же формулу можно представить немного в другом виде. Для каждого $$$p$$$ в массиве $$$nx$$$ будем хранить самую правую позицию массива, число на которой равно $$$a_p$$$. Пусть $$$x = nx_l$$$, $$$s = (a_r - a_l) + (nx_l - l)$$$. Пока $$$a_x \ne a_r$$$, будем "прыгать" через блок равных элементов ($$$x = nx_{x + 1}$$$), изменяя текущий баланс (прибавляя разницу между новым и старым значением, вычитая длину блока). В те моменты, когда баланс будет меньше $$$0$$$, будем вычитать его из $$$s$$$ и делать снова равным $$$0$$$. Доказательство корректности перехода от $$$f(l, r)$$$ к этому алгоритму я оставляю читателю.
Итак, у нас уже есть достаточно быстрый алгоритм, который получает 76 баллов. Чтобы получить полный балл, можно заметить, что можно построить прыжки через прыжки через блоки равных чисел. А именно, из каждого момента, в котором у нас нулевой баланс, мы будем прыгать в ближайший момент с отрицательным балансом, обновляя ответ и снова приходя в момент с нулевым балансом.
Однако и этого мало, потому что у нас может быть очень много таких моментов. Поэтому, на новых прыжках мы построим бинапы на сумму, а чтобы построить их, пройдемся по блокам равных элементов с деревом отрезков.
Получившееся решение работает за $$$O((n + q) log n)$$$.
Пусть pr — массив простых чисел, где $$$pr_0 = 2, pr_1 = 3$$$ etc.
Нам нужно найти $$$f(n, b)$$$, где $$$f(x, y) = x$$$ при $$$x < pr_y$$$. Функцию можно вычислять по следующей формуле: $$$f(n, b) = f(n, b - 1) + f(n / pr_b, b - 1) + ... + f(n / (pr_{b}^k), b - 1)$$$, где $$$k = floor(log_{pr_b}(n))$$$.
Далее можно заметить, что значения $$$f(n, b)$$$ при достаточно маленьких ($$$\le 2000000$$$) $$$n$$$ будут использоваться очень часто, поэтому эти значения можно запомнить в массиве и не пересчитывать много раз. Помимо этого, для $$$b \le 8$$$ (или 9) будет не так много различных чисел, которые в разложении содержат множители не больше $$$pr_b$$$ (а именно, порядка пары десятков миллионов), а значит, все эти числа можно также сохранить в отсортированном массиве и при маленьких b вместо запуска функции находить ответ lower_bound-ом к этому массиву).
Совокупность этих идей при аккуратной реализации даёт 82 балла.
Идеи на 100: заметим, что $$$f(n, b) = f(n, b - 1) + f(n / pr_b, b)$$$ (это очевидно вытекает из прошлой формулы), то есть, можно вычислять значения функции не в глубину, а в ширину. Если прикрутить различные оптимизации к стандартному алгоритму BFS, получится решение, которое на максимальном тесте работает около 3.6 секунд, чего достаточно для получения 100 баллов.
Идеями на 100 со мной поделился grishared, за что я ему крайне признателен.
Спасибо за внимание!
