Республиканская олимпиада по информатике 2022 года за 11 класс | Казахстанские олимпиады

Задача A. Покраска суммой

Автор разбора : Инкара Сабитова

Отсортируем массив для удобства.

Заметим две вещи:

1. Если в массиве нет положительного числа, это значит что ответ 1. Очевидно что два наибольших элемента невозможно перекрасить в этом случае, а значит единственная раскраска это попытаться перекрасить все $i$ во всех тройках $(i, n - 1, n)$.

2. Если в массиве есть положительное число то в каждой покраске будет только два белых элемента. Это легко доказывается. Пусть у нас остался один положительный элемент, очевидно что если он последний то его не получится перекрасить, так как сумма двух неположительных чисел не может быть больше положительного. Теперь докажем что всегда останется два элемента, возьмём три самых максимальных элемента $(i, j, k)$, выполняется $a_i < a_j < a_k$, $a_k$ обязательно положительный исходя из прошлых выводов, а значит $a_i < a_j + a_k$, а значит мы всегда можем перекрасить $a_i$. А значит мы будем удалять элементы до тех пор пока не останется два элемента.

Давайте узнаем какая пара элементов $l, r$ может остаться, а какая нет.

1. Мы можем удалить все элементы после $r$, это проверяется проверкой условия $a_i > a_{i - 1} + a_{i - 2}$ для всех $i > r$.

2. Мы можем удалить все элементы между $l$ и $r$, это легко проверяется проверкой условия $a_r +a_{i-1} > a_{i}$ => $a_r > a_i - a_{i-1}$ для всех $l < i < r$.

Для решения $O(n^3)$ нам нужно просто перебрать все пары $l$ и $r$ и проверить их в тупую.

Для решения $O(n^2 * log(n))$ или $O(n^2)$ нам нужно просто перебрать все пары $l$ и $r$ и поддерживать результат первой проверки вот так $pd_i = (pd_{i + 1}$ $\&\&$ $a_{i + 1} < a_i + a_{i - 1})$. В $pd_i$ будет храниться можно ли удалить все элементы на суффиксе $i + 1$. Для проверки второго условия достаточно проверить то что минимальное $a_i - a_{i-1}$ на отрезке $(l + 1, r - 1)$ строго меньше $a_r$, минимум на отрезке искать легко.

Для решения $O(n * log^2(n))$ или $O(n * log(n))$ достаточно заметить то что все числа на отрезке $L...(r-1)$ (где $L$ самое левое подходящее $l$) будут подходящими $l$. Так что достаточно найти $L$, это можно сделать бинпоиском в тупую или любым другим способом, особо много времени любое такое решение занимать не должно.

Код : (Ссылка)

Задача B. MEXI

Автор разбора : Инкара Сабитова

Для начала давайте для каждого $x$ будем искать ответ отдельно.

Пусть нам нужно найти $r_1$, легко понять что самое выгодное $r_1$ это самое правое доступное $r_1$, то есть максимальное $r_1$ для которого MEX на отрезке $(1, r_1) \le x$. Понятно что любое значение правее будет нельзя использовать так как MEX на таком отрезке будет уже равен $x$, а брать границу левее просто не выгодно так как этим мы только добавим значений к следующему отрезку что бессмысленно.

Остальные правые границы отрезка можно будет искать аналогично, следовательно мы получаем решение за $O(n^2)$.

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

Для каждого $i$ запомним $a_{i, j}$ - ближайшее вхождение числа $j$ в массиве $a$ после элемента $i$. Теперь для того чтобы получить правую границу достаточно найти максимум среди значений $a_{i, j}$ где $i$ это левая граница из которой мы ищем оптимальную правую, а $j$ это любое число от $0$ до $x - 1$. Если хранить дополнительный массив с максимальными элементами на префиксах то мы сможем находить правую границу за $O(1)$. Время работы решения так и осталось $O(n^2)$ из-за подсчёта массива $a_{i, j}$, однако можно заметить что часть с подсчётом ответов значительно ускорилась. Вспомним что мы всегда выбираем максимальную правую границу, а при $x$ максимальная граница будет находиться как минимум на $x$ элементов правее, правую границу мы находим за $O(1)$, а значит мы суммарно тратим $\sum_{x=0}^{x<n} n/x$ ~ $n*log(n)$. Ну давайте заметим что можно поддерживать $a$ с помощью персистентного ДО, тогда поиск правой границы будет занимать $O(log(n))$, однако кол-во времени на подсчёт $a$ будет $O(nlog(n))$, таким же будет количество используемой памяти.

Теперь у нас есть решение за $O(n * log^2(n))$. Можно сказать что наша программа работает за $\sum_{i = 1}^{i < n}ans_i * log(n)$, до этого мы приняли что $\sum_{i = 1}^{i < n}ans_i$ ~ $nlog(n)$, но на самом деле это ~$n$. Почему? Ну давайте заметим что $ans_i \leq cnt_i + 1$, где $cnt_i$ количество вхождений элемента $i$ в массив. Ну теперь можно сделать так:

$\sum_{i = 1}^{i < n}ans_i \leq \sum_{i = 1}^{i < n}(cnt_i + 1)$ => $\sum_{i = 1}^{i < n}ans_i \leq 2 * n$, а это значит что на самом деле решение выше работало за $O(n* log(n))$.

Код: (Ссылка)

Задача C.Запросы на перестановке

Автор разбора : Ли Ван

Подзадача 1. $N, Q \leq 5000$. 7 баллов.

Каждый запрос обрабатываем за линию. Решение за $O(NQ)$.

Подзадача 2. $p_i=i$, нету запросов типа 3. 15 баллов.

Тривиальная задача на дерево отрезков.

Подзадача 3. Все запросы типа 2 идут после запросов типа 1 и 3. 17 баллов.

Для удобства добавим массив $q_i$ такой, что $p_{q_i}=i$.

Будем считать $PS_i$ - сумму запросов первого типа, покрывающих $i$. Тогда для запросов 2-го типа можно предпосчитать префикс-сумму $Pref_i = Pref_{i-1} + PS_{q_i}$ и отвечать за $O(1)$. Свели задачу к "добавить $x$ ко всем $PS_i$ на отрезке $[l, r]$" и "поменять значения $PS_a$ и $PS_b$".

Подзадача 4. $N, Q \leq 50000$. 16 баллов.

Воспользуемся корневой декомпозицией. Главная идея в хранении суммы каждого блока массива $a_i$. Назовем сумму блока $i$ $S_i$. Для этого для каждого запроса 1-го типа нужно находить количество $j$ в отрезке $[l, r]$ таких, что $p_j$ находится в блоке $i$ и обновить $S_i$ соответственно для каждого $i$. Для запросов 2-го типа нам нужно эффективно находить значение $PS_{q_i}$ тех $i$, блоки которых не входят в отрезок $[l, r]$ полностью. Это тривиальная задача, решаемая деревом отрезков или деревом Фенвика.

Решение за $O(Q*sqrt(n)*log2(n)$

Код: https://codeforces.com/contest/4/submission/154421087

Подзадача 5. Нету запросов типа 3. 24 баллов.

Теперь асимптотика $O(Q* sqrt(n) * log2 * (n))$ слишком медленна. Заметим, что теперь можно предпосчитать префикс-суммы (заместо Фенвика), чтобы быстро обновлять $S_i$. Однако нам все равно нужно быстро находить значение $PS_{q_i}$. Применим корневую декомпозицию. Для запросов 1-го типа обновим $PBLOCKS_i$ всех блоков i, находящихся внутри отрезка $[l, r]$ и обновим $PS_i$ для всех i, блоки которых не входят в отрезок полностью.

Решение за $O(Q * sqrt(n))$

Полное решение.

Главная проблема - быстро обновлять $S_i$. Будем поддерживать $prefinb_{i,j}$ - количество таких $k$, что $p_k$ входит в блок j, $k \leq i$ и $k$ входит в один блок с $i$. Также будем поддерживать $Pref_{i,j}$ - количество таких $k$, что $k$ входит в блок $\leq i$ и $p_k = j$. Так мы сможем за $O(1)$ обновлять $S_i$.

Код для лучшего понимания: https://codeforces.com/contest/4/submission/154423843

Задача D. Витя - черепашка ниндзя 2

Автор разбора : Инкара Сабитова

Подзадача 1. $M = 1$. 10 баллов.

Путь всегда определяется однозначно, в него будут входить все клетки. Значит мы можем просто отсортировать все числа и выбрать $K$ самых больших числа.

Подзадача 2. $K = N + M - 1$. 15 баллов.

В этой подзадаче мы всегда платим за все клетки на пути, а значит нам нужно просто найти путь с минимальной суммой от клетки $(1, 1)$ до $(n, m)$. Это можно сделать с помощью примитовного применения ДП:

$dp_{1, 1} = a_{1, 1}$. $dp_{1, i} = dp_{1, i - 1} + a_{1, i}$, $i > 1$. $dp_{i, 1} = dp_{i - 1, 1} + a_{i, 1}$, $i > 1$. $dp_{i, j} = min(dp_{i - 1, j}, dp_{i, j - 1}) + a_{i, j}$, $i > 1, j > 1$.

Подзадача 3. K = 1. 14 баллов.

Теперь мы платим только за максимум на пути, это также решается примитивным ДП как в прошлой сабтаске, однако переходы немного изменяются:

$dp_{1, 1} = a_{1, 1}$. $dp_{1, i} = max(dp_{1, i - 1}, a_{1, i})$, $i > 1$. $dp_{i, 1} = max(dp_{i - 1, 1}, a_{i, 1})$, $i > 1$. $dp_{i, j} = max(min(dp_{i - 1, j}, dp_{i, j - 1}), a_{i, j})$, $i > 1, j > 1$.

Подзадача 4. $N, M <= 300$ и не более трёх различных элементов. 17 баллов.

Ну давайте запускать такую функцию, solve(x). Эта функция будет возвращать ответ среди всех путей на которых выполняются такие условия:

1. За все $a_{i, j}$ на пути которые меньше $x$ мы обязательно не платим.

2. За все $a_{i, j}$ на пути которые больше $x$ мы обязательно платим(и увеличиваем третий параметр ДП на 1).

3. За все $a_{i, j}$ на пути которые равны $x$, мы выбираем платить за них или нет(и в зависимости от выбора делаем переход в ДП).

Можно заметить что мы говорим про третий параметр дп, мы вводим новый параметр который говорит о количестве элементов >= x за которые мы заплатили на пути.

То есть поддерживаем $dp_{i, j, k}$. Переходы почти такие же как в подзадаче 2, но теперь мы учитываем три случая описанных выше.

Значение которое вернёт функция это $dp_{n, m, k}$.

Теперь просто для каждого $x$ запустим $solve(x)$ и выберем минимальное среди них. Всего различных $x$ есть $d + 1$ штук, где $d$ количество различных чисел.

Ассимптотика : $O(n * m * k * d)$

Подзадача 5. $N, M, a_{i,j} <= 100$ . 22 балла.

Решение аналогичное подзадаче 4, но в этом случае $d \leq 100$.

Ассимптотика : $O(n * m * k * d)$

Полное решение.

Теперь давайте избавимся от третьего параметра ДП. Теперь давайте при подсчёте $solve(x)$ будем делать такую операцию :

$a_{i, j} = max(0, a_{i, j} - x)$.

И будем запускать решение для второй подзадачи на этой матрице, и в конце давайте добавим $k * x$ к ответу, считая ответ так мы обязательно найдём правильный ответ но почему?

Если мыслить логически ответ будет неправильно считаться в случае где среди максимальных $k$ элементов есть элементы < x. Однако давайте заметим что ответ посчитанный для такого пути будет больше, а значит получить ответ который меньше чем настоящий ответ невозможно. Также давайте заметим что такие случаи учтутся при меньшем $x$, а значит таким способом в конце концов все случаи будут учитаны, а значит ответ всегда будет получен.

Ассимптотика : $O(n * m * d)$

Задача E.

Автора разбора : Ван Ли

Распишем условие когда побеждает дружба :

$mx1+mn1$ $=$ $mx2+mn2$

$mx1-mx2$ $=$ $mn2-mn1$

Иначе говоря, надо найти кол-во отрезков, где разница между первым и вторым максимумом равна разнице между вторым и первым минимумом.

Рассмотрим отрезки в которых i является вторым максимумом.

Для этого обозначим:

$L1$ - индекс первого большего элемента слева

$L2$ - индекс второго большего элемента слева

$R1$ - индекс первого большего элемента справа

$R2$ - индекс второго большего элемента справа

Тогда можно заметить, что $i$ будет вторым максимумом во всех отрезках $(l, r)$ таких, что

1. $L2+1 \leq l \leq L1$ и $i \leq r \leq R1-1$, где для каждого отрезка первым максимумом будет a[L1]

или

2. $L1+1 \leq l \leq i$ и $R1 \leq r \leq R2-1$, где для каждого отрезка первым максимумом будет a[R1]

Заметим, что если представлять отрезки $(l, r)$ в виде точек с координатой (l, r) на двумерной плоскости, то неравенства выше можно представить в виде прямоугольников

Аналогично выпишем прямогольники для второго минимума

Назовем значением прямоугольника разницу между первым и вторым максимумом (или вторым и первым минимумом) в отрезках этого прямоугольника

Теперь заметим, что каждая точка будет покрыта ровно двумя прямоугольниками. Если у двух прямоугольников точки одинаковое значение, то равенство $mx1-mx2$ $=$ $mn2-mn1$ выполняется для этой точки.

Иначе говоря, надо найти площадь пересечения прямоугольников с одним значением

Это делается сканлайном с деревом отрезков

Задача F. Нархан и скобочки

Автор разбора : Инкара Сабитова

Данная задача решается при помощи Alien-trick aka Лямбда оптимизация, aka Дискретная метод Лагранжа.

Идея такая давайте за расположение открытой скобки в особенную клетку будем платить штраф $\lambda$ и не смотреть на количество открытых скобок, будем просто получать максимальный ответ и количество открытых скобок в специальных позициях.

Тогда давайте заметим что при увеличении лямбы количество открытых скобок в специальных будет неубывать. Так что будем бинарить оптимальную лямбду для того чтобы получить $k$ открытых скобок. Более подробно про этот метод лучше прочитать в специальных статьях.

Теперь вопрос как считать ответ для определённой $\lambda$?

Пусть изначально все скобки закрытые, тогда будем "активировать" элементы.

Будем на ходу поддерживать отсортированное множество элементов которые мы можем активировать, будем хранить данные о том насколько изменится цена и насколько изменится количество открывающихся скобок в ответе. Не забудем учитывать штраф при подсчёте того насколько изменится ответ.

Для начала активируем первый элемент, так как без него у нас никогда не получится ПСП.

Далее на каждой итерации будем проводить такие действия, изначально $i = 2$:

Добавляем в множество $i$ и $i + 1$ элементы, активируем элемент из множества который максимально увеличит ответ. Увеличим $i$ на два.

Давайте подумаем почему эта жадность даст нам правильный ответ?

1. ПСП, изначально была последовательность закрытых скобок. Потом мы $n/2$ раза добавили открывающуюся скобку, а значит баланс равен 0. Также можно заметить что префиксный баланс всегда будет неотрицательным, так как каждый шаг мы активируем одну открывающуюся скобку на префиксе, что увеличивает все правые префиксные суммы на 1, что делает все префиксные суммы до $i + 2$ положительными.

2. Мы всегда берём максимальное возможное, можно заметить что активации клеток независимы между собой, не важно какую клетку мы активируем не изменится ничего кроме результата, т.е. активация одной скобки не повлияет на активацию другой скобки. А значит выбор максимальный оптимален.

Все действия в жадности можно проделывать с помощью встроенных структур данных похожих на priority_queue и set.

Теперь мы просто вернём полученную сумму и кол-во открытых скобок.

В итоге мы получим три значения $\lambda_{ans} , res, cnt$, где $\lambda_{ans}$ - оптимальный штраф, $res$ - максимальный ответ при таком штрафе, $cnt$ - количество специальных активированных позиций использованных для получения такого ответа.

Если $cnt = k$, то нет проблем просто делаем $res = res - \lambda_{ans} * cnt$ и выводим ответ. Иначе можем заметить что оптимальная $\lambda$ лежит между $lambda_{ans}$ и $lambda_{ans} + 1$. Давайте просто найдём ответы и количество специальных активированных позиций для каждого из двух штрафов. Отнимем все вхождения штрафов от ответов и запишем значения в $val_{\lambda}$, и посчитаем разницу между количеством специальных активированных позиций для двух штрафов.

В итоге мы можем узнать некий коэффициент $d = (val_{\lambda_{ans} + 1} - val_{\lambda_{ans}})/(cnt_{\lambda_{ans} + 1} - cnt_{\lambda_{ans}})$, и с помощью него посчитаем ответ $res = d * (k - cnt) + val_{\lambda_{ans}}$. Для того чтобы понять почему это работает прочитайте статьи про эту оптимизацию.

Теперь можно вывести ответ, ассимптотика решения $O(n * log^2(n))$. Код для лучшего понимания.