1. На раунд было предложено суммарно 30 задач

2. E задумывалась как C, а C — как B

Заметим, что максимизация суммы чисел в таблице равносильна максимизации количества пар чисел, которые образуют клетку таблицы.

Не ограничивая общности, будем считать, что $$$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 \lt y \leq l$$$, и будет $$$cnt_h$$$ пар. Это получится сделать, так как подходящих чисел $$$y$$$ не меньше, чем подходящих $$$x$$$.

• если $$$\displaystyle cnt_h \gt \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$$$, то нужно в пару каждому числу $$$h \lt y \leq l$$$ дать в пару своё число $$$x \leq h$$$. После этого разбить оставшиеся числа $$$x \leq h$$$ на пары (возможно, останется одно лишнее число). Получится как раз $$$\displaystyle \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$$$ пар.

359457886

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

Заметим, что задача равносильна минимизации откатов для достижения точки с числом $$$\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$$$ откатов.

359458220

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

Во первых, заметим, что $$$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]$$$.

359458251

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

Во первых, докажем, что при $$$n = 2^x$$$ ($$$x$$$ — целое) не существует примера.

Пусть $$$n$$$ стоит на позиции $$$i$$$. Предположим, что $$$i \lt n$$$. Тогда $$$p_i \oplus i= p_j $$$, для некоторого $$$j$$$. Но $$$p_i \oplus i \geq n$$$, ведь $$$p_i = n = 2^x$$$, а $$$p_j \lt 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 \lt 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 \gt r$$$.

Остается проверить, что $$$i = 1$$$ имеет подходящее $$$j$$$. Возьмем $$$j = r + 1$$$. $$$n$$$ — четное, а значит $$$r$$$ — четное. Тогда $$$p_j = r$$$ и $$$p_1 = r+1$$$. Действительно: $$$r+1 = r\oplus 1$$$.

359458288

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

Рассмотрим, какие перестановки $$$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}$$$ этого отрезка, поскольку все последующие значения $$$ \gt k$$$).

Если же мы вставим $$$k$$$ между какими-то значениями, то мы получим ситуацию, что у нас и слева, и справа от $$$k$$$ есть значение, которое $$$ \lt k$$$. Тогда, чтобы получить $$$\operatorname{mex} = k$$$, нам надо набрать все числа $$$ \lt k$$$, но поскольку они есть и слева, и справа, мы включим $$$k$$$, и получим $$$\operatorname{mex} \gt k$$$.

Итого, у нас есть $$$2$$$ варианта, как обеспечить $$$w_k=1$$$, и $$$k-1$$$ вариант для $$$w_k=0$$$. Мы получили, что

В этой версии задачи $$$w = s$$$, а значит нужно лишь проверить, делится ли $$$f(w)$$$ на $$$c$$$. Для этого пройдемся по всем $$$i$$$ и будем сокращать $$$c$$$ на наибольший общий делитель очередного множителя и числа $$$c$$$. Если в итоге получилось $$$c = 1$$$, то ответ $$$-1$$$. Иначе ответ $$$f(w)$$$.

359458322

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

Из D1 имеем:

Посчитаем произведение членов-множителей для всех символов $$$s$$$, которые даны (\texttt{0} или \texttt{1}), назовём это число $$$b$$$; произведение остальных членов назовём $$$x$$$. Остальные символы мы можем выбирать, то есть нам нужно найти наименьшее значение

не делящееся на $$$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)$$$.

359458348

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

Сразу скажем, что ответ $$$-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$$$).

1. $$$k = 4$$$ Иначе. Перейдем к доказательствам для $$$k \geq 2$$$.

$$$k = 2$$$

Предположим, что нельзя за $$$k \lt 2$$$ операции и можно за $$$k = 2$$$, при условии что разница не $$$-1$$$ и нет префикса/суффикса с положительной разницей. Если первая операция — префикс или суффикс, то в этой подстроке разница $$$\geq 0$$$. Чтобы после этого можно было победить за $$$1$$$ операцию, в оставшейся части должна быть разница $$$-1$$$ (т.к. если разница $$$\geq 0$$$, то разница всей изначальной строки неотрицательная, а если $$$ \lt -1$$$, то суммарная разница после $$$1$$$ операции $$$ \lt 0$$$). Тогда разница всей строки тоже $$$-1$$$. Если же первая операция какая-то другая, то после операции разница $$$\leq -1 + 1 + -1 = -1$$$ (префикс + подстрока + суффикс). То есть победить не получится.

$$$k = 3$$$

Предположим, что нельзя за $$$k \lt 3$$$ операции и можно за $$$k = 3$$$, при условии что нет префикса/суффикса с неотрицательной разницей и нет двух единиц подряд.

Пусть изначально разность равна $$$z$$$. Пусть мы делаем операцию с подстрокой $$$l$$$, $$$r$$$. Тогда пусть в подстроке $$$1$$$, $$$l-1$$$ разность равна $$$a \lt 0$$$, в подстроке $$$l$$$, $$$r$$$ равна $$$b$$$, а в подстроке $$$r+1$$$, $$$n$$$ равна $$$c \lt 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$$$), причём это что-то имеет разность $$$ \gt 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 \lt 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$$$ единицы подряд — противоречие.

359458367

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

Будем называть вершину мёртвой, если в ней $$$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)$$$.

359458396

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача