Спасибо за участие в раунде! Мы надеемся, что вам понравились задачи. Нам очень жаль, что с условием в задаче B возникли проблемы.↵
↵
<spoiler summary="Фан факты">↵
на раунд было предложено суммарно 30 задач↵
↵
E задумывалась как C, а C как B↵
</spoiler>↵
↵
[problem:2189A]↵
↵
Идея: [user:Fakewave,2026-01-23]↵
↵
<spoiler summary="Решение">↵
Заметим, что максимизация суммы чисел в таблице равносильна максимизации количества пар чисел, которые образуют клетку таблицы.↵
↵
Не ограничивая общности, будем считать, что $h \leq l$. Для любой клетки таблицы $(x, y)$ выполнено: $1 \leq x \leq h$, $1 \leq y \leq l$. Пусть $cnt_h$ — количество чисел массива, не превосходящих $h$, а $cnt_l$ — количество чисел массива, не превосходящих $l$. Тогда, во первых, ответ не превосходит $cnt_h$, ведь в каждой паре должно быть число, не превосходящее $h$. С другой стороны, ответ не превосходит $\displaystyle \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$, ведь в каждой паре оба числа должны не превосходить $l$. Остается понять, что $\displaystyle min(cnt_h, \Big\lfloor \frac{cnt_l}{2} \Big\rfloor)$ пар можно получить. Для этого разберём два случая.↵
↵
- если $\displaystyle cnt_h \leq \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$, то достаточно в пару каждому числу $x \leq h$ дать в пару своё число $h < y \leq l$, и будет $cnt_h$ пар. Это получится сделать, так как подходящих чисел $y$ не меньше, чем подходящих $x$.↵
↵
- если $\displaystyle cnt_h > \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$, то нужно в пару каждому числу $h < y \leq l$ дать в пару своё число $x \leq h$. После этого разбить оставшиеся числа $x \leq h$ на пары (возможно, останется одно лишнее число). Получится как раз $\displaystyle \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$ пар.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359457886]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:1,option1]↵
↵
Хорошая задача [likes:1,option2]↵
↵
Нормальная задача [likes:1,option3]↵
↵
Плохая задача [likes:1,option4]↵
↵
Ужасная задача [likes:1,option5] ↵
</spoiler>↵
↵
↵
↵
[problem:2189B]↵
↵
Идея: [user:furt1ve,2026-01-23], [user:Fakewave,2026-01-23]↵
↵
<spoiler summary="Решение">↵
Заметим, что задача равносильна минимизации откатов для достижения точки с числом $\geq x$. (Рассмотрим момент, когда лягушка впервые оказалась в точке $\geq x$. Тогда вместо полного прыжка лягушка могла прыгнуть не на полную длину, а ровно в точку $x$). Тогда будем считать, что лягушка всегда прыгает на $a_i$ делений вперед $i$-м видом прыжка.↵
↵
Во первых, лягушка может использовать прыжок $i$-го вида $b_i-1$ раз, не испытав откат. Пусть $r$ это количество делений, которое осталось до числа $x$ после этих прыжков (если $r \leq 0$, то нужно $0$ откатов). ↵
↵
Теперь у нас любой прыжок будет создавать откат. Однако заметим, что после одного прыжка с откатом, использовав $i$-й вид прыжка, мы можем использовать этот же прыжок еще $b_i-1$ раз, не испытав откат. После этого мы окажемся в той же ситуации (любой прыжок создает откат), однако мы переместимся на $a_ib_i-c_i$ делений. Таким образом, стоит использовать прыжок с максимальным значением $a_ib_i-c_i$.↵
↵
Пусть $m = \max(a_ib_i-c_i)$ по всем $i$ от $1$ до $n$. Тогда если $m \leq 0$, то мы не сможем переместиться вперед (т.к. мы сначала испытываем откат на $c_i$, а затем движемся вперёд на $a_ib_i$), и ответ $-1$. Иначе потребуется $\displaystyle \Big\lceil \frac{r}{m} \Big\rceil$ откатов.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359458220]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:2,option1]↵
↵
Хорошая задача [likes:2,option2]↵
↵
Нормальная задача [likes:2,option3]↵
↵
Плохая задача [likes:2,option4]↵
↵
Ужасная задача [likes:2,option5] ↵
</spoiler>↵
↵
↵
↵
[problem:2189C1]↵
↵
Идея: [user:Fakewave,2026-01-23]↵
↵
<spoiler summary="Решение">↵
Будет скоро добавлено.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359458251]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:3,option1]↵
↵
Хорошая задача [likes:3,option2]↵
↵
Нормальная задача [likes:3,option3]↵
↵
Плохая задача [likes:3,option4]↵
↵
Ужасная задача [likes:3,option5] ↵
</spoiler>↵
↵
↵
↵
[problem:2189C2]↵
↵
<spoiler summary="Решение">↵
Будет скоро добавленоВо первых, заметим, что $p_i = p_j \oplus i$ равносильно $p_i \oplus i = p_j$. Для $i = n-1$ в качестве $j$ может выступать только $j = n$. Давайте попробуем сделать такую перестановку, что для всех $i$ в качестве $j$ будет выступать $j = n$. То есть хотим сделать так, чтобы для всех $i \geq 2$ было выполнено $p_i \oplus i = p_n$. Возьмем $p_n = 1$. Тогда замечаем, что на позиции $2k$ должно стоять $2k \oplus 1= 2k+1$, а на позиции $2k+1$ должно стоять $(2k+1) \oplus 1 = 2k$. То есть числа разбиваются на пары $2k$ и $2k+1$.↵
↵
Разберем $2$ варианта:↵
↵
1. $n$ четное, тогда возьмем $p_1 = n$, $p_{2k} = 2k+1$, $p_{2k+1} = 2k$ ($1 \leq k \leq \frac{n}{2} - 1$);↵
↵
2. $n$ нечетное, тогда возьмем $p_1 = n-1$, $p_{2k} = 2k+1$ ($1 \leq k \leq \frac{n-1}{2}$) , $p_{2k+1} = 2k$ ($1 \leq k \leq \frac{n-3}{2}$).↵
↵
Случаи различаются тем, что на $p_1$ останутся разные числа.↵
↵
Например, при $n = 9$: $[8, 3, 2, 5, 4, 7, 6, 9, 1]$, при $n = 10$: $[10, 3, 2, 5, 4, 7, 6, 9, 8, 1]$.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359458251]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:3,option1]↵
↵
Хорошая задача [likes:3,option2]↵
↵
Нормальная задача [likes:3,option3]↵
↵
Плохая задача [likes:3,option4]↵
↵
Ужасная задача [likes:3,option5] ↵
</spoiler>↵
↵
↵
↵
[problem:2189C2]↵
↵
<spoiler summary="Решение">↵
Во первых, докажем, что при $n = 2^x$ ($x$ — целое) не существует примера. ↵
↵
Пусть $n$ стоит на позиции $i$. Предположим, что $i < n$. Тогда $p_i \oplus i= p_j $, для некоторого $j$. Но $p_i \oplus i \geq n$, ведь $p_i = n = 2^x$, а $p_j<n$ — противоречие. Значит $i = n$. Но тогда $p_{n-1} = p_n \oplus (n-1)$. Но $p_n \oplus (n-1)$ больше $n$, а $p_{n-1}$ меньше — противоречие.↵
↵
Для $n \neq 2^x$ покажем, что пример существует.↵
↵
Рассмотрим примеры, взятые в C1. Заметим, что при нечетном $n$ пример подходит, ведь $p_1 = n-1$, а где то после стоит число $n$ и $n \oplus 1 = (n-1)$. Теперь рассмотрим пример для четного $n$.↵
↵
$n = 2^x+r$, где $r < 2^x$ (иными словами, $x$ — старший бит $n$). Тогда давайте поменяем местами $p_1$ и $p_r$. Давайте посмотрим, что изменилось. Так как для всех $i \geq 2$ до этого в качестве $j$ выступало только $n$, то сломаться могло только число, стоящее на позиции $r$. Но теперь $p_r = n$. Заметим, что $2^x \oplus r = n$ и при этом число $2^x$ стоит на позиции $2^x+1$. Таким образом, для $i = r$ теперь подходит $j = 2^x+1 > r$.↵
↵
Остается проверить, что $i = 1$ имеет подходящее $j$. Возьмем $j = r + 1$. $n$ — четное, а значит $r$ — четное. Тогда $p_j = r$ и $p_1 = r+1$. Действительно: $r+1 = r\oplus 1$.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359458288]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:4,option1]↵
↵
Хорошая задача [likes:4,option2]↵
↵
Нормальная задача [likes:4,option3]↵
↵
Плохая задача [likes:4,option4]↵
↵
Ужасная задача [likes:4,option5] ↵
</spoiler>↵
↵
↵
↵
[problem:2189D1]↵
↵
Идея: [user:Fakewave,2026-01-23], [user:yanb0,2026-01-23]↵
↵
<spoiler summary="Решение">↵
Рассмотрим, какие перестановки $p$ удовлетворяют условию строки $w$. Очевидно, что если $w_1 = \texttt{0}$ или $w_n = \texttt{0}$, подходящих $p$ нет (в любой перестановке есть подотрезок только с числом $0$ и подотрезок со всеми числами), поэтому дальше считаем, что $w_1 = w_n = \texttt{1}$. Давайте конструировать $p$, начиная с $p = [0]$ и вставляя по очереди числа $1, 2, \ldots, n - 1$ в какие-то позиции.↵
↵
Пусть мы расставили числа $0, 1, \ldots, k - 1$ и теперь собираемся вставить число k относительно них. У нас есть $k + 1$ вариантов, куда его вставить. ↵
↵
Если мы вставим $k$ перед всеми числами, либо после всех чисел, то мы можем всегда выбрать все оставшиеся числа в качестве отрезка и получить на них $\operatorname{mex} = k$ (заметим, что вставка последующих чисел не повлияет на $\operatorname{mex}$ этого отрезка, поскольку все последующие значения $> k$). ↵
↵
Если же мы вставим $k$ между какими-то значениями, то мы получим ситуацию, что у нас и слева, и справа от $k$ есть значение, которое $< k$. Тогда, чтобы получить $\operatorname{mex} = k$, нам надо набрать все числа $< k$, но поскольку они есть и слева, и справа, мы включим $k$, и получим $\operatorname{mex} > k$.↵
↵
Итого, у нас есть $2$ варианта, как обеспечить $w_k=1$, и $k-1$ вариант для $w_k=0$. Мы получили, что ↵
↵
$$f(w) = \prod_{i = 1}^{n - 1}\begin{cases} 2 &\text{если } w_i = \texttt{1} \\ i - 1 &\text{иначе}\end{cases}$$↵
↵
В этой версии задачи $w = s$, а значит нужно лишь проверить, делится ли $f(w)$ на $c$. Для этого пройдемся по всем $i$ и будем сокращать $c$ на наибольший общий делитель очередного множителя и числа $c$. Если в итоге получилось $c = 1$, то ответ $-1$. Иначе ответ $f(w)$.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359458322]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:5,option1]↵
↵
Хорошая задача [likes:5,option2]↵
↵
Нормальная задача [likes:5,option3]↵
↵
Плохая задача [likes:5,option4]↵
↵
Ужасная задача [likes:5,option5] ↵
</spoiler>↵
↵
↵
↵
[problem:2189D2]↵
↵
<spoiler summary="Решение">↵
Из D1 имеем:↵
↵
$$f(w) = \prod_{i = 1}^{n - 1}\begin{cases} 2 &\text{если } w_i = \texttt{1} \\ i - 1 &\text{иначе}\end{cases}$$↵
↵
Посчитаем произведение членов-множителей для всех символов $s$, которые даны (\texttt{0} или \texttt{1}), назовём это число $b$; произведение остальных членов назовём $x$. Остальные символы мы можем выбирать, то есть нам нужно найти наименьшее значение↵
↵
$$bx = b\prod_{i \in [1, n - 1], s_i = \texttt{?}}\begin{cases} 2 \\ i - 1\end{cases}$$↵
↵
не делящееся на $c$. От $b$ можно избавиться — $x$ не должен делиться на $c' = \frac{c}{\gcd(b, c)}$. (В реализации для получения $c'$ мы делим $c$ на $\gcd$ с каждым членом произведения $b$ во избежание переполнения.) Если мы можем выбирать $s_2$, то выберем $s_2 = \texttt{1}$, что сделает один из членов произведения равным $1$ — это не вызовет делимость и не увеличит число. В итоге, мы должны выбрать для нескольких $j \ge 2$ (для $j = i - 1$, где $s_i = \texttt{?}$) умножить $x$ либо на $2$, либо на $j$, чтобы произведение было минимально и не делилось на $c'$, и ответом будет $bx$.↵
↵
Рассмотрим два случая.↵
↵
1. $c'$ — степень $2$. Для всех чётных $j$ выберем умножать на $2$, т.к. умножение на $2$ вместо положительного чётного числа не вызовет делимость и не увеличит произведение. Остаётся жадно выбирать умножение на $2$ для наибольших из оставшихся $j$, пока это возможно ($c'$ всё ещё не делит $x$), чтобы минимизировать $x$.↵
2. $c'$ — не степень $2$. Тогда выбирая каждый раз умножение на $2$, $x$ не поделится на $c'$, а произведение будет минимальным, т.к. каждый раз мы выбирали меньший из возможных множителей ($2 \le j$).↵
↵
Итоговая асимптотика: $\mathcal{O}(n \log n)$.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359458348]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:6,option1]↵
↵
Хорошая задача [likes:6,option2]↵
↵
Нормальная задача [likes:6,option3]↵
↵
Плохая задача [likes:6,option4]↵
↵
Ужасная задача [likes:6,option5] ↵
</spoiler>↵
↵
↵
↵
[problem:2189E]↵
↵
Идея: [user:Fakewave,2026-01-23], [user:furt1ve,2026-01-23]↵
↵
<spoiler summary="Решение">↵
Сразу скажем, что ответ $-1$, если строка состоит из $0$.↵
↵
Пусть мы сделали $k$ операций, $i$-я из которых стоила $a_i$. Тогда $(a_1-1)+(a_2-1)+\cdots+(a_k-1) = n-1$ (количество символов, которые надо удалить), откуда $cost = a_1+a_2+\cdots+a_k=n-1+k$. То есть задача переходит в найти наименьшее число операций $k$, для достижения цели. Ответ будет $n-1+k$.↵
↵
Покажем, что $k \leq 4$. Пусть $s_i = 1$. Заменим подстроки $[1, i-1]$ и $[i+1, n]$ на какие-нибудь символы. Теперь у нас строка $x1y$. Заменим подстроку $[1, 2]$ на $1$, получится строка $1y$. Остается заменить её на строку $1$.↵
↵
↵
Теперь разберемся, когда минимальное число операций это $k = 0, 1, 2, 3$ (иначе $k = 4$).↵
↵
Под \textbf{разностью} строки будем подразумевать разность между количеством единиц и нулей.↵
↵
Утверждается, что за $k$ операций можно сделать, если:↵
↵
1. $k = 0$↵
Когда $s = 1$.↵
↵
2. $k = 1$↵
Разность строки неотрицательная.↵
↵
3. $k = 2$↵
В строке есть префикс/суффикс с положительной разницей (тогда оставшуюся часть можно заменить на любой символ и после этого перевести всю строку в $1$) или разность строки равна $-1$ (тогда если первое условие не выполнено, то можно сделать операцию замены подстроки $[1, n-1]$ на $1$ (ведь её разность $0$, т.к. $s_n = 0$), получится строка $10$, которую можно перевести в $1$ одним действием).↵
↵
4. $k = 3$↵
В строке есть префикс/суффикс с неотрицательной разницей (тогда оставшуюся часть можно заменить на $0$, эту часть на $1$ и получится строка $10$ или $01$, дальше достаточно одной операции) или есть $2$ единицы подряд (тогда заменим префикс и суффикс до них на что-то, получится строка с разницей $\geq 0$, которую можно перевести в $1$).↵
↵
↵
5. $k = 4$↵
Иначе.↵
Перейдем к доказательствам для $k \geq 2$.↵
↵
#### $k = 2$↵
↵
Предположим, что нельзя за $k < 2$ операции и можно за $k = 2$, при условии что разница не $-1$ и нет префикса/суффикса с положительной разницей.↵
Если первая операция — префикс или суффикс, то в этой подстроке разница $\geq 0$. Чтобы после этого можно было победить за $1$ операцию, в оставшейся части должна быть разница $-1$ (т.к. если разница $\geq 0$, то разница всей изначальной строки неотрицательная, а если $< -1$, то суммарная разница после $1$ операции $<0$). Тогда разница всей строки тоже $-1$. Если же первая операция какая-то другая, то после операции разница $\leq -1 + 1 + -1 = -1$ (префикс + подстрока + суффикс). То есть победить не получится.↵
↵
#### $k = 3$↵
↵
Предположим, что нельзя за $k < 3$ операции и можно за $k = 3$, при условии что нет префикса/суффикса с неотрицательной разницей и нет двух единиц подряд.↵
↵
Пусть изначально разность равна $z$. Пусть мы делаем операцию с подстрокой $l$, $r$. Тогда пусть в подстроке $1$, $l-1$ разность равна $a < 0$, в подстроке $l$, $r$ равна $b$, а в подстроке $r+1$, $n$ равна $c < 0$.↵
↵
Если $b = 0$, то теперь разность становится $a+1+c$.↵
↵
Пусть $a+c+1 = -1$. Тогда так как $a + c = -2$ и $a,c \leq -1$, то $a = -1$ и $c = -1$. Но тогда если подстрока $l$, $r$ начинается с $0$ и заканчивается $0$ (иначе префикс $1\ldots l$ или суффикс $r\ldots n$ имеет разность $\geq 0$). Но тогда подстрока $l+1$, $r-1$ имеет разность $2$. Тогда размер этой подстроки четный (ведь если нулей $x$, то единиц $2+x$, а значит всего символов $2+2x$). Поделим символы на пары соседних $(l+1, l+2; \dots; r-2, r-1)$. В каждой из них разность $\leq 0$ (т.к. не $2$ единицы), а значит разность этой подстроки не равна $2$. Значит, такое невозможно.↵
↵
Другой случай: появится положительный префикс/суффикс (не ограничивая общности, префикс). ($l$, $r$ — не префикс и не суффикс, т.к. $b = 0$).↵
↵
Заметим, что получившийся положительный префикс $T$. Понятно, что $T$ будет содержать $1$ (которую получили из $b$) и ещё что-то из суффикса $r+1 \ldots n$ (обозначим его за $M$), причём это что-то имеет разность $> 0$. Тогда если эта разность $d$, то у $T$ разность $a+1+d \geq 1$. Тогда $a+d \leq 0$. Ранее мы показали, что $d \leq 1$ (иначе есть $2$ единицы подряд). Тогда $a \geq -1$. Значит, $a = -1$. Тогда $M$ начинается с $0$ (иначе $a+b+1 = 0$ и мы имеем префикс $\geq 0$). Тогда оставшийся используемый префикс $M$ имеет разность $2$, а значит содержит $2$ подряд идущие единицы — противоречие.↵
↵
$b < 0$.↵
↵
Если разность становится $-1$, то тогда теперь разность равна $a-1+c$. $a-1+c = -1 \implies a+c = 0$, что невозможно.↵
↵
Другой случай: появится положительный префикс/суффикс (не ограничивая общности, префикс).↵
↵
- Пусть $l = 1$. Тогда после этого суффикс $r+1, \ldots, n$. Теперь получается $0$ + префикс из $M$. Но тогда этот префикс должен иметь разность $\geq 2 \implies$ есть $2$ единицы — противоречие.↵
↵
- Иначе мы содержим префикс $1 \ldots (l-1)$ + $0$ (полученный из $b$) + префикс $(r+1 \ldots n)$ (обозначим его за $M$). Тогда этот префикс должен иметь разность $\geq 3$ (т.к. у $1 \ldots (l-1)$ разность $\leq -1$, а ещё и $0$ появляется). Тогда есть $2$ единицы подряд — противоречие.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359458367]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:7,option1]↵
↵
Хорошая задача [likes:7,option2]↵
↵
Нормальная задача [likes:7,option3]↵
↵
Плохая задача [likes:7,option4]↵
↵
Ужасная задача [likes:7,option5] ↵
</spoiler>↵
↵
↵
↵
[problem:2189F]↵
↵
Идея: [user:yanb0,2026-01-23]↵
↵
<spoiler summary="Решение">↵
Будем называть вершину мёртвой, если в ней $0$ гаек, и при подвешивании за неё среди поддеревьев её детей не больше одного поддерева с положительной суммой количеств гаек.↵
↵
Будем записывать операцию перемещения для вершины $v$ как $\operatorname{c}(v)$. ↵
↵
Пусть $A$ — лес, состоящий из всех живых вершин. Докажем, что $A$ всегда связный, т.е. является деревом. Если для противоречия $A$ состоит хотя бы из двух компонент связности, на пути между ними должна найтись мёртвая вершина $v$, но с другой стороны $v$ живая, т.к. обе компоненты связности находятся в разных поддеревьях детей $v$ при подвешивании за $v$, противоречие, ч.т.д.↵
↵
Пусть $\deg(v)$ — степень вершины $v$ в $A$. Несложно заметить, что при применении $\operatorname{c}(v)$, $a_v := a_v + \deg(v)$, а для всех остальных вершин $u \in A$, $a_u := a_u + \deg(u) - 2$. Если $v \not \in A$, то $a_v := a_v + 1$, $a_u := a_u + \deg(u) - 2$, $a_p := a_p + \deg(p) - 1$, где $p$ — ближайшая к $v$ вершина из $A$. $[*]$↵
↵
Для последовательности действий определим дерево $L$ как $A$ в момент после всех операций $\operatorname{c}(v)$ и до съедения гаек.↵
↵
Пусть у нас есть последовательность операций (включая съедение), приводящая к тому, что гаек не останется. Докажем, что последнюю из операций $\operatorname{c}(v)$, где $v \not \in L$, можно заменить на операцию $\operatorname{c}(u)$, где $u \in L$, при этом $A$ станет своим нестрогим подмножеством, и гаек опять же не останется. Рассмотрим момент перед применением $\operatorname{c}(v)$. Есть два варианта:↵
↵
1. $v$ жива. Тогда при замене $\operatorname{c}(v)$ на $\operatorname{c}(u)$, $a_v$ уменьшится на $2$, а $a_u$ увеличится на $2$ по $[*]$.↵
↵
2. $v$ мертва. Пусть $p$ — ближайшая к $v$ вершина из $A$. Тогда при замене $\operatorname{c}(v)$ на $\operatorname{c}(u)$, $a_v$ и $a_u$ уменьшатся на $1$ (станут равными $0$), а $a_p$ увеличится на $1$ по $[*]$. ↵
↵
В обоих случаях, все $a_x$ для $x \not \in L$ уменьшатся, и несложно видеть, что последовательность операций после $\operatorname{c}(v)$ также приведёт все гайки в $L$, после чего те же самые операции съедения уберут все гайки, ч.т.д. Таким образом, все операции типа $\operatorname{c}(v)$, где $v \not \in L$, можно (последовательно с конца) заменить на $\operatorname{c}(u)$ для некоторых $u \in L$.↵
↵
Теперь остаётся решить следующую задачу:↵
↵
Нужно выбрать поддерево $L$ изначального дерева, потом несколько раз применить $\operatorname{c}(u)$, $u \in L$, чтобы сделать все вершины не из $L$ мёртвыми, а затем применить операцию съедения для всех $v \in L$. Заметим, что по $[*]$ все вершины не из $L$ станут мёртвыми вне зависимости от того, какие вершины $L$ мы выбираем, иными словами, можно применять все $\operatorname{c}(v)$ только к одной вершине $v$.↵
↵
Представим динамику по ориентированным рёбрам $xy$, $dp[x][y]$: наименьшее количество операций $\operatorname{c}(v)$, где $v$ со стороны $x$ от $xy$, нужное, чтобы сделать все вершины со стороны $y$ (включая $y$) от $xy$ мёртвыми. Значение $a_y$ может уменьшаться только когда $\deg(y) = 1$, поэтому $dp[x][y] = \sum_{i=0}^{k}\Bigl(dp[y][ch[i]]\Bigr)$, то есть $dp[x][y]$ равно сумме $a_v$ по всем $v$ в поддереве $y$, если подвесить всё дерево за $x$.↵
↵
Для всех вершин $v \not \in L$ в какой-то момент и всегда после него $a_v = 0$, а ещё возможно, что $a_v = 0$ перед всеми операциями, больше никогда $a_v$ не равно $0$.↵
↵
Определим $zero[y]$ как наименьшее количество операций $\operatorname{c}(v)$, нужное, чтобы $a_y = 0$ после любого количества операций $\operatorname{c}(v)$, не меньшем $zero[y]$. $zero[y] = \min_x({dp[x][y]})$ для всех $x$, смежных с $y$, и $zero[y] = 0$, если изначально $a_y = 0$ и $\deg(y) = 2$. Это так, потому что если $a_y \ne 0$ или $\deg(y) \ne 2$, $y$ окончательно "обнулится", только когда станет мёртвой. $\min_x({dp[x][v]})$ больше $dp[v][u]$ для всех, возможно, кроме одной, вершин $u$, смежных с $v$, а значит, больше $\min_t({dp[t][u]})$ для $t$, смежных с $u$, смежных с $v$. Значит, применяя $\operatorname{c}(v)$ к $v$ с наибольшим $zero[v]$, каждое $a_u$ станет равным $0$ после $zero[u]$ операций.↵
↵
Таким образом, либо операций $\operatorname{c}(x)$ нет, и операцию съедения нужно применить ко всем $y$ с начальным $a_y = 0$, либо операций $\operatorname{c}(x)$ $k$, и операцию съедения нужно применить ко всем вершинам $y$ с $zero[y] \ge k$. Для первого случая просто посчитаем стоимость этой последовательности операций, а для второго случая за $O(n \log n)$ отсортируем $zero$, после чего переберём количество "обнулённых" вершин, пробегаясь по $zero$, будем считать ответ как $(n - i) \cdot q + zero[i - 1] \cdot p$. Ответом на задачу будет минимальный из полученных.↵
↵
Суммарная асимптотика: $O(n \log n)$.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359458396]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:8,option1]↵
↵
Хорошая задача [likes:8,option2]↵
↵
Нормальная задача [likes:8,option3]↵
↵
Плохая задача [likes:8,option4]↵
↵
Ужасная задача [likes:8,option5] ↵
</spoiler>↵
↵
↵
<spoiler summary="Фан факты">↵
на раунд было предложено суммарно 30 задач↵
↵
E задумывалась как C, а C как B↵
</spoiler>↵
↵
[problem:2189A]↵
↵
Идея: [user:Fakewave,2026-01-23]↵
↵
<spoiler summary="Решение">↵
Заметим, что максимизация суммы чисел в таблице равносильна максимизации количества пар чисел, которые образуют клетку таблицы.↵
↵
Не ограничивая общности, будем считать, что $h \leq l$. Для любой клетки таблицы $(x, y)$ выполнено: $1 \leq x \leq h$, $1 \leq y \leq l$. Пусть $cnt_h$ — количество чисел массива, не превосходящих $h$, а $cnt_l$ — количество чисел массива, не превосходящих $l$. Тогда, во первых, ответ не превосходит $cnt_h$, ведь в каждой паре должно быть число, не превосходящее $h$. С другой стороны, ответ не превосходит $\displaystyle \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$, ведь в каждой паре оба числа должны не превосходить $l$. Остается понять, что $\displaystyle min(cnt_h, \Big\lfloor \frac{cnt_l}{2} \Big\rfloor)$ пар можно получить. Для этого разберём два случая.↵
↵
- если $\displaystyle cnt_h \leq \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$, то достаточно в пару каждому числу $x \leq h$ дать в пару своё число $h < y \leq l$, и будет $cnt_h$ пар. Это получится сделать, так как подходящих чисел $y$ не меньше, чем подходящих $x$.↵
↵
- если $\displaystyle cnt_h > \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$, то нужно в пару каждому числу $h < y \leq l$ дать в пару своё число $x \leq h$. После этого разбить оставшиеся числа $x \leq h$ на пары (возможно, останется одно лишнее число). Получится как раз $\displaystyle \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$ пар.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359457886]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:1,option1]↵
↵
Хорошая задача [likes:1,option2]↵
↵
Нормальная задача [likes:1,option3]↵
↵
Плохая задача [likes:1,option4]↵
↵
Ужасная задача [likes:1,option5] ↵
</spoiler>↵
↵
↵
↵
[problem:2189B]↵
↵
Идея: [user:furt1ve,2026-01-23], [user:Fakewave,2026-01-23]↵
↵
<spoiler summary="Решение">↵
Заметим, что задача равносильна минимизации откатов для достижения точки с числом $\geq x$. (Рассмотрим момент, когда лягушка впервые оказалась в точке $\geq x$. Тогда вместо полного прыжка лягушка могла прыгнуть не на полную длину, а ровно в точку $x$). Тогда будем считать, что лягушка всегда прыгает на $a_i$ делений вперед $i$-м видом прыжка.↵
↵
Во первых, лягушка может использовать прыжок $i$-го вида $b_i-1$ раз, не испытав откат. Пусть $r$ это количество делений, которое осталось до числа $x$ после этих прыжков (если $r \leq 0$, то нужно $0$ откатов). ↵
↵
Теперь у нас любой прыжок будет создавать откат. Однако заметим, что после одного прыжка с откатом, использовав $i$-й вид прыжка, мы можем использовать этот же прыжок еще $b_i-1$ раз, не испытав откат. После этого мы окажемся в той же ситуации (любой прыжок создает откат), однако мы переместимся на $a_ib_i-c_i$ делений. Таким образом, стоит использовать прыжок с максимальным значением $a_ib_i-c_i$.↵
↵
Пусть $m = \max(a_ib_i-c_i)$ по всем $i$ от $1$ до $n$. Тогда если $m \leq 0$, то мы не сможем переместиться вперед (т.к. мы сначала испытываем откат на $c_i$, а затем движемся вперёд на $a_ib_i$), и ответ $-1$. Иначе потребуется $\displaystyle \Big\lceil \frac{r}{m} \Big\rceil$ откатов.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359458220]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:2,option1]↵
↵
Хорошая задача [likes:2,option2]↵
↵
Нормальная задача [likes:2,option3]↵
↵
Плохая задача [likes:2,option4]↵
↵
Ужасная задача [likes:2,option5] ↵
</spoiler>↵
↵
↵
↵
[problem:2189C1]↵
↵
Идея: [user:Fakewave,2026-01-23]↵
↵
<spoiler summary="Решение">↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359458251]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:3,option1]↵
↵
Хорошая задача [likes:3,option2]↵
↵
Нормальная задача [likes:3,option3]↵
↵
Плохая задача [likes:3,option4]↵
↵
Ужасная задача [likes:3,option5] ↵
</spoiler>↵
↵
↵
↵
[problem:2189C2]↵
↵
<spoiler summary="Решение">↵
Будет скоро добавлено
↵
Разберем $2$ варианта:↵
↵
1. $n$ четное, тогда возьмем $p_1 = n$, $p_{2k} = 2k+1$, $p_{2k+1} = 2k$ ($1 \leq k \leq \frac{n}{2} - 1$);↵
↵
2. $n$ нечетное, тогда возьмем $p_1 = n-1$, $p_{2k} = 2k+1$ ($1 \leq k \leq \frac{n-1}{2}$) , $p_{2k+1} = 2k$ ($1 \leq k \leq \frac{n-3}{2}$).↵
↵
Случаи различаются тем, что на $p_1$ останутся разные числа.↵
↵
Например, при $n = 9$: $[8, 3, 2, 5, 4, 7, 6, 9, 1]$, при $n = 10$: $[10, 3, 2, 5, 4, 7, 6, 9, 8, 1]$.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359458251]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:3,option1]↵
↵
Хорошая задача [likes:3,option2]↵
↵
Нормальная задача [likes:3,option3]↵
↵
Плохая задача [likes:3,option4]↵
↵
Ужасная задача [likes:3,option5] ↵
</spoiler>↵
↵
↵
↵
[problem:2189C2]↵
↵
<spoiler summary="Решение">↵
Во первых, докажем, что при $n = 2^x$ ($x$ — целое) не существует примера. ↵
↵
Пусть $n$ стоит на позиции $i$. Предположим, что $i < n$. Тогда $p_i \oplus i= p_j $, для некоторого $j$. Но $p_i \oplus i \geq n$, ведь $p_i = n = 2^x$, а $p_j<n$ — противоречие. Значит $i = n$. Но тогда $p_{n-1} = p_n \oplus (n-1)$. Но $p_n \oplus (n-1)$ больше $n$, а $p_{n-1}$ меньше — противоречие.↵
↵
Для $n \neq 2^x$ покажем, что пример существует.↵
↵
Рассмотрим примеры, взятые в C1. Заметим, что при нечетном $n$ пример подходит, ведь $p_1 = n-1$, а где то после стоит число $n$ и $n \oplus 1 = (n-1)$. Теперь рассмотрим пример для четного $n$.↵
↵
$n = 2^x+r$, где $r < 2^x$ (иными словами, $x$ — старший бит $n$). Тогда давайте поменяем местами $p_1$ и $p_r$. Давайте посмотрим, что изменилось. Так как для всех $i \geq 2$ до этого в качестве $j$ выступало только $n$, то сломаться могло только число, стоящее на позиции $r$. Но теперь $p_r = n$. Заметим, что $2^x \oplus r = n$ и при этом число $2^x$ стоит на позиции $2^x+1$. Таким образом, для $i = r$ теперь подходит $j = 2^x+1 > r$.↵
↵
Остается проверить, что $i = 1$ имеет подходящее $j$. Возьмем $j = r + 1$. $n$ — четное, а значит $r$ — четное. Тогда $p_j = r$ и $p_1 = r+1$. Действительно: $r+1 = r\oplus 1$.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359458288]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:4,option1]↵
↵
Хорошая задача [likes:4,option2]↵
↵
Нормальная задача [likes:4,option3]↵
↵
Плохая задача [likes:4,option4]↵
↵
Ужасная задача [likes:4,option5] ↵
</spoiler>↵
↵
↵
↵
[problem:2189D1]↵
↵
Идея: [user:Fakewave,2026-01-23], [user:yanb0,2026-01-23]↵
↵
<spoiler summary="Решение">↵
Рассмотрим, какие перестановки $p$ удовлетворяют условию строки $w$. Очевидно, что если $w_1 = \texttt{0}$ или $w_n = \texttt{0}$, подходящих $p$ нет (в любой перестановке есть подотрезок только с числом $0$ и подотрезок со всеми числами), поэтому дальше считаем, что $w_1 = w_n = \texttt{1}$. Давайте конструировать $p$, начиная с $p = [0]$ и вставляя по очереди числа $1, 2, \ldots, n - 1$ в какие-то позиции.↵
↵
Пусть мы расставили числа $0, 1, \ldots, k - 1$ и теперь собираемся вставить число k относительно них. У нас есть $k + 1$ вариантов, куда его вставить. ↵
↵
Если мы вставим $k$ перед всеми числами, либо после всех чисел, то мы можем всегда выбрать все оставшиеся числа в качестве отрезка и получить на них $\operatorname{mex} = k$ (заметим, что вставка последующих чисел не повлияет на $\operatorname{mex}$ этого отрезка, поскольку все последующие значения $> k$). ↵
↵
Если же мы вставим $k$ между какими-то значениями, то мы получим ситуацию, что у нас и слева, и справа от $k$ есть значение, которое $< k$. Тогда, чтобы получить $\operatorname{mex} = k$, нам надо набрать все числа $< k$, но поскольку они есть и слева, и справа, мы включим $k$, и получим $\operatorname{mex} > k$.↵
↵
Итого, у нас есть $2$ варианта, как обеспечить $w_k=1$, и $k-1$ вариант для $w_k=0$. Мы получили, что ↵
↵
$$f(w) = \prod_{i = 1}^{n - 1}\begin{cases} 2 &\text{если } w_i = \texttt{1} \\ i - 1 &\text{иначе}\end{cases}$$↵
↵
В этой версии задачи $w = s$, а значит нужно лишь проверить, делится ли $f(w)$ на $c$. Для этого пройдемся по всем $i$ и будем сокращать $c$ на наибольший общий делитель очередного множителя и числа $c$. Если в итоге получилось $c = 1$, то ответ $-1$. Иначе ответ $f(w)$.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359458322]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:5,option1]↵
↵
Хорошая задача [likes:5,option2]↵
↵
Нормальная задача [likes:5,option3]↵
↵
Плохая задача [likes:5,option4]↵
↵
Ужасная задача [likes:5,option5] ↵
</spoiler>↵
↵
↵
↵
[problem:2189D2]↵
↵
<spoiler summary="Решение">↵
Из D1 имеем:↵
↵
$$f(w) = \prod_{i = 1}^{n - 1}\begin{cases} 2 &\text{если } w_i = \texttt{1} \\ i - 1 &\text{иначе}\end{cases}$$↵
↵
Посчитаем произведение членов-множителей для всех символов $s$, которые даны (\texttt{0} или \texttt{1}), назовём это число $b$; произведение остальных членов назовём $x$. Остальные символы мы можем выбирать, то есть нам нужно найти наименьшее значение↵
↵
$$bx = b\prod_{i \in [1, n - 1], s_i = \texttt{?}}\begin{cases} 2 \\ i - 1\end{cases}$$↵
↵
не делящееся на $c$. От $b$ можно избавиться — $x$ не должен делиться на $c' = \frac{c}{\gcd(b, c)}$. (В реализации для получения $c'$ мы делим $c$ на $\gcd$ с каждым членом произведения $b$ во избежание переполнения.) Если мы можем выбирать $s_2$, то выберем $s_2 = \texttt{1}$, что сделает один из членов произведения равным $1$ — это не вызовет делимость и не увеличит число. В итоге, мы должны выбрать для нескольких $j \ge 2$ (для $j = i - 1$, где $s_i = \texttt{?}$) умножить $x$ либо на $2$, либо на $j$, чтобы произведение было минимально и не делилось на $c'$, и ответом будет $bx$.↵
↵
Рассмотрим два случая.↵
↵
1. $c'$ — степень $2$. Для всех чётных $j$ выберем умножать на $2$, т.к. умножение на $2$ вместо положительного чётного числа не вызовет делимость и не увеличит произведение. Остаётся жадно выбирать умножение на $2$ для наибольших из оставшихся $j$, пока это возможно ($c'$ всё ещё не делит $x$), чтобы минимизировать $x$.↵
2. $c'$ — не степень $2$. Тогда выбирая каждый раз умножение на $2$, $x$ не поделится на $c'$, а произведение будет минимальным, т.к. каждый раз мы выбирали меньший из возможных множителей ($2 \le j$).↵
↵
Итоговая асимптотика: $\mathcal{O}(n \log n)$.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359458348]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:6,option1]↵
↵
Хорошая задача [likes:6,option2]↵
↵
Нормальная задача [likes:6,option3]↵
↵
Плохая задача [likes:6,option4]↵
↵
Ужасная задача [likes:6,option5] ↵
</spoiler>↵
↵
↵
↵
[problem:2189E]↵
↵
Идея: [user:Fakewave,2026-01-23], [user:furt1ve,2026-01-23]↵
↵
<spoiler summary="Решение">↵
Сразу скажем, что ответ $-1$, если строка состоит из $0$.↵
↵
Пусть мы сделали $k$ операций, $i$-я из которых стоила $a_i$. Тогда $(a_1-1)+(a_2-1)+\cdots+(a_k-1) = n-1$ (количество символов, которые надо удалить), откуда $cost = a_1+a_2+\cdots+a_k=n-1+k$. То есть задача переходит в найти наименьшее число операций $k$, для достижения цели. Ответ будет $n-1+k$.↵
↵
Покажем, что $k \leq 4$. Пусть $s_i = 1$. Заменим подстроки $[1, i-1]$ и $[i+1, n]$ на какие-нибудь символы. Теперь у нас строка $x1y$. Заменим подстроку $[1, 2]$ на $1$, получится строка $1y$. Остается заменить её на строку $1$.↵
↵
↵
Теперь разберемся, когда минимальное число операций это $k = 0, 1, 2, 3$ (иначе $k = 4$).↵
↵
Под \textbf{разностью} строки будем подразумевать разность между количеством единиц и нулей.↵
↵
Утверждается, что за $k$ операций можно сделать, если:↵
↵
1. $k = 0$↵
Когда $s = 1$.↵
↵
2. $k = 1$↵
Разность строки неотрицательная.↵
↵
3. $k = 2$↵
В строке есть префикс/суффикс с положительной разницей (тогда оставшуюся часть можно заменить на любой символ и после этого перевести всю строку в $1$) или разность строки равна $-1$ (тогда если первое условие не выполнено, то можно сделать операцию замены подстроки $[1, n-1]$ на $1$ (ведь её разность $0$, т.к. $s_n = 0$), получится строка $10$, которую можно перевести в $1$ одним действием).↵
↵
4. $k = 3$↵
В строке есть префикс/суффикс с неотрицательной разницей (тогда оставшуюся часть можно заменить на $0$, эту часть на $1$ и получится строка $10$ или $01$, дальше достаточно одной операции) или есть $2$ единицы подряд (тогда заменим префикс и суффикс до них на что-то, получится строка с разницей $\geq 0$, которую можно перевести в $1$).↵
↵
↵
5. $k = 4$↵
Иначе.↵
Перейдем к доказательствам для $k \geq 2$.↵
↵
#### $k = 2$↵
↵
Предположим, что нельзя за $k < 2$ операции и можно за $k = 2$, при условии что разница не $-1$ и нет префикса/суффикса с положительной разницей.↵
Если первая операция — префикс или суффикс, то в этой подстроке разница $\geq 0$. Чтобы после этого можно было победить за $1$ операцию, в оставшейся части должна быть разница $-1$ (т.к. если разница $\geq 0$, то разница всей изначальной строки неотрицательная, а если $< -1$, то суммарная разница после $1$ операции $<0$). Тогда разница всей строки тоже $-1$. Если же первая операция какая-то другая, то после операции разница $\leq -1 + 1 + -1 = -1$ (префикс + подстрока + суффикс). То есть победить не получится.↵
↵
#### $k = 3$↵
↵
Предположим, что нельзя за $k < 3$ операции и можно за $k = 3$, при условии что нет префикса/суффикса с неотрицательной разницей и нет двух единиц подряд.↵
↵
Пусть изначально разность равна $z$. Пусть мы делаем операцию с подстрокой $l$, $r$. Тогда пусть в подстроке $1$, $l-1$ разность равна $a < 0$, в подстроке $l$, $r$ равна $b$, а в подстроке $r+1$, $n$ равна $c < 0$.↵
↵
Если $b = 0$, то теперь разность становится $a+1+c$.↵
↵
Пусть $a+c+1 = -1$. Тогда так как $a + c = -2$ и $a,c \leq -1$, то $a = -1$ и $c = -1$. Но тогда если подстрока $l$, $r$ начинается с $0$ и заканчивается $0$ (иначе префикс $1\ldots l$ или суффикс $r\ldots n$ имеет разность $\geq 0$). Но тогда подстрока $l+1$, $r-1$ имеет разность $2$. Тогда размер этой подстроки четный (ведь если нулей $x$, то единиц $2+x$, а значит всего символов $2+2x$). Поделим символы на пары соседних $(l+1, l+2; \dots; r-2, r-1)$. В каждой из них разность $\leq 0$ (т.к. не $2$ единицы), а значит разность этой подстроки не равна $2$. Значит, такое невозможно.↵
↵
Другой случай: появится положительный префикс/суффикс (не ограничивая общности, префикс). ($l$, $r$ — не префикс и не суффикс, т.к. $b = 0$).↵
↵
Заметим, что получившийся положительный префикс $T$. Понятно, что $T$ будет содержать $1$ (которую получили из $b$) и ещё что-то из суффикса $r+1 \ldots n$ (обозначим его за $M$), причём это что-то имеет разность $> 0$. Тогда если эта разность $d$, то у $T$ разность $a+1+d \geq 1$. Тогда $a+d \leq 0$. Ранее мы показали, что $d \leq 1$ (иначе есть $2$ единицы подряд). Тогда $a \geq -1$. Значит, $a = -1$. Тогда $M$ начинается с $0$ (иначе $a+b+1 = 0$ и мы имеем префикс $\geq 0$). Тогда оставшийся используемый префикс $M$ имеет разность $2$, а значит содержит $2$ подряд идущие единицы — противоречие.↵
↵
$b < 0$.↵
↵
Если разность становится $-1$, то тогда теперь разность равна $a-1+c$. $a-1+c = -1 \implies a+c = 0$, что невозможно.↵
↵
Другой случай: появится положительный префикс/суффикс (не ограничивая общности, префикс).↵
↵
- Пусть $l = 1$. Тогда после этого суффикс $r+1, \ldots, n$. Теперь получается $0$ + префикс из $M$. Но тогда этот префикс должен иметь разность $\geq 2 \implies$ есть $2$ единицы — противоречие.↵
↵
- Иначе мы содержим префикс $1 \ldots (l-1)$ + $0$ (полученный из $b$) + префикс $(r+1 \ldots n)$ (обозначим его за $M$). Тогда этот префикс должен иметь разность $\geq 3$ (т.к. у $1 \ldots (l-1)$ разность $\leq -1$, а ещё и $0$ появляется). Тогда есть $2$ единицы подряд — противоречие.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359458367]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:7,option1]↵
↵
Хорошая задача [likes:7,option2]↵
↵
Нормальная задача [likes:7,option3]↵
↵
Плохая задача [likes:7,option4]↵
↵
Ужасная задача [likes:7,option5] ↵
</spoiler>↵
↵
↵
↵
[problem:2189F]↵
↵
Идея: [user:yanb0,2026-01-23]↵
↵
<spoiler summary="Решение">↵
Будем называть вершину мёртвой, если в ней $0$ гаек, и при подвешивании за неё среди поддеревьев её детей не больше одного поддерева с положительной суммой количеств гаек.↵
↵
Будем записывать операцию перемещения для вершины $v$ как $\operatorname{c}(v)$. ↵
↵
Пусть $A$ — лес, состоящий из всех живых вершин. Докажем, что $A$ всегда связный, т.е. является деревом. Если для противоречия $A$ состоит хотя бы из двух компонент связности, на пути между ними должна найтись мёртвая вершина $v$, но с другой стороны $v$ живая, т.к. обе компоненты связности находятся в разных поддеревьях детей $v$ при подвешивании за $v$, противоречие, ч.т.д.↵
↵
Пусть $\deg(v)$ — степень вершины $v$ в $A$. Несложно заметить, что при применении $\operatorname{c}(v)$, $a_v := a_v + \deg(v)$, а для всех остальных вершин $u \in A$, $a_u := a_u + \deg(u) - 2$. Если $v \not \in A$, то $a_v := a_v + 1$, $a_u := a_u + \deg(u) - 2$, $a_p := a_p + \deg(p) - 1$, где $p$ — ближайшая к $v$ вершина из $A$. $[*]$↵
↵
Для последовательности действий определим дерево $L$ как $A$ в момент после всех операций $\operatorname{c}(v)$ и до съедения гаек.↵
↵
Пусть у нас есть последовательность операций (включая съедение), приводящая к тому, что гаек не останется. Докажем, что последнюю из операций $\operatorname{c}(v)$, где $v \not \in L$, можно заменить на операцию $\operatorname{c}(u)$, где $u \in L$, при этом $A$ станет своим нестрогим подмножеством, и гаек опять же не останется. Рассмотрим момент перед применением $\operatorname{c}(v)$. Есть два варианта:↵
↵
1. $v$ жива. Тогда при замене $\operatorname{c}(v)$ на $\operatorname{c}(u)$, $a_v$ уменьшится на $2$, а $a_u$ увеличится на $2$ по $[*]$.↵
↵
2. $v$ мертва. Пусть $p$ — ближайшая к $v$ вершина из $A$. Тогда при замене $\operatorname{c}(v)$ на $\operatorname{c}(u)$, $a_v$ и $a_u$ уменьшатся на $1$ (станут равными $0$), а $a_p$ увеличится на $1$ по $[*]$. ↵
↵
В обоих случаях, все $a_x$ для $x \not \in L$ уменьшатся, и несложно видеть, что последовательность операций после $\operatorname{c}(v)$ также приведёт все гайки в $L$, после чего те же самые операции съедения уберут все гайки, ч.т.д. Таким образом, все операции типа $\operatorname{c}(v)$, где $v \not \in L$, можно (последовательно с конца) заменить на $\operatorname{c}(u)$ для некоторых $u \in L$.↵
↵
Теперь остаётся решить следующую задачу:↵
↵
Нужно выбрать поддерево $L$ изначального дерева, потом несколько раз применить $\operatorname{c}(u)$, $u \in L$, чтобы сделать все вершины не из $L$ мёртвыми, а затем применить операцию съедения для всех $v \in L$. Заметим, что по $[*]$ все вершины не из $L$ станут мёртвыми вне зависимости от того, какие вершины $L$ мы выбираем, иными словами, можно применять все $\operatorname{c}(v)$ только к одной вершине $v$.↵
↵
Представим динамику по ориентированным рёбрам $xy$, $dp[x][y]$: наименьшее количество операций $\operatorname{c}(v)$, где $v$ со стороны $x$ от $xy$, нужное, чтобы сделать все вершины со стороны $y$ (включая $y$) от $xy$ мёртвыми. Значение $a_y$ может уменьшаться только когда $\deg(y) = 1$, поэтому $dp[x][y] = \sum_{i=0}^{k}\Bigl(dp[y][ch[i]]\Bigr)$, то есть $dp[x][y]$ равно сумме $a_v$ по всем $v$ в поддереве $y$, если подвесить всё дерево за $x$.↵
↵
Для всех вершин $v \not \in L$ в какой-то момент и всегда после него $a_v = 0$, а ещё возможно, что $a_v = 0$ перед всеми операциями, больше никогда $a_v$ не равно $0$.↵
↵
Определим $zero[y]$ как наименьшее количество операций $\operatorname{c}(v)$, нужное, чтобы $a_y = 0$ после любого количества операций $\operatorname{c}(v)$, не меньшем $zero[y]$. $zero[y] = \min_x({dp[x][y]})$ для всех $x$, смежных с $y$, и $zero[y] = 0$, если изначально $a_y = 0$ и $\deg(y) = 2$. Это так, потому что если $a_y \ne 0$ или $\deg(y) \ne 2$, $y$ окончательно "обнулится", только когда станет мёртвой. $\min_x({dp[x][v]})$ больше $dp[v][u]$ для всех, возможно, кроме одной, вершин $u$, смежных с $v$, а значит, больше $\min_t({dp[t][u]})$ для $t$, смежных с $u$, смежных с $v$. Значит, применяя $\operatorname{c}(v)$ к $v$ с наибольшим $zero[v]$, каждое $a_u$ станет равным $0$ после $zero[u]$ операций.↵
↵
Таким образом, либо операций $\operatorname{c}(x)$ нет, и операцию съедения нужно применить ко всем $y$ с начальным $a_y = 0$, либо операций $\operatorname{c}(x)$ $k$, и операцию съедения нужно применить ко всем вершинам $y$ с $zero[y] \ge k$. Для первого случая просто посчитаем стоимость этой последовательности операций, а для второго случая за $O(n \log n)$ отсортируем $zero$, после чего переберём количество "обнулённых" вершин, пробегаясь по $zero$, будем считать ответ как $(n - i) \cdot q + zero[i - 1] \cdot p$. Ответом на задачу будет минимальный из полученных.↵
↵
Суммарная асимптотика: $O(n \log n)$.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
[submission:359458396]↵
</spoiler>↵
↵
<spoiler summary="Оцените задачу">↵
Отличная задача [likes:8,option1]↵
↵
Хорошая задача [likes:8,option2]↵
↵
Нормальная задача [likes:8,option3]↵
↵
Плохая задача [likes:8,option4]↵
↵
Ужасная задача [likes:8,option5] ↵
</spoiler>↵
↵
