Неофициальный разбор + обсуждение длинного тура Открытой олимпиады 2023
Разница между ru3 и ru4, 0 символ(ов) изменены
Привет, Codeforces! На днях закончился длинный тур Открытой олимпиады этого года, который проходил с 21.11 по 15.01. В нём было много интересных задач, которые мне хотелось бы разобрать и обсудить в этом посте.↵

Я постараюсь описать свои мысли в ходе решения как можно подробнее, но я не гарантирую, что начинающим спортпрогерам всё будет понятно ;)↵

Собственно, ниже мои решения + реализации (прощу прощения, если код трудночитаем):↵

<spoiler summary="А на 100 баллов">↵
Заметим тот факт, что для любого $1 < i \le n$ будет выполняться $max(p_{0:i}) \ge i$. Назовём _хорошей позицией_ такое $i$, что $max(p_{0:i}) = i$.↵

Понятно, что если закончить очередной подотрезок не на _хорошей позиции_, то само число $i$ не войдет в этот подотрезок -> оно точно встретится в результирующей перестановке позже $max(p_{0:i})$, противоречие.↵
То есть, концы отрезков могут совпадать только с _хорошими позициями_ -> перестановку можно разбить на $k$ отрезков с необходимым свойством только тогда, когда количество _хороших позиций_ в этой перестановке $\ge k$.↵
Построение ответа достаточно тривиально &mdash; сделаем концами отрезков $k$ последних хороших позиций.↵

Асимптотика: $O(n)$.↵

Код: https://pastebin.com/05P67xen↵
</spoiler>↵

<spoiler summary="B на 76 (100?) баллов">↵
Условие задачи можно переформулировать так &mdash; найти количество чисел $\le a_i$, таких, что сумма двух соседних цифр в их записи не превышает $10$. К этому можно придти кукареком (перебирая первые числа и находя закономерности) или через математику.↵

В любом случае, переформулированную задачу можно решать с помощью ДП по цифрам, а именно по первой половине записи числа (потому что вторая половина будет зеркальна первой). Состоянием будет последняя рассмотренная позиция и цифра, которую на неё записали.↵

Асимптотика: $O(log_{10}(a_i))$ для одного запроса.↵

Код: https://pastebin.com/YrtJRZMG↵
</spoiler>↵

<spoiler summary="C на 47 баллов">↵
В решениях ниже я буду считать, что $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 &mdash; 1)$↵

- $v$ не является продолжением $u$ -> обновим ответ для копии $v$ с весом $w_v$↵

Можем и здесь запустить Дейкстру, но нужно сделать важную оптимизацию, не перебирая те ребра, которые точно не можем прорелаксировать. А именно, если находясь в ребре $v$, мы не можем прорелаксировать хотя бы одно ребро, в которое можно придти из $v$ и которое не его продолжение, то мы аналогично не сможем прорелаксировать другие не-продолжения ребра $v$.↵

Асимптотика: $O(m * max(w) * log(m))$.↵

Код: https://pastebin.com/FXeBHdp1↵
</spoiler>↵

<spoiler summary="D на 100 баллов">↵
В этой задаче существует масса вариаций с решениями на сетах, но я рассмотрю не совсем обычное, но более простое для меня решение с использованием техники _Segment Tree Beats_.↵

Будем считать, что какая-то позиция обновлена в момент времени $x$, если после $x$-ой операции на ней появился снег, до $x$-ой операции на ней не было снега, и если этот снег не убрали до текущей операции. Если на позиции сейчас нет снега, то можно считать, что эта позиция была обновлена в момент $INF$.↵

Будем хранить дерево отрезков с тремя параметрами для каждой вершины: _min_prev_time_, _max_prev_time_ и _total_time_, где _min_prev_time_ &mdash; минимальный момент времени, в который обновили какую-то позицию на отрезке; _max_prev_time_ &mdash; аналогично предыдущему, но на максимум; _total_time_ &mdash; сумма всех _total_time_ на этом отрезке.↵

Если операция в момент времени $t$ имеет тип +, делаем min= $t$ для всех позиций с $l$ по $r$.↵

Если операция в момент времени $t$ имеет тип -, делаем _total_time_ += $t$ &mdash; _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_.↵

Строгого доказательства времени работы не будет, потому что не силён в методе потенциалов :( Буду очень рад, если кто-то в комментариях найдёт асимптотику данного решения.↵

Код: https://pastebin.com/wy0REYfb↵
</spoiler>↵

<spoiler summary="E на 67 (100?) баллов">↵
В этой задаче можно сделать корневую декомпозицию с идеей разбиения объектов по тяжести.↵

Скажем, что число $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))$.↵

Код: https://pastebin.com/mtazYBZW↵
</spoiler>↵

<spoiler summary="F на 76 (100?) баллов">↵
Первые 4 группы достаточно легко сдаются склейкой различных простых идей, мы же приступим сразу к 5 группе.↵

Есть один интересный способ проверки на то, является ли отрезок статической строки ПСП. А именно, если посчитать стеки для всех префиксов строки, то $[l; r]$ будет являться ПСП тогда и только тогда, когда стеки для префиксов $[0; l - 1]$ и $[0; r]$ равны. Разумеется, сравнивать стеки поэлементно очень долго, поэтому захешируем их.↵

Получаем решение для 5 группы, которое работает за $O(n + q)$.↵

В 6 группе всё уже не так просто, поскольку появляются изменения в точке. Если мы хотим и дальше использовать хеширование в решении, то полиномальное нам точно не подойдет, поскольку наше хеширование должно быть ассоциативным (чтобы не считать хеш поэлементно) и некоммутативно (чтобы порядок элементов имел значение). Вспоминаем, что умножение матриц выполняет оба этих свойства! ↵

Значит, можно каждой открытой скобке сопоставить матрицу 2x2 из случайных чисел от $0$ до $MOD - 1$, а каждой закрытой скобке &mdash; матрицу, обратную матрице открытой скобки такого же типа. В таком случае, если подотрезок является ПСП, то произведение матриц на нём является единичной матрицей.↵

Чтобы добавить обновления в точке, построим дерево отрезков с операцией умножения матриц, обновление в таком случае делается тривиально.↵

Взломать такой хеш невероятно трудно (поскольку существует порядка $MOD^(d^2) / 2$ различных пар матриц (где $d$ &mdash; сторона матрицы), произведение которых равно единичной матрице, причем каждая матрица имеет только одну матрицу-пару).↵

Итоговая асимптотика: $O(d^3 * n * log(n))$, где $d$ &mdash; выбранный размер матрицы для хеширования.↵

Код: https://pastebin.com/r71qkqzT↵
</spoiler>↵

<spoiler summary="G на 100 баллов">↵
Определим ПСП немного иначе: ПСП называется такая строка, что для любого $0 \le i < n$ на суффиксе $[i:n]$ находится ровно $(n - i) / 2$ открытых скобок (поскольку при большем или меньшем количестве не будет подходящего баланса).↵

Из этого определения гораздо легче вывести жадное решение задачи.↵

Будем рассматривать все позиции по уменьшению их стоимости и параллельно для каждой позиции хранить количество открытых скобок, которое мы можем поставить на суффиксе этой позиции. Если текущая позиция &mdash; p и на префиксе $[0:p + 1]$ мы в любую позицию ещё можем поставить одну открытую скобку, сделаем это и обновим количества на префиксе. Если же не можем сделать, то переходим к следующей позиции.↵

Для поддерживания количеств открытых скобок, которые можем поставить на суффиксе, удобнее всего использовать дерево отрезков на массовые операции. Получаем решение с асимптотикой $O(n log n)$.↵

Получившееся решение отдалённо напоминает алгоритм построение миностова. Однако, я не умею строго доказывать корректность этого алгоритма, то есть это кукарек (впрочем, как и в большинстве жадных решений ;)).↵

Код: https://pastebin.com/fHn6Nt2S↵
</spoiler>↵

<spoiler summary="H на 79 (100?) баллов">↵
Переформулируем задачу в более формальный вид. Обозначим за $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)$.↵

Код: https://pastebin.com/HTC0WgSf↵
</spoiler>↵

<spoiler summary="I на 82 балла + некоторые идеи на 100 баллов">↵
Пусть pr &mdash; массив простых чисел, где $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 баллов. ↵

Вышеописанной идеей со мной поделился [user:grishared,2023-01-16], за что я ему крайне признателен.↵

Код: https://pastebin.com/LzZNhtJq↵
</spoiler>↵

Спасибо за внимание!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru9 Русский tiom4eg 2023-01-16 19:12:36 6 Мелкая правка: 'r) + 1, a_{r - 1} - a_l)$ (' -> 'r) + 1, a_r - a_l)$ ('
ru8 Русский tiom4eg 2023-01-16 14:51:17 24 Мелкая правка: 'ллов. \n\nВышеописанной идеей со мной п' -> 'ллов. \n\nИдеями на 100 со мной п'
ru7 Русский tiom4eg 2023-01-16 14:49:14 210
ru6 Русский tiom4eg 2023-01-16 13:54:46 14 мелкая правка
ru5 Русский tiom4eg 2023-01-16 13:49:46 11
ru4 Русский tiom4eg 2023-01-16 13:47:07 0 (опубликовано)
ru3 Русский tiom4eg 2023-01-16 13:33:50 598 Мелкая правка: 'го $1 < i <= n$ будет ' -> 'го $1 < i \le n$ будет '
ru2 Русский tiom4eg 2023-01-16 12:56:41 3461
ru1 Русский tiom4eg 2023-01-16 11:06:55 9003 Первая редакция (сохранено в черновиках)