Привет, Codeforces! На днях закончился длинный тур Открытой олимпиады этого года, который проходил с 21.11 по 15.01. В нём было много интересных задач, которые мне хотелось бы разобрать и обсудить в этом посте.
Я постараюсь описать свои мысли в ходе решения как можно подробнее, но я не гарантирую, что начинающим спортпрогерам всё будет понятно ;)
Собственно, ниже мои решения + реализации (прощу прощения, если код трудночитаем):
Заметим тот факт, что для любого 1 < i <= n будет выполняться max(p[0:i]) >= i. Назовём "хорошей позицией" такое i, что max(p[0:i]) = i.
Понятно, что если закончить очередной подотрезок не на хорошей позиции, то само число i не войдет в этот подотрезок -> оно точно встретится в результирующей перестановке позже max(p[0:i]), противоречие. То есть, концы отрезков могут совпадать только с хорошими позициями -> перестановку можно разбить на k отрезков с необходимым свойством только тогда, когда количество хороших позиций в этой перестановке >= k. Построение ответа достаточно тривиально — сделаем концами отрезков k последних хороших позиций.
Асимптотика — O(n).
Условие задачи можно переформулировать так — найти количество чисел <= a[i], таких, что сумма двух соседних цифр в их записи не превышает 10. К этому можно придти кукареком (перебирая первые числа и находя закономерности) или через математику.
В любом случае, переформулированную задачу можно решать с помощью ДП по цифрам, а именно по первой половине записи числа (потому что вторая половина будет зеркальна первой). Состоянием будет последняя рассмотренная позиция и цифра, которую на неё записали.
Асимптотика: O(log10(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 является тяжелым, если оно встречается >= 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, а каждой закрытой скобке — матрицу, обратную матрице открытой скобки такого же типа. В таком случае, если подотрезок является ПСП, то произведение матриц на нём является единичной матрицей.
Чтобы добавить обновления в точке, построим дерево отрезков с операцией умножения матриц, обновление в таком случае делается тривиально.
Взломать такой хеш невероятно трудно (поскольку существует порядка MOD^(d^2) / 2 различных пар матриц (где d — сторона матрицы), произведение которых равно единичной матрице, причем каждая матрица имеет только одну матрицу-пару).
Итоговая асимптотика: O(d^3 * n * log(n)), где d — выбранный размер матрицы для хеширования.
Определим ПСП немного иначе: ПСП называется такая строка, что для любого 0 <= i < n на суффиксе [i:n] находится ровно (n — i) / 2 открытых скобок (поскольку при большем или меньшем количестве не будет подходящего баланса).
Из этого определения гораздо легче вывести жадное решение задачи.
Будем рассматривать все позиции по уменьшению их стоимости и параллельно для каждой позиции хранить количество открытых скобок, которое мы можем поставить на суффиксе этой позиции. Если текущая позиция — p и на префиксе [0:p + 1] мы в любую позицию ещё можем поставить одну открытую скобку, сделаем это и обновим количества на префиксе. Если же не можем сделать, то переходим к следующей позиции.
Для поддерживания количеств открытых скобок, которые можем поставить на суффиксе, удобнее всего использовать дерево отрезков на массовые операции. Получаем решение с асимптотикой O(n log n).
Получившееся решение отдалённо напоминает алгоритм построение миностова. Однако, я не умею строго доказывать корректность этого алгоритма, то есть это кукарек (впрочем, как и в большинстве жадных решений ;)).
Переформулируем задачу в более формальный вид. Обозначим за f(l, r) ответ для отрезка [l; r]. В таком случае, если a[l] != 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] != 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_prb).
Далее можно заметить, что значения f(n, b) при достаточно маленьких (<= 2000000) n будут использоваться очень часто, поэтому эти значения можно запомнить в массиве и не пересчитывать много раз. Помимо этого, для b <= 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 баллов.
Вышеописанной идеей со мной поделился grishared, за что я ему крайне признателен.
