Спасибо за участие в раунде! Мы надеемся, что вам понравились задачи. Нам очень жаль, что с условием в задаче B возникли проблемы.
Идея: Fakewave
Заметим, что максимизация суммы чисел в таблице равносильна максимизации количества пар чисел, которые образуют клетку таблицы.
Не ограничивая общности, будем считать, что $$$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$$$ пар.
Заметим, что задача равносильна минимизации откатов для достижения точки с числом $$$\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$$$ откатов.
2189C1 - XOR Convenience (Easy Version)
Идея: Fakewave
Будет скоро добавлено.
2189C2 - XOR-convenience (Hard Version)
Будет скоро добавлено.
2189D1 - Little String (Easy Version)
Рассмотрим, какие перестановки $$$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)$$$.
2189D2 - Little String (Hard Version)
Из 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$$$.
Рассмотрим два случая.
- $$$c'$$$ — степень $$$2$$$. Для всех чётных $$$j$$$ выберем умножать на $$$2$$$, т.к. умножение на $$$2$$$ вместо положительного чётного числа не вызовет делимость и не увеличит произведение. Остаётся жадно выбирать умножение на $$$2$$$ для наибольших из оставшихся $$$j$$$, пока это возможно ($$$c'$$$ всё ещё не делит $$$x$$$), чтобы минимизировать $$$x$$$.
- $$$c'$$$ — не степень $$$2$$$. Тогда выбирая каждый раз умножение на $$$2$$$, $$$x$$$ не поделится на $$$c'$$$, а произведение будет минимальным, т.к. каждый раз мы выбирали меньший из возможных множителей ($$$2 \le j$$$).
Итоговая асимптотика: $$$\mathcal{O}(n \log n)$$$.
Сразу скажем, что ответ $$$-1$$$, если строка состоит из $$$0$$$.
Пусть мы сделали $$$k$$$ операций, $$$i$$$-я из которых стоила $$$a_i$$$. Тогда $$$(a_1-1)+(a_2-1)+..+(a_k-1) = n-1$$$ (количество символов, которые надо удалить), откуда $$$cost = a_1+a_2+..+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$$$ операций можно сделать, если:
$$$k = 0$$$ Когда $$$s = 1$$$.
$$$k = 1$$$ Разность строки неотрицательная.
$$$k = 2$$$ В строке есть префикс/суффикс с положительной разницей (тогда оставшуюся часть можно заменить на любой символ и после этого перевести всю строку в $$$1$$$) или разность строки равна $$$-1$$$ (тогда если первое условие не выполнено, то можно сделать операцию замены подстроки $$$[1, n-1]$$$ на $$$1$$$ (ведь её разность $$$0$$$, т.к. $$$s_n = 0$$$), получится строка $$$10$$$, которую можно перевести в $$$1$$$ одним действием).
$$$k = 3$$$ В строке есть префикс/суффикс с неотрицательной разницей (тогда оставшуюся часть можно заменить на $$$0$$$, эту часть на $$$1$$$ и получится строка $$$10$$$ или $$$01$$$, дальше достаточно одной операции) или есть $$$2$$$ единицы подряд (тогда заменим префикс и суффикс до них на что-то, получится строка с разницей $$$\geq 0$$$, которую можно перевести в $$$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..l$$$ или суффикс $$$r..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..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,.., n$$$. Теперь получается $$$0$$$ + префикс из $$$M$$$. Но тогда этот префикс должен иметь разность $$$\geq 2 \implies$$$ есть $$$2$$$ единицы — противоречие.
Иначе мы содержим префикс $$$1..(l-1)$$$ + $$$0$$$ (полученный из $$$b$$$) + префикс $$$(r+1..n)$$$ (обозначим его за $$$M$$$). Тогда этот префикс должен иметь разность $$$\geq 3$$$ (т.к. у $$$1..(l-1)$$$ разность $$$\leq -1$$$, а ещё и $$$0$$$ появляется). Тогда есть $$$2$$$ единицы подряд — противоречие.
2189F - Zhora the Vacuum Cleaner
Идея: yanb0
Будем называть вершину мёртвой, если в ней $$$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)$$$. Есть два варианта:
$$$v$$$ жива. Тогда при замене $$$\operatorname{c}(v)$$$ на $$$\operatorname{c}(u)$$$, $$$a_v$$$ уменьшится на $$$2$$$, а $$$a_u$$$ увеличится на $$$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)$$$.
