Рассмори одну полоску длины $$$k$$$ из символов '#'. Сколько времени нужно, чтобы ее стереть? Что происходит за одну секунду?

За одну секунду мы стираем 2 символа '#' (или 1, если был всего один символ). Тогда через сколько времени мы все сотрем?

Через $$$\lceil\frac{k}{2}\rceil$$$ секунд. Тогда чему равен ответ?

Мы должны найти самую длинную полоску из подряд идущих символов '#' и вычислить ответ по формуле из предыдущего шага.

В условии написано, что мы можем перекладывать единицы слева направо, тогда что логичнее всего можно сделать?

Логичнее всего строить последовательность слева направо. Пойдем слева направо. Пусть мы стоим в позиции $$$i$$$, тогда какую оптимальную высоту мы хотим получить здесь?

Какое ограничение снизу на $$$a_i$$$ мы можем записать?

Запишем последовательность $$$(1,2,\ldots, n)$$$ -- это возрастающая последовательность с минимальными выстоами башен, тогда $$$a_i \ge i$$$, то есть мы хотим сделать $$$a_i$$$ равным $$$i$$$.

Тогда будем поддерживать количество единиц $$$S$$$, которые мы можем перенести с башен до $$$i$$$-й. Что делаем, если $$$a_i \gt i$$$?

Если $$$a_i \gt i$$$, тогда мы можем увеличить $$$S$$$ на $$$(a_i - i)$$$ и пойти дальше (и уменьшить $$$a_i$$$ до $$$i$$$). А что если $$$a_i \lt i$$$?

Тогда нам нужно увелчить высоту башни, потратив $$$(i - a_i)$$$. Тогда если $$$S \lt (i - a_i)$$$, то ответа нет, а иначе уменьшаем $$$S$$$ на $$$(i - a_i)$$$ и идем дальше.

В задачах на сортировку очень часто помогает придумать способ обменять местами какие-то две элемента $$$(i,j)$$$. Попробуем поприменять описанные в условии операции несколько раз.

Мы можем обменивать $$$(i, i + x)$$$ и $$$(i, i + y)$$$, тогда какие два элемента мы еще можем обменять?

Тогда мы можем обменять $$$(i, i + x)$$$, дальше обменять $$$(i, i + y)$$$, а затем опять $$$(i, i + x)$$$, тогда мы по сути обменяли местами $$$(i + x, i + y)$$$ или другими словами $$$(i, i + (x - y))$$$. На что это похоже?

Как работает простейший алгоритм Евклида?

Алгоритм Евклида гласит, что $$$gcd(x, y) = gcd(x, y - x) = \ldots$$$. А если хотите больше узнать о нетривиальных применениях этого алгоритма, рекомендую прочитать ЭТОТ ПОСТ и присоединиться к нам в сообщество)

Из шагов выше получаем, что мы можем обменять местами любые два индекса $$$(i,j)$$$, что $$$|i - j|$$$ делится на $$$gcd(x, y)$$$. Как нам это помогает?

Это значит, что мы можем отсортировать подпоследовательности $$$i_1 \lt i_2 \lt \ldots$$$, которые имеют одинаковые остаток от деления на $$$gcd(x, y)$$$. Сдеаем это и проверим, что итоговая последовательность отсортировалась.

Решим задачу попроще: допустим мы можем изменить знак любого префикса, чему тогда равен ответ?

Тогда ответ равен \sum |a_i|, как его получить?

Если $$$a_n \lt 0$$$, то мы можем поменять знак у префикса $$$[1 \ldots n]$$$ и перейти к вычислению ответа на массиве $$$(a_1,a_2,\ldots,a_{n-1})$$$, потому дальнейшие изменения никак не повлияют на $$$a_n$$$.

Возвращаемся к нашей задаче. Какие элементы мы никогда не сможем изменить?

Пусть $$$B = \max b_j$$$ — максимальный префикс, который мы можем изменить. Тогда все элемент $$$a_i$$$, что $$$i \gt B$$$ мы не можем изменить, значит мы можем добавить к ответу их сумму и забыть про них, теперь считаем, что мы можем поменять все элементы местами. Идем дальше. Какие элементы всегда будут меняться одинаково? (то есть нельзя изменить знак одного элемента без изменения второго)

Пусть $$$b_1 \lt b_2 \lt \ldots \lt b_m$$$, тогда элементы $$$[1,b_1]$$$ всегда будут меняться одинаково, а еще какие?

Рассмотрим блоки $$$[1, b_1], [b_1+1,b_2], [b_2+1,b_3], \ldots,[b_{m-1}+1,b_m]$$$. Элементы в каждом блоке всегда будут меняться одинаково, тогда что мы можем сделать?

Тогда мы можем вычислить сумму элементов в каждом блоке и перейти к задаче из Шага 1, тогда как посчитать ответ?

Пусть $$$S_i$$$ — сумма элементов в блоке $$$[b_{i-1}+1,b_i]$$$, тогда ответ $$$\sum |S_i|$$$

Давайте формально запишем, что то нас хотят в условии. Пусть $$$f_i = 1$$$, если $$$s_i = s_{i-1}$$$ и $$$f_i = 0$$$ иначе. Тогда что от нас хотят в условии? Что означает операция выбора отрезка $$$[l,r]$$$? Что при этом меняется и как?

Такая оперция изменяет $$$f_l$$$ с 0 на 1 и наоборот, а также меняет $$$f_{r+1}$$$ с 0 на 1 и наоборот. То есть по сути за одну операцию мы можем изменить какие-то два элемента $$$f_i,f_j$$$ (или один, если отрезок — это префикс или суффикс). Как нам это помогает?

Пусть к нам пришел запрос $$$l,r,k$$$. Пусть $$$x = \sum_{i=l+1}^{r}f_i$$$. Тогда как определить ответ?

В таком случае минимальное количество операций равно $$$\lceil\frac{x}{2}\rceil$$$, остается сравнить его с $$$k$$$. А чтобы посчитать $$$x$$$ достаточно предподсчитать префиксные суммы.

Рассмотрим некоторую вершину $$$v$$$ и ее поддерево, пусть в ее поддереве находятся числа $$$x_1 \lt x_2 \lt \ldots \lt x_l$$$. Какое свойство должно выполнятьcя?

Должно выполняться, что эти числа должны образовывать отрезок, как проверить это свойство?

Должно выполнться равенство $$$x_l-x_1+1=l$$$. Хорошо, осталось еще учесть то, что мы теперь можем циклически сдвигать всех сыновей.

Мы хотим отсортировать все элементы, но мы можем делать только циклические сдвиги, а еще мы знаем, что все поддеревья хранят непрерывный отрезок чисел. Как тогда мы можем отсортировать эти числа?

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

Если нарисовать картинку, то можно заметить, что удобно работать с отрезками $$$(i - a_i, i + a_i)$$$, тогда что будет означать условие |i — j| > max(a_i, a_j)?

Пусть $$$i \gt j$$$, тогда условие переписывается как i > j + a_i И $$$i - a_i \gt j$$$, то есть никакой центр никакого отрезка не покрывается каким-то другим отрезком. Отлично, в задачах про отрезки важно спросить себя, могут ли быть вложенные отрезки?

Нет, не могут, т.к. иначе центр одного отрезка покровется бОльшим отрезком, тогда мы можем отсортировать отрезки по правой границе (по $$$i + a_i$$$). Что тогда? Пусть мы после сортировки выбрали отрезки $$$\ldots (l_1,r1), (l_2,r_2), (l_3, r_3)$$$, нужно ли нам проверять свойство выше для отрезков $$$(l_1,r1), (l_3,_r3)$$$, если мы знаем, что все соседние отрезки удовлетворяют условиям выше?

Нет, не нужно, потому что мы знаем, что центры отрезков $$$(l_1,r_1)$$$ и $$$(l_3,r_3)$$$ лежат по разные стороны от отрезка $$$(l_2,r_2)$$$, а значит не может быть так, что центр одного отрезка покрыт вторым отрезком, потому что $$$l_1 \lt l_2 \lt l_3$$$ и $$$r_1 \lt r_2 \lt r_3$$$, это удобное свойство возникает из-за того, что не может быть вложенных отрезков в ответе.

После сортировки логичным шагом является применение динамического программирования, стандартный подход в поиске подпоследовательностей максимальной длины с какими-то свойствами.

Итак, допустим мы отсортировали отрезки по правой границе: $$$(l_1,r_1),(l_2,r_2),\ldots, (l_2,r_n)$$$. Тогда пусть $$$dp_i$$$ — длина максимальной подпоследовательности, заканчивающейся в $$$i$$$-м отрезке. Ответ равен $$$\max dp_i$$$. Изначально можем проставить $$$dp_i = 1$$$ для всех $$$i$$$. Осталось только придумать переход.

Пусть центр $$$i$$$ — го отрезка равен $$$c_i = (l_i + r_i) / 2$$$ Пусть мы хотим посчитать $$$dp_i$$$. Тогда в медленном решении мы бы хотели перебрать $$$j \lt i$$$ , что $$$c_j \lt l_i$$$ и $$$r_j \lt c_i$$$. Что мы можем сделать? Как найти такие $$$j$$$, что $$$r_j \lt c_i$$$?

Вспомним, что наши отрезки отсортированы по $$$r_i$$$, тогда мы можем бинарным поиском найти максмальное $$$q$$$, что $$$r_q \lt c_i$$$, тогда для всех $$$j \le q$$$ будет верно, что $$$r_j \lt c_i$$$. Осталось разобраться с условием $$$c_j \lt l_i$$$.

(возможно, есть вариант проще), но для этого я использую персистентное дерево отрезков. То есть я для каждого $$$i$$$ знаю дерево отрезков $$$T_i$$$, которое хранит в позициях $$$c_j$$$ значения $$$dp_j$$$ для всех $$$j \le i$$$. Тогда для обновления $$$dp_i$$$ мне достаточно найти максимум в префиксе $$$[0, l_i - 1]$$$ в ДО $$$T_q$$$.

В условии несколько раз намекнули, что $$$n$$$ -- четное число. Как мы можем это использовать?

Мы можем попробовать придумать перестановку, что $$$c_{final}$$$ всегда будет четным, тогда он не может стать единицой. Как это сделать?

Раз $$$n$$$ -- четное, то мы можем поставить на четные позиции нечетные числа и наоборот. Например, вот так: $$$2,1,4,3,\ldots,n,n-1$$$. Почему это работает?

Это рабтоает, потому что тогда $$$i\cdot p_i \equiv 0 \pmod{2}$$$ для любого $$$i$$$, значит и вся сумма тоже будет всегда четной.

Первое, что пришло в голову — это последовательность $$$2,2,4,8,16,\ldots$$$, тогда сумма всех чисел — это большая степень двойки, а все элементы тоже степени двойки. У этой последовательности есть замечательное свойство, а именно каждый следующий элемент равен сумме предыдущих. Но здесь есть проблема, какая?

Все элементы должны быть разные. Хорошо, каким образом мы можем это сделать?

В шаге один мы получили свойство, что $$$a_{i+1}=a_1+a_2+\ldots a_i$$$. То есть теперь мы можем строить $$$a$$$ итеративно. Но для этого надо задать первые два числа, поставим туда $$$1,2$$$. Тогда итоговая последовательность будет равна $$$1,2,3,6,12,24,\ldots$$$. Легко проверить, что она подходит.

Первое, что мы видим — это то, что написано в условии, а именно, что исходный массив не убывает, тогда любая подпоследовательность тоже неубывает, что это нам дает?

Рассмотрим какую-нибудь подпоследовательность $$$b_1,b_2,\ldots,b_k$$$. Тогда сумма будет равна $$$b_1-b_2+b_3-b_4+\ldots$$$. Что это нам дает?

Как можно оценить сумму, если $$$k$$$ — четно? А если $$$k$$$ — нечетно?

Если $$$k$$$ четно, тогда мы можем разбить сумму на пары $$$(b_1-b_2)+(b_3-b_4)+\ldots$$$. Тогда видно, что сумма не может быть больше нуля, т.к. $$$b_i \le b_{i+1}$$$. А для нечетных $$$k$$$?

Для нечетных $$$k$$$ можно сделать почти то же самое, а именно представить сумму как $$$b_1 + (b_3-b_2) + (b_5-b_4) + \ldots$$$. Тогда если $$$b_1 \gt 0$$$, то сумма строго больше нуля, значит $$$b_1 = -1$$$ а остальная сумма равна единице. Хорошо, как теперь считать ответ для четных $$$k$$$?

Если $$$k$$$ четное, тогда мы хотим, чтобы $$$b_1=b_2,b_3=b_4,\ldots$$$. Давайте разобьем весь массив на блоки из одинаковых чисел и выпишем массивы $$$A_i,B_i$$$, где $$$A_i$$$ — это значение блока, а $$$B_i$$$ — размер блока. Например, если массив был $$$-1,-1,-1, 1, 1, 2,2,2,2,2,3,3,3,4$$$, тогда $$$A = (-1,1,2,3,4), B = (3, 2, 5, 3, 1)$$$.

Это означает, что мы из каждого блока хотим выбрать четное число элементов. Из блока $$$i$$$ это можно сделать $$$C_i$$$ способами, где $$$C_i = \sum_{k=0}^{B_i/2}\binom{C_i}{2k}$$$. Тогда общее количество четных подпоследовательностей равно $$$X = \prod_i C_i$$$.

Теперь решим для нечетных $$$k$$$. Мы хотим, чтобы $$$b_1=-1$$$, а также для остальных пар $$$(b_2,b_3),(b_4,b_5)$$$ должно быть верно, что все пары кроме одной состоят из одинаковых чисел, то есть есть такое $$$i$$$, что для остальных $$$j \neq i$$$ верно, что $$$b_{2j}=b_{2j+1}$$$, а для $$$i$$$ верно, что $$$b_{2i}+1=b_{2i+1}$$$. То есть мы хотим из первого блока минус единичек выбрать нечетное число элементов, далее из остальных блоков мы хотим выбрать четное число элементов, но также должна быть пара соседних блоков $$$(i, i+1)$$$, что $$$A_i+1=A_{i+1}$$$ и из этих блоков мы хотим выбрать уже нечетное число элементов. Как это посчитать?

Пусть $$$D_i$$$ — количество способов выбрать нечетное число элементов из $$$i$$$-го блока. Мы знаем, что $$$A_1=-1$$$ (так должно быть , иначе ответ 0).

Пусть $$$X = D_1\cdot\prod_{i=2}C_i$$$. Тогда общее количество способов выбрать нечетную подпоследовательность равно сумме по всем $$$i$$$, что $$$A_i+1=A_{i+1}$$$ величин $$$\frac{X}{C_i\cdot C_{i+1}}\cdot {D_i\cdot D_{i+1}}$$$. То есть мы перебираем пару соседних блоков, значения которых отличаются на единицу и делаем так, чтобы только в этих блоках мы выбираем нечетное число элементов.

Допустим Алиса уже увеличила некоторые элементы исходного массива и начинается игра. Сколько максимум операций может быть в теории, какую грубую оценку можно сделать?

Пусть $$$f(x)$$$ — количество операций, которое нужно сделать Алисе с одним числом $$$x$$$ до конца игры. Чтобы вычислить $$$f(x)$$$ достаточно проэмулировать то, что написано в условии, а именно делить каждый раз когда $$$x$$$ четное и вычитать единицу, когда $$$x$$$ нечетное. Тогда, очевидно, что ответ не может быть больше $$$\sum\limits_{i=1}^{n}f(a_i)$$$. Но эта оценка слишком грубая. Как сделать лучше? На что не может повлиять Боб?

Пусть $$$g(a)$$$ — максимальное число $$$k$$$, что все числа $$$a_i$$$ делятся на $$$2^k$$$. То есть если мы для каждого числа в массиве посчитаем сколько раз его надо поделить на два прежде чем оно станет нечетным и в конце возьмем минимум по таким числам, то получим $$$g(a)$$$. Так вот, как бы Боб не переставлял числа, Алиса всегда будет сначала $$$g(a)$$$ раз делить все числа массива на два. Значит, как можно оценить ответ?

Ответ не больше $$$\sum f(a_i) - g(a)\cdot (n - 1)$$$, потому что в первой сумме мы лишний раз посчитали $$$g(a)$$$, причем сделали это $$$(n-1)$$$ раз, т.к. все числа будет делить одновременно на два ровно $$$g(a)$$$ раз, значит делений на два будет не $$$n\cdot g(a)$$$, а $$$g(a)$$$, значит экономим $$$n\cdot g(a) - g(a) = g(a)\cdot(n - 1)$$$ операций. Хорошо, может ли Боб гарантировать такую оценку?

Да, может, как он это может сделать? Представим, что мы поделили все числа на два и теперь в массиве есть хотя бы одно нечетное число, как нам оно может помочь?

Боб может поставить нечетное число на вторую позицию перед каждым ходом Алисы, тогда Алиса каждый раз будет менять ровно одно число (тут надо еще аккуратно разобрать случай $$$n=1$$$). Значит оценка достигается, осталось только разобраться с тем, как до начала игры Алиса должна увеличить некоторые элементы массива. Что мы можем перебрать?

Мы можем перебрать $$$g(a)$$$, оно очевидно не будет больше чем $$$O(\log_2{\max{a_i}})$$$. Допустим, мы зафиксировали $$$g(a)$$$, что дальше?

Тогда нам осталось минимизировать $$$\sum f(a_i)$$$, причем мы хотим, чтобы $$$a_i$$$ делилось на $$$2^k$$$. То есть для каждого $$$i$$$ мы хотим заменить его на $$$t\cdot 2^k$$$, заплатив за это $$$t\cdot 2^k - a_i$$$, чтобы потом еще добавить к ответу $$$f(t\cdot 2^k)$$$. То есть мы хотим найти минимум $$$t\cdot 2^k + f(t\cdot 2^k)$$$. Как это можно сделать?

Для фиксированного $$$k$$$ мы можем сначала для каждого $$$t$$$ вычислить $$$t\cdot 2^k + f(t\cdot 2^k)$$$, а затем предподсчитать суффиксные минимумы, т.к. мы хотим, чтобы $$$t\cdot 2^ k \ge a_i$$$.

Чтобы найти $$$b$$$, что нам достаточно узнать?

Нам достаточно знать хотя бы один бит $$$i$$$ у числа $$$v$$$, тогда мы можем сделать $$$m_0=0,m_1=2^i$$$. Попробуем вытащить какой-то из битов. Какой самый простой информативный $$$x$$$ мы можем выбрать? Надо выбрать так, чтобы потом мы смогли отсечь несколько случае, когда мы точно сможем узнать один из битов числа $$$v$$$.

$$$x = 1$$$. Тогда если $$$o(v,x) \gt 1$$$, тогда операция была OR. Что нам это дает?

Это дает нам как раз информацию о каком-то бите числа $$$v$$$. Например, можно взять старший бит числа $$$o(v,x)$$$. Хорошо, а что если $$$o(v,x) = 0 \lt 1$$$?

Тогда мы знаем, что была операция AND, причем бит $$$0$$$ у числа $$$v$$$ обязан быть равен нулю, т.к. иначе $$$1 & 1 = 1 \neq 0$$$. Остался случай $$$o(v,x)=x=1$$$. Что тогда мы можем сказать про число $$$v$$$?

Тогда, если была выбрана операция OR, то $$$v = 0$$$ или $$$v = 1$$$. А если операция AND, то $$$v$$$ — некоторое нечетное число. Можно ли это как-то использовать?

Теперь надо придумать $$$m_0, m_1$$$ такие, что по выражению $$$m_b \oplus v$$$ мы точно сможем определить $$$b$$$. Какие $$$m_0,m_1$$$ выбрать?

Представим, что мы выбрали $$$m_0,m_1$$$ и нам вернули $$$r = v \oplus m_b$$$, как тогда определить $$$b$$$?

Если $$$v = 0$$$, тогда $$$r = m_0$$$ или $$$r = m_1$$$. Если $$$v$$$ — нечетное число, тогда $$$r$$$ и $$$m_b$$$ имеют разную четность. Что отсюда получаем?

Отсюда получаем, что $$$m_0,m_1$$$ должны иметь разную четность, иначе мы не сможем выбрать $$$m_b$$$ при нечетном $$$v$$$. Хорошо, если $$$v$$$ — нечетное число, тогда мы можем определить $$$b$$$, но если $$$v = 0$$$, то тогда $$$r = m_0$$$ или $$$r = m_1$$$. Причем эти два разны случая сложно отличить. Кажется, что для любых фикисрованных $$$m_0,m_1$$$ можно всегда такое решение сломать. То есть пусть мы выдали $$$b$$$, тогда можно подобрать такое $$$v$$$, что $$$o(v,x)=1$$$, но $$$r=m_{b\oplus 1}\oplus v$$$. Как же тогда быть? Как обхитрить интерактор? О чем ему не известно?

В условии написано, что $$$v$$$ выбирается до того, как мы выдадим $$$m_0,m_1$$$. Ему не известно о нашей стратегии выбора $$$m_0, m_1$$$. Тогда мы можем выбрать случайные $$$m_0,m_1$$$ разной четности, тогда если $$$r = m_0$$$ или $$$r = m_1$$$, тогда $$$v = 0$$$ с большой вероятностью (то есть событие, что $$$v \neq 0$$$ и $$$r = m_0$$$ или $$$r = m_1$$$ очень маловероятно, так как такое бывает только тогда, когда например $$$r = m_0 = m_1 \oplus v$$$, то есть $$$v = m_0 \oplus m_1$$$) , иначе выбираем $$$b$$$, смотря на четность чисел $$$r,m_0,m_1$$$. Упражнение: какая вероятность провала?

Вероятность провала равна $$$\frac{1}{2^{29}}$$$, т.к. мы выбираем нечетные $$$v$$$, равные конкретному случайному числу. Значит вероятность успеха на одном примере равна $$$(1 - 1/2^{29})$$$, значит вероятность успеха на одном тесте равна $$$(1 - 1 / 2^{29})^{10^5}$$$, т.к. в одном тесте может быть до $$$10^5$$$ примеров. Воспользуемся замечательным пределом, получим $$$(1 - 1 / 2^{29})^{10^5} = (1 - 1 / 2^{29})^{2^{29} \cdot (10^5/2^{29})} = (1/e)^{10^5/2^{29}}$$$ — то есть это $$$1 / e$$$ в какой-то очень маленькой степени (порядка $$$10^{-4}$$$), значит это число, близкое к единице.

Допустим, ответ есть, тогда как будет выглядеть последняя операция? Она будет выглядеть так: мы берем рядом стоящие числа $$$1$$$ и $$$n$$$ и разносим их по сторонам. Это намекает на то, что это особые числа.

В задачах на констуктив очень часто помогает придумать какой-то инвариант (то есть какое-то свойство, которое будет сохранятся после каждой операции). Мы хотим отсортировать перестановку с помощью алгоритма, похожего на сортировку вставками. Какой инвариант можно придумать?

Можно например брать числа $$$n-1,n-2,\ldots,2$$$ (пока не будем трогать $$$1$$$ и $$$n$$$) и вставлять их в начало. Тогда инвариант будет такой: Каждый раз перестановка будет выглядеть так: $$$(k, k+1,\ldots,n-1) \ldots$$$ — то есть префикс отсортирован и там лежат числа от $$$k$$$ до $$$n - 1$$$, а в суффиксе будет "мусор". Теперь мы хотим положить в начало число $$$k - 1$$$. В каком простом случае мы можем это сделать?

Если $$$k - 1$$$ лежит в позиции $$$i \lt n$$$, тогда мы можем применить операцию $$$op(i)$$$, тогда $$$k - 1$$$ переместиться в начало, а его сосед справа в конец, тогда префикс будет отсортирован, там будут числа от $$$(k - 1)$$$ до $$$(n - 1)$$$, а в суффиксе будет мусор. Что делать, если $$$i = n$$$?

Здесь нужно попробовать поделать какие-то операции, в итоге можно прийти к такому. Мы хотим перекинуть $$$k-1$$$ в начало, для этого надо положить что-нибудь справа от него. Если $$$k \gt 2$$$, тогда слева от $$$(k - 1)$$$ есть как минимум еще два числа (мы же не трогали $$$1$$$ и $$$n$$$), пусть это числа $$$x,y$$$, тогда мы можем их разнести — один влево, один вправо, теперь наш массив выглядит так:

$$$x (k \ldots (n-1)) \ldots (k-1) y$$$

Теперь что делаем?

Теперь можем перекинуть $$$(k-1)$$$ в начало, сделав операцию $$$op(n-1)$$$, теперь массив выглядит так:

$$$ (k - 1) x (k \ldots (n-1)) \ldots y$$$

Нам мешается $$$x$$$ между $$$(k - 1)$$$ и $$$k$$$. Что можно сделать?

Можно его просто перекинуть в конец, сделав операцию $$$op(1)$$$. Тогда массив будет выглядеть так:

$$$ ((k - 1) \ldots (n-1)) \ldots y x$$$

Что будет в конце? И сколько операций мы потратили?

В конце возможны два варианта:

1. $$$(2\ldots (n-1)),1,n$$$ — легко решается одной операцией $$$op(n-1)$$$

2. $$$(2\ldots n),1$$$ — тут нужно уже думать.

Мы уже потратили $$$3n$$$ операций (по три операции на одну вставку числа $$$k-1$$$ в начало с сохранением инваранта)

Значит у нас осталось еще $$$n$$$ операций, чтобы разобраться со вторым случаем.

Если порешать в случае $$$n = 4$$$, то можно заметить, что массив $$$(2,3,4,1)$$$ не получается отсортировать. Почему?

Если $$$n$$$ четное, то одна операция $$$op(i)$$$ по сути делает $$$(i - 1)$$$ обменов слева и $$$n - (i + 1) = n - i - 1$$$ обменов справа, значит суммарно $$$n - 2$$$ операции обмена, а значит знак перестановки не меняется. Хорошо, какой знач перестановки у $$$(2,\ldots,n),1$$$ при четном $$$n$$$?

Шаг перестановки равен $$$(-1)^x$$$, где $$$x$$$ — количество инверсий, здесь их $$$(n-1)$$$ штук, то есть нечетное число, а так как одна операция не меняет знак перестановки, значит знак всегда будет равен $$$-1$$$, а знак у отсортированной перестановки равен $$$+1$$$, значит ответа нет. А как решать для нечетных $$$n$$$?

Мы хотим сделать так, чтоб в итоге массив перед последней операций выглядит например так $$$2,3,\ldots,(n-1),1,n$$$.

Как это сделать? Нам нужно справа то единицы положить $$$n$$$, как это можно сделать?

Например с помощью операции $$$op(n-2)$$$, тогда массив будет выглядеть так:

$$$(n-1),2,3,4,\ldots,(n-2),1,n$$$.

Но здесь $$$(n-1)$$$ лежит в начале, нужно исправить. Попробуем опять применить эту операцию.

Получим

$$$(n-2),(n-1),2,3,4,\ldots,n,1$$$.

Опять единица в самом конце, но мы смогли сделать $$$(n-2)$$$ в самом начале после двух операций. Если сделать еще две операции будет массив

$$$(n-4),(n-3),(n-2),(n-1),2,3,4,\ldots,n,1$$$.

То есть по сути мы циклически сдигваем префикс.

А если сделать $$$n-3$$$ операции суммарно, то будет

$$$(n-4),(n-3),(n-2),(n-1),\ldots,2,n,1$$$.

Тогда что будет, если эту операцию сделать еще раз?

Тогда получим массив

$$$2,3,\ldots,(n-1),\ldots,1, n$$$.

Осталось один раз применить $$$op(n-1)$$$. В итоге потратили еще не более $$$n$$$ операций, значит суммарно не более $$$4n$$$ операций.

Что написано в условии? Сказано, что мы можем взять левую башню и обрезать правую башню высотой первой, приечм мы можем это делать только с самой ближайшей справа башней, которая больше левой. А можно ли любую башню справа обрезать, а не только самую ближайшую.

Можно. Мы можем много раз подряд выбирать башню $$$i$$$, тогда с ее помощью можно обрезать все башни правее нее. Тогда какую минимальную высоту можно получить в башне $$$i$$$?

В башне $$$i$$$ мы можем получить высоту $$$\min(a_1,a_2,\ldots,a_i)$$$, но никак не меньше. Тогда чему равен ответ?

Пусть $$$A_i$$$ — префиксный минимум, тогда ответ $$$\sum_i A_i$$$

Что происходит в задаче? Мы сначала перемешиваем массив $$$b$$$, а потом пытаемся превратить его в $$$a$$$ с помощью добавления неотрицательных чисел. Тогда какой критерий можно сформулировать для массива $$$b$$$ после перемешивание, что его можно превратить в $$$a$$$?

Массив $$$b$$$ можно превратить в $$$a$$$ тогда и только тогда, когда $$$b_i \le a_i$$$ для всех $$$i$$$. Тогда посмотрим на исходный массив $$$b$$$, посмотрим на какой-то элемент $$$b_i$$$, на каких позициях он может стоят в финальном ответе?

Найдем для него минимальный $$$j$$$, что $$$b_i \le a_j$$$, тогда мы можем положить $$$b_i$$$ в любую позицию, начиная с $$$j$$$, то есть $$$(j,j+1,\ldots)$$$. Тогда какую простую стратегию можем придумать?

Можем идти слева направо и если встретили $$$b_i \gt a_i$$$, тогда для него можем найти миниальную позицию $$$j$$$, что $$$b_i \le a_j$$$ и подвинуть этот элемент туда. Ограничения позволяют решить задачу за $$$O(n^2)$$$. Почему это работает?

Во-первых, мы обязаны подвинуть элемент $$$b_i$$$ хотя бы в $$$j$$$, но с другой стороны не имеет смысл сейчас его двигать дальше, потому что мы сможем это сделать на следующих шагах, если потребуется.

В большинстве задач, можно попробовать решать их, идя слева направо, то есть попытаться решить задачу для префикса $$$a_1,a_2,\ldots,a_i$$$. В этой задаче стоит сделать именно так, потому что в итоге мы хотим получить отсортированный массив, значит максимум будут всегда справа. Как это сделать?

Пускай мы решили задачу для префикса $$$a_1,\ldots,a_{i-1}$$$. Мы хотим добавить $$$a_i$$$. Какие бывают случаи?

Если $$$a_{i-1} \le a_i$$$, то префикс уже отсортирован, а если $$$a_i \lt a_{i-1}$$$?

Тогда мы обязаны свапать $$$a_i$$$ с предыдущим элементом пока префикс не отсортирован. Что тогда будет происходить?

Тогда сам элемент $$$a_i$$$ не поменяется, но подвинется куда-то влево, а те элементы, с которыми мы поменяемся местами увеличиться на $$$a_i$$$. Отлично, научились решать задачу за $$$O(n^2)$$$, но можно ли быстрее? Нужно ли нам знать весь префикс?

Так как в итоге нам нужно узнать только последний элемент, то можем помнить только его, тогда если $$$a_{i-1} \le a_i$$$, то новый макс. элемент равен $$$a_i$$$, а иначе $$$a_{i-1}+a_i \ge a_{i-1}$$$.

Какое самое простое условие должно выполняться, чтобы строка была красивой? В каких случаях мы точно не сможем сделать ни одной операции?

Строка точно не является красивой, если она содержит хотя бы два элемента, причем все элементы чередуются (например $$$01010101$$$), то есть нет одинаковых соседей.

Задача похожа на часто-встречающуюся задачу, когда два соседних элемента заменяют на их сумму. В такой задаче сумма массива никогда не меняется. Можно ли сделать в этой задаче что-то похожее?

Пусть $$$a$$$ — это число, на которое мы заменим нули, а $$$b$$$ — число, на которое мы заменим единицы. Тогда мы хотим, чтобы $$$a + a = b, b + b = a$$$, то есть $$$2a=b,2b=a$$$. Что тогда?

Тогда $$$a = 2\cdot b = 2\cdot (2\cdot a) = 4a$$$, то есть $$$3a = 0$$$. На что похоже?

Это похоже на арифметику по модулю $$$3$$$. Возьмем $$$a \equiv +1\pmod{3}, b \equiv -1 \pmod{3}$$$

Тогда какой второй критерий мы хотим?

Так как теперь при выполнении операции сумма элементов по модулю 3 не меняется, то в итоге мы хоим получить либо $$$a$$$, либо $$$b$$$, то есть хотим, чтобы сумма элементов не была равна нулю по модулю 3. Попробуем проверить, достаточно ли этих двух критериев.

Пусть у нас есть строка $$$s_1s_2\ldots s_n, n \ge 2$$$, приечм $$$\sum s_i \not\equiv 0\pmod{3}$$$. И еще есть два равных соседа $$$s_i = s_{i+1}$$$, тогда если мы применим к ним операцию, то сумма опять не будет равна нулю, осталось проверить, что в случае $$$n \ge 3$$$ у нас опять будут одинаковые соседи. Рассмотрим самую левую пару одинаковых элементов. Если $$$i \gt 1$$$, то у нас слева стоит $$$-s_{i-1}$$$, а два элемента $$$s_i,s_{i+1}$$$ заменятся на $$$-s_i$$$, тогда получили двух одинаковых соседей. А если $$$i=1$$$, тогда эта пара лежит в первом блоке одинаковых элементов. Тогда правее этого блока либо есть следующий блок из противоложных элементов, либо блока нет. Если блок есть, тогда мы можем самую правую пару соседей из первого блока, тогда новый элемент будет равен первому элементу следующего блока. А если у нас блок всего один?

Тогда $$$n \ge 4$$$, потому что мы рассматриваем случай $$$n \ge 3$$$, то $$$n$$$ не равно $$$3$$$, так как иначе сумма будет равна нулю. Тогда после применений операции в блоке будет $$$n - 2 \ge 2$$$ элемента, значит будет хотя бы одна пара одинаковых соседей.

Можем ли мы восстановить однозначно некоторые элементы $$$b_i$$$?

Рассмотрим $$$i$$$, что $$$b_i \neq -1$$$, тогда мы знаем, что $$$a[b_i] = b[a_i]$$$, тогда мы точно знаем, чему равен элемент в $$$a_i$$$, и наоборот, если мы знаем значение $$$b$$$ в индексе $$$a_i$$$, то знаем и в индексе $$$i$$$. Как тогда можно посмотреть на перестановку?

Очень часто помогает посмотреть на перестановку в виде набора циклов, То есть например берем $$$1 \rightarrow a[1] \rightarrow a[a[1]], \ldots$$$. Что тогда следует из предыдущего шага?

Получается, что если на цикле у какого-то элемента мы знаем значение $$$b$$$, то во всех остальных иднексах, лежащих в этом же цикле мы тоже можем однозначно восстановить значения. Что будет после восстановления

После восстановления у нас будет набор незаполненных циклов. То есть мы знаем, какие индексы мы хотим заполнить. А какими числами мы можем это сделать?

Мы можем заполнить их еще неиспользованными числами из $$$b$$$. Тогда как получить ответ?

Так как мы хотим получить лексикографически минимальную перестановку, то выгоднее всего в минимальный индекс класть минимальное число. Так и сделаем, а именно будем брать каждый раз мнимальный индекс без числа, брать минимальное неиспользованное число и заполнять цикл, в котором лежит этот индекс. В процессе обязательно проверяем, что мы не используем уже использованное число.

Переформулируем задачу. Мы хотим выбрать максимальный набор индексов $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$$$, что мы можем раскрасить элементы массива $$$a$$$ на позициях $$$i_j$$$ без возникновения каких-либо противоречий.

Как раскрасить элемент $$$a_i$$$? Каким отрезком?

Мы можем раскрасить этот элемент только отрезком $$$[i - a_i + 1, i + m - a_i]$$$, обозначим его за $$$[L_i,R_i]$$$. Какие тогда самые простые противоречия могут быть?

Если есть $$$i_j$$$, что $$$L_{i_j} \lt 1$$$ или $$$R_{i_j} \gt n$$$, тогда точно не может раскрасить эти элементы. Хорошо, а в каком порядке красить элементы? Какие могут быть проблемы?

Когда мы красим какой-то отрезок $$$[L_i, R_i]$$$, то мы также закрашиваем и элемента на всем этом отрезке, то есть все $$$j$$$, что $$$L_i \le j \le R_i$$$, тогда если $$$L_j \neq L_i$$$, то мы затрем элемент $$$j$$$, значит нам надо будет его опять красить. О чем это говорит, в каком порядке нужно красить элементы $$$a_i, a_j$$$?

Если отрезок $$$[L_i,R_i]$$$ покрывает $$$j$$$, причем $$$L_i \neq L_j$$$, то мы обязаны красить элемент $$$j$$$ после $$$i$$$. А если окажется так, чтобы $$$[L_j,R_j]$$$ изменит $$$i$$$?

Тогда мы не сможем покрасить одновременно два элемента $$$i,j$$$. Хорошо, а что если теперь нет таких плохих пар, в каком порядке красить элементы?

Если отрезок $$$[L_i,R_i]$$$ покрывает $$$j$$$ проведем ребро из $$$i$$$ в $$$j$$$, раз у нас нет плохих пар, то в таком графе не будет циклов, т.к. все отрезки имеют одинаковую длину, значит если был цикл, то была и пара плохих элементов. Тогда этот граф можно топологически отсортировать и получить порядок, в котором нужно красить элементы.

Нужно ли нам проверять все пары индексов из множества?

Т.к. длины всех отрезков одинаковы (аналогично рассуждениям из предыдущего шага), то достаточно проверить только соседей. Тогда как решать задачу?

Мы хотим найти максимальную подпоследовательность $$$i_1 \lt i_2 \lt \ldots$$$, что никакие два соседа не являются плохими. Будем решать с помощью динамического программирования. Заведем $$$dp_i$$$ — максимальная поледовательность, которая заканчивается в $$$i$$$. База $$$dp_i=1$$$, если $$$1 \le L_i \le R_i \le n$$$. Ответ: $$$\max(dp_i)$$$. Как сделать переход?

Зафиксируем $$$i$$$, мы хотим найти $$$j \lt i$$$, что либо $$$L_j = L_i$$$, либо $$$R_j \lt i$$$, либо $$$j \lt L_i$$$. Тогда по всем таким $$$j$$$ нужно обновить $$$dp_i$$$ значением $$$\max(dp_i, dp_j+1)$$$. Первый случай легко обрабатывается: просто для каждого $$$L_i$$$ поддерживаем максимальное $$$dp_i$$$, а два последних случая обрабатываются с помощью Дерева Фенвика или Дерева Отрезков.

В этой задаче если бы можно было задавать запросы $$$i = j$$$, то можно было бы просто сделать $$$b = a$$$. Но здесь это сделать не получится. Рассмотрим какой-нибудь сложный предельный случай. Какой?

Если все числа — это разные простые числа в некоторых степенях? То есть $$$a = (p_1^{\alpha_1}, p_2^{\alpha_2},\ldots)$$$?

Тогда нам нужно как-то закодировать весь массив, причем никакие два элемента исходного массива не содержат информации друг о друге. Значит нам нужно какое-то дополнительное знание. Какое?

Например, можно взять первые 150 простых чисел в максимальных степенях, что эта степень не больше $$$10^6$$$. Тогда как мы могли бы восстановить массив, если бы все $$$p_i$$$ были бы среди этих 150 простых?

Мы могли для каждого $$$i$$$ взять $$$gcd(a_i, p_j)$$$ для всех простых и перемножить. Но что если у некоторых $$$a_i$$$ есть простые в разложении, которые не встречаются среди первых 150 простых чисел?

Если посчитать количество хороших чисел, которые можно восстановить, то их больше $$$3\cdot 10^5$$$, а это число больше $$$2^{18}$$$, но наши числа могут быть больше $$$2^{18}$$$, но не больше чего?

Все числа не больше $$$2^{20}$$$. На что похожи числа $$$18,20,9,10$$$?

На то, что $$$\frac{10}{9}=\frac{20}{18}$$$, тогда что мы можем сделать?

Мы можем выписать все числа массива в ряд из $$$20n$$$ бит, а дальше перегруппировать эти биты в блоки по 18 бит, получив массив из $$$\lceil\frac{20n}{18}\rceil = \lceil\frac{10n}{9}\rceil$$$ чисел, каждое из которых не больше $$$2^{18}$$$. А что дальше?

Тогда каждое число — это по сути индекс хорошего элемента. Тогда как решать всю задачу.

При кодировании мы переразбиваем массив, превращая его в массив индексов, дальше заменяем каждый индекс на соответсвтующее хорошее число и в конец добавляем еще 150 простых в максимально возможных степенях.

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

Судя по всему, нужно аккуратно расписать формулы в соответствии с условием задачи. Предположим, что мы знаем, что ответ равен $$$T$$$. Какие на него есть условия, когда Никита не использует ИИ? Сколько строк кода напишут ребята?

Они напишут $$$T\cdot (x + y)$$$ строк кода и мы хотим, чтобы выполялось $$$T\cdot (x + y) \ge n$$$, тогда $$$T \ge \frac{n}{x+y}$$$. А что если они будут использовать ИИ?

Тогда они напишут $$$T\cdot x + (T-z)\cdot 10\cdot y$$$ строк. Какое тогда есть ограничение на $$$T$$$?

$$$T\cdot x + (T-z)\cdot 10\cdot y \ge n$$$, тогда $$$T\cdot(x+10y) \ge n + 10zy$$$, тогда $$$T \ge \frac{n + 10zy}{x+10y}$$$.

Выбираем максимум из двух выражений и округляем вверх.

Какой самый простой случай можно рассмотреть?

Когда $$$n=2$$$. Как его решить?

Обозначим два числа за $$$X,Y$$$, тогда можно взять например такой ответ: "XYYXXYXY", тогда для $$$X$$$ расстояния образуют множество $$$(3,1,2)$$$, а у $$$Y$$$ множество $$$(1,3,2)$$$. Как теперь решить для случая $$$n=3$$$?

Можно например взять ответ из прмеров или например такую строку: "XYZXXZXYYZZY". Как теперь решить задачу для четных $$$n$$$?

Можно разбить числа на пары $$$(1,2),(3,4),\ldots,(n-1,n)$$$, для каждой пары мы можем построить блок длины $$$8$$$, останется их только склеить. А как решить задачу для нечетных $$$n$$$?

Если $$$n$$$ нечетное, то $$$n \ge 3$$$, тогда мы можем построить блок для чисел $$$(n-2,n-1,n)$$$ длины $$$12$$$. Нам остается только решить задачу для оставшихся $$$(n-3)$$$ чисел. А это мы уже умеем делать, т.к. $$$(n-3)$$$ — четное число.

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

У нас есть скобки всего двух типов: "(" и ")". Пусть мы удалим $$$x$$$ скобок "(" и $$$y$$$ скобок ")", тогда $$$x+y \le k$$$. Какие скобки типа "(" нам выгоднее всего удалять?

Нам выгоднее всего удалить $$$x$$$ самых левых скобок "(", почему?

Посмторим на оптимальный ответ. В нем мы можем найти ПСП какой-то длины. Посмотрим на первый символ этой ПСП, он равен "(", причем мы можем считать, что это самая первая скобка в строке (если это не так, тогда мы можем заменить первый символ на скобку "(" левее). Т.к. мы предположили, что мы удалили не $$$x$$$ самых левых скобок "(", тогда есть удаленная скобка, которая правее скобки "(" в ПСП, мы можем вместо удаления этой более правой скобки удалить скобку из ПСП, тогда сама ПСП не увеличится.

Хорошо, а какие тогда скобки ")" нам выгоднее всего удалять?

Нам выгоднее всего удалять $$$y$$$ самых правых скобок ")". Как тогда решать задачу? Что можно перебрать?

Мы можем перебрать $$$x$$$ за $$$O(n)$$$, тогда $$$y=k-x$$$. Остается только удалить скобки за $$$O(n)$$$ и посчитать длину максимальной ПСП в оставшейся строке. Как это сделать?

Можно это сделать жадно. Будем идти слева направо и поддерживать текущее количество скобок "(" без парной ")" (пусть это число равно $$$b$$$), а также количество уже спаренных скобок (это и есть длина ПСП). Если текущий символ "(", что тогда можем сделать?

Можем увеличить $$$b$$$ на единицу, а если текущий символ — это ")"?

Тогда мы можем попытаться спарить эту скобку с какой-то из "(". То есть, если $$$b \gt 0$$$, то мы можем уменьшить $$$b$$$ на единицу и увеличить ответ на $$$2$$$.

Первое, на что обратил внимание, что мы можем сжать координаты и считать, что $$$0 \le a_i \lt n$$$. Тогда для каждого $$$0 \le x \lt n$$$ мы можем выписать все позиции $$$i$$$, что $$$a_i=x$$$.

Как нам для конкретного $$$x$$$ проверить, что все числа в массиве $$$a_i=x$$$ образуют один отрезок?

Пусть $$$l$$$ — минимальная позиция $$$a_l=x$$$, а $$$r$$$ — максимльная, пусть $$$c$$$ — количество элементов в массиве, равных $$$x$$$. Как проверить условие?

Достаточно проверить, что $$$r - l + 1 = c$$$. Хорошо, теперь какой бывает простой случай?

Пусть $$$F(x) = 1$$$, если $$$x$$$ образует единый отрезок и $$$0$$$ иначе. Тогда простой случай, когда $$$F(x)=1$$$ для всех $$$x$$$. Хорошо, осталося случай, когда есть какой-то $$$y$$$, что $$$F(y)=0$$$. Что тогда? Какую позицию тогда точно нужно будет поменять?

Тогда мы знаем, что $$$r-l+1 \gt c$$$ и есть "дырки", то есть позиции, в которых стоят какие-то другие числа. В таком случае мы будем обязаны обменять местами либо $$$l$$$, либо $$$r$$$ с кем-то другим, т.к. иначе величина $$$r-l+1$$$ может только увеличиться, а $$$c$$$ не изменится. Тогда сколько всего можно перебрать пар для обмена местами?

Мы можем перебрать пары $$$(l,i),(r,i)$$$ для всех $$$i$$$, то есть всего есть $$$O(n)$$$ пар. Как нам для конкретной пары проверить, помогает ли она или нет?

Мы можем поддерживать множество позиций в std::set<int>, тогда операцию swap и проверку конкретного $$$x$$$ можно еализовать за $$$O(\log{n})$$$. Как тогда решить задачу?

Давайте поддерживать количество $$$x$$$, что $$$F(x)=0$$$ Давайте переберем все пары для swap , сделаем этот swap и обновим количество плохих $$$x$$$-ов. Если помогло, то выводим ответ, а иначе меняем обратно, возвращая все на место и идем дальше.

Зафиксирую конкетную перестановку бит из условия. Какие простые условия можно проверить?

Мы хотим, чтобы не было нуля, а также чтобы все числа были разные. Тогда какое единственное условие может быть нарушено?

Скажем, что перестановка бит хорошая, если максимальный элемент после перестановки бит не больше $$$n$$$. Тогда чему равен ответ?

Он равен количеству хороших перестановок, потому что разные перестановки бит дают разные перестановки массива $$$p$$$. Можем ли мы перебрать все перестановки бит $$$a_0,a_1,\ldots,a_{k-1}$$$?

Да, можем, потому что $$$\log_2(n) \le 11$$$, а $$$11! \le 4\cdot 10^7$$$. Что останется сделать?

Останется проверить, что для конкретной перестановки бит все числа будут не больше $$$n$$$. Что значит, что число $$$x$$$ больше числа $$$n$$$?

Это когда мы сравниваем два числа начиная со старших бит и находим первое несовпадение в бите $$$j$$$ и так оказывается, что $$$n_j=0,x_j=1$$$, то есть $$$j$$$-й бит числа $$$n$$$ равен нулю, а у числа $$$x$$$ он равен единице.

Тогда мы можем перебирать биты начиная со старшего, пусть смотрим на бит $$$j$$$, тогда мы хотим проверить, есть ли число $$$x$$$, что в битах $$$a_q$$$ (здесь $$$q \gt j$$$) в нем стоит то же самое, что в бите $$$q$$$ числа $$$n$$$, а в бите $$$a_q$$$ стоит единица, в то время как у $$$n$$$ стоит ноль. Как мы можем это проверить?

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

Как строится последовательность $$$a$$$? В условии написано, что $$$a_{i+2}=a_{i}\mod a_{i+1}$$$ Каким свойством тогда должна обладать последовательность $$$a$$$?

По построению, получается, что $$$a_i \ge a_{i+1}$$$, то есть последовательность должна быть отсортирована по невозрастанию. Как тогда решать всю задачу?

Тогда мы можем отсортировать последовательность $$$b$$$ по невозрастанию и проверить, что $$$b_{i+2}=b_{i}\mod b_{i+1}$$$

Какие самые простые числа являются палиндромами?

Это числа, состоящие из одной цифры. Когда мы можем так сделать? Как мы можем использовать свойство числа $$$b$$$?

Мы знаем, что число $$$b$$$ делится на $$$12$$$, тогда $$$b = (n - a)$$$ тоже делится на $$$12$$$. Тогда что мы знаем про число $$$a$$$?

Мы знаем остаток от деления числа $$$a$$$ на $$$12$$$, он равен остатку от деления числа $$$n$$$ на $$$12$$$, потому что $$$n-a\equiv\pmod{12}$$$, значит $$$n\equiv a\pmod{12}$$$. Пусть $$$r$$$ — остаток от деления. Тогда какие числа мы можем использовать в качестве числа $$$a$$$?

$$$a \in {r, r + 12, r + 24, r + 36, \ldots, r + 12\cdot i, \ldots}$$$. Что если $$$r \lt 10$$$?

Тогда мы можем взять $$$a = r$$$, потому что число $$$a$$$ в таком случае будет состоять из одной цифры. А что если $$$r \in {10, 11}$$$?

Если $$$r = 11$$$, то опять можем взять $$$a = r = 11$$$, потому что $$$11$$$ уже палиндром. Остался случай $$$r = 10$$$. Что делать с ним?

Если $$$r = 10$$$, тогда $$$a \in {10, 22, 34, 46, \ldots}$$$. Какое $$$a$$$ можем взять?

Можем взять $$$a = 22$$$. На самом деле, теперь мы видим, что если ответ есть, то можем выбрать $$$a \le 22$$$, тогда можем просто перебрать $$$a$$$ и проверить, что $$$(n - a)\equiv 0\pmod{12}$$$ и $$$a$$$ палиндром.

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

Давайте разберем случай, когда $$$i=1$$$, тогда остальные можно решить аналогично. Итак, мы хотим, чтобы $$$w_1=0$$$, а также чтобы выполнялись условия сообщающихся сосудов. Сейчас в задаче циклическое условие, какую более простую задачу можно решить?

Можно попробовать решить задачу, где наше условие не цикличное. Как это сделать?

Как выбрать $$$w_2$$$?

Можно взять $$$w_2=h_2$$$, но тогда возможно сломается условие для $$$h_2$$$. Как выбрать $$$w_3$$$?

Можем взять $$$w_3 = \max(w_2,h_2)$$$, тогда что будет если $$$w_2 \gt h_2$$$?

Тогда $$$w_3 = w_2$$$ и условие сохранилось, тогда как выбрать $$$w_{i+1}$$$, если мы знаем $$$w_i$$$?

Можем взять $$$w_{i+1}=\max(w_i, h_i)$$$. То есть по сути мы строим массив префиксных максимумов массива $$$h$$$. Что в таком случае у нас ломается?

Сломаться может условие на $$$h_n$$$, потому что в исходной задаче мы имеет цикличные условия. То есть может быть так, что $$$w_n$$$ слишком большой, а т.к. $$$w_1=0$$$, то возможно, что $$$w_n \gt h_n$$$ и $$$w_n\neq w_1$$$. Как будет выглядеть наш полученный массив $$$w$$$? На какой элемент в массиве $$$h$$$ можно обратить внимание?

На максимальный элемент, пусть он расположен в $$$h_q$$$. После $$$q$$$-го элемента все элементы будут равны. Какой аналогичный простой шаг мы можем сделать?

Мы можем построить массив суффиксных максимумов, тогда возможно сломается условие на $$$h_1$$$ из-за того, что $$$w_2$$$ будет слишком большим. Как мы можем тогда решить задачу?

В качестве финального $$$w$$$ мы можем взять минимум из двух ответов — префиксного максимума и суффиксного максимума.

Попробую проэмулировать несколько первых шагов. Изначально нам известны числа на позициях $$${1, 2^k+1}$$$, после первого шага нам будут известны числа на позициях $$${1, 2^{k-1}+1, 2^k+1}$$$. Что будет еще на следующем шаге?

Нам будут известны числа на позициях $$${1, 2^{k-2}+1,2^{k-1}+1,2^{k-2}+2^{k-1}+1}$$$. Чем равно расстояние между соседними индексами?

До шагов расстояние равно $$$2^k+1-1=2^k$$$, на первом шаге расстояние равно $$$2^{k-1}+1-1=2^k+1-(2^{k-1}+1)=2^{k-1}$$$. Какое будет расстояние между индексами на следующем шаге?

Оно будет равно $$$2^{k-2}$$$ и так далее. Мы хотим посчитать $$$\sum_i x_i\cdot y_i$$$, как можно вычислить $$$y_i$$$, зная только $$$x_i$$$?

Можно вычислить так: $$$y_i = n - x_i$$$, тогда вся сумма будет равна $$$n\sum_i x_i - \left(\sum_i x_i^2\right)$$$. Как вычислить $$$\sum_i x_i$$$? Какой физический смысл у этой суммы?

Эта сумма считает общее количество бит по всем элементам массив, можно ли это как-то перефразировать?

Пусть $$$F(j)$$$ — количество элементов в массиве $$$a$$$, у которых $$$j$$$-й бит равен единице? Тогда чему равна вся сумма?

Вся сумма равна $$$\sum_j F(j)$$$. Как посчитать $$$F(j)$$$ для конкретного $$$j$$$? От чего зависит эта величина?

Эта величина зависит от того, что находится в $$$j$$$-м бите у чисел $$$a_1, a_{2^k+1}$$$. И размера массива.

Такую величину можно посчитать с помощью динамического программирования $$$F_{l, x, y}$$$ -- количество ежиниц в массиве $$$a$$$, если этот массив будет состоять из $$$2^l+1$$$ элементов, а первый и последний элемент будут равны $$$x$$$ и $$$y$$$ соответственно. Какая База динамики?

База динамики такая: $$$F_{0,x,y}=x+y$$$. А где будет лежать ответ?

Пусть $$$cnt_{x,y}$$$ — количество бит, что в $$$a_1$$$ лежит бит $$$x$$$, а в $$$a_{2^k+1}$$$ лежит бит $$$y$$$. Тогда $$$\sum_i x_i = \sum_{x=0}^{1}\sum_{y=0}^{1}cnt_{x,y}\cdot F_{k,x,y}$$$. Осталось только посчитать переход динамики.

Допустим, мы знаем ответ для слоя $$$l$$$, то есть знаем значения $$$F_{l,x,y}$$$ для любых $$$x,y$$$. Как посчитать $$$F_{l+1,x,y}$$$? Мы знаем, что мы должны рассмотреть середину и положить туда число $$$z=x\oplus y$$$

Тогда $$$F_{l+1,x,y}=F_{l,x,z}+F_{l,z,y}-z$$$, потому что мы поделим массив на две части и два раз посчитаем $$$z$$$, поэтому его нужно один раз вычесть из ответа.

Хорошо, как теперь посчитать $$$\sum_i x_i^2$$$? Какой физический смысл этой величины?

Физический смысл этой величины такой: по сути мы перебираем все пары бит $$$p,q$$$ и добавляем единицу, если в $$$p$$$-м бите и в $$$q$$$-м бите стоят единицы. Как тогда это посчитать?

Опять с помощью динамики $$$G_{l,x,y,z,w}$$$ — это количество элементов финального массива (причем все элементы состоят из двух бит), что в этих элементах в обоих битах стоят единицы. Причем первый элемент содержит биты $$${x,y}$$$, а последний элемент содержит биты $$${z,w}$$$. Какая база динамики?

База динамики: $$$G_{0,x,y,z,w}=xy+zw$$$. А как посчитать ответ?

Ответ можно посчитать так: $$$\sum_i x_i^2 = \sum_{x=0}^{1}\sum_{y=0}^{1}\sum_{z=0}^{1}\sum_{w=0}^{1}cnt_{x,z}\cdot cnt_{y,w}\cdot G_{k,x,y,z,w}$$$. Осталось только разобраться с переходом.

Мы хотим найти $$$G_{l+1}$$$ по $$$G_l$$$. Оять мы выделяем середину, в которой будут лежать биты $$${u=x\oplus z, v=y\oplus w}$$$. Тогда $$$G_{l+1,x,y,z,w}=G_{l,x,y,u,v}+G_{l,u,v,z,w}-u\cdot v$$$.

Итак, мы знаем, что $$$a_i$$$ — количество отрезков, в которых $$$p_i$$$ является минимумом. Представим, что мы смотрим на какую-то перестановку, на какой элемент можно обратить внимание?

На минимальный элемент, пусть он находится в позиции $$$i$$$, тогда сколько отрезков его покрывает?

Его покрывает $$$i\cdot (n-i+1)$$$ (в 1-индексации). Как нам найти позицию, где лежит минимумум? А что если их несколько?

Все позиции, где $$$a_i=i\cdot(n-i+1)$$$ потенциальные позиции для минимума. Если таких нет, то ответ 0, а если их несколько? Тогда ответ тоже 0, потому что в перестановке только один минимум. Хорошо, тогда пусть мы смогли найти позицию минимума $$$i$$$. Тогда левее этого элемента находится $$$c_l=i-1$$$ элементов, а правее $$$c_r=n-i$$$. Зависят ли элементы из левой части от элементов из правой части?

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

Всего есть $$$\binom{c_l+c_r}{c_l}$$$ способов. Если количество перестановок в левой части равно $$$L$$$, а в правой часте равно $$$R$$$, тогда чему равен итоговый ответ?

Он равен $$$\binom{c_l+c_r}{c_l}\cdot L\cdot R$$$. Осталось только понять, как находить минимальный иднекс $$$i$$$? Что будет если мы каждый раз будем находить его ближе к конце массива, какое время работы будет в худшем случае?

Оно будет равно $$$n+(n-1)+(n-2)+\ldots + 1=O(n^2)$$$. А если мы будм находить его всегда в $$$i \le n / 2$$$.

Тогда время работы можно оценить так $$$T(n)=T(c_l)+T(c_r)+\min(c_l,c_r) \le 2T(n/2)+O(n)=O(n\log{n})$$$. Это называется мастер-теорема

Из задачи $$$C$$$ мы знаем, что для каждого $$$i$$$ мы ищем префиксные и суффиксные максимумы и считаем сумму минимумов из двух ответов. Чтобы удобнее было работать, давайте удвоим массив $$$h$$$, то есть увеличим его в два раза и сделаем $$$h_{i+n}=h_i$$$. Тогда при работе с ответов для $$$i$$$-го индекса нам нужно будет решать задачу для подотрезка $$$[i, i + n)$$$. В каком месте префиксные максимумы перестают меняться?

Префиксные максимумы, как и суффиксные перестают меняться в максимамльном элементе $$$h_q$$$. Как его быстро найти для всех подотрезков $$$[i, i + n)$$$?

Пусть $$$h_z$$$ — первый максимум во всем массиве $$$h$$$, тогда $$$q = z$$$ или $$$q = z + n$$$. Тогда по сути нам нужно стартонуть с элемента $$$i$$$ и идти до элемента $$$q$$$, поддерживая максимум и считая сумму этих максимумов. Аналогично, нам нужно стартонуть с элемента $$$i + n - 1$$$ и идти до $$$q$$$, поддерживая максимум. Тогда нам нужно научиться для массива $$$h$$$ и индекса $$$q$$$ считать массив $$$R_j,j \ge q$$$ — сумма максимумов, если мы начнем с $$$j$$$-го элемента и будем идти до элемента $$$q$$$. Как можно это сделать?

Для начала можно сделать $$$R_j=R_{j-1}+h_j$$$, но тогда мы упустим ответ, если $$$h_j \gt h_{j-1}$$$. На какой элемент слева от $$$j$$$ нам нужно смотреть?

Нам нужно найти ближайший слева элемент $$$v \lt j$$$, что $$$h_v \ge h_j$$$, тогда чему будет равен $$$R_j$$$?

Он будет равен $$$R_j=R_{v}+(j-v)\cdot h_j$$$. Как найти $$$v$$$?

С помощью стека, будем идти слева направо и поддерживать некоторое множество индексов. Пусть мы рассматриваем индекс $$$j$$$, тогда нам нужно снять с вершины стека все индекс, значения в которых меньше $$$h_j$$$, тогда после этого на вершине стека будет как раз ближайший слева элемент $$$h_v \ge h_j$$$.

Первое, на что я обратил внимание, что финальная позиция — это одна из позиций в исходном массиве. Почему? Потому, что если это не так, и финальная позиция оказалась в точке $$$x$$$, тогда мы можем ее подвинуть в ближайшую точку в массиве $$$a_i$$$.

Следующее, на что я обратил внимание -- это ограничения задачи, они позволяют перебрать точку $$$x=a_j$$$ и посчитать для нее ответ.

Как посчитать ответ. Два человека идут к точке между ними, значит нам нужно разделить всех людей на три группы, какие?

1. $$$a_i=x$$$, пусть их $$$M$$$
2. $$$a_i \lt x$$$, пусть их $$$L$$$
3. $$$a_i \gt x$$$, пусть их $$$R$$$ Тогда как посчитать ответ?

Нам не нужно учитывать людей из первой группы, т.к. они уже стоят в финальной точке. Как подвинуть остальных людей? Каким парам людей не имеет смысла звонить?

Тем парам людей, которые находятся в одной группе. Еще если мы позвоним людям из разных групп, то мы всегда можем назначить точку $$$x$$$. Тогда чему равен ответ?

Ответ равен $$$\max(L, R)$$$

Пусть мы знаем ответ $$$h$$$ для префикса $$$0\ldots i$$$. Как нам проверить, правильный ли он или нет? Какие есть условия?

Самое простое условие -- это $$$a_0 \ge h$$$, тогда мы можем к себе в запас положить $$$a_0-h$$$ лишней глазури. Какое будет условие для $$$a_1$$$?

Условие такое: $$$a_1 + (a_0-h) \ge h$$$. Так как мы можем сложить глазурь $$$a_1$$$ и остатки глазури с прошлого шага $$$a_0-h$$$. Перепишем это условие: (a_0+a_1) \ge 2h. Тогда у нас останется $$$(a_0+a_1)-2h$$$ лишней глазури. Тогда какое условие в общем виде для префикса $$$i$$$?

Такое: $$$a_0+a_1+\ldots+a_i\ge (i+1)h$$$. Тогда получается, что $$$h \le \frac{A_i}{i+1}$$$, где $$$A_i$$$ — префиксная сумма массива $$$a: A_i=A_{i-1}+a_i$$$.

Первое, на что я обратил внимание -- это ограничения задачи, которые позволяют ее решать за, например, $$$O(n^2)$$$. То есть мы можем что-то перебрать, а потом при фиксированном чем-то можем сделать еще что-нибудь за $$$O(n)$$$. Какую простую версию задачи можно решить?

Представим, что у нас нет людей типа A, тогда есть только I и E. Тогда как решить такую подзадачу?

Чтобы решить эту подзадачу, мы должны просто идти слева направо по строке. Если встретили I, то сажаем его за новый столик (если столики остались), а если E — то сажаем его за неполный столик с хотя бы одним человек (если такой есть). Хорошо, теперь вернем A. По сути, A — это либо I, либо E. Пусть мы знаем, сколько из A людей перекрасятся в I, тогда как нам выгодно их красить?

Нам выгодно перекрашивать некоторый префикс людей типа A в тип I, потому что мы хотим, чтобы на момент рассмотрения I было как можно больше свободных столов, а на момент рассмотрения E, было как можно больше непустых столов. Тогда как решать всю задачу?

Перебираем, сколько людей типа A мы перекрасим в тип I (остальные будут перекрашены в тип E), перекрашиваем, проверяем за линию. Итого $$$O(n^2)$$$.

Попробуем решить жадно. Основная проблема — как работать с A. Пусть мы встретили A. Что мы можем с ним сделать?

Мы можем посадить его за пустой столик, но тогда мы заблокируем место для одного из будущих I. А если посадим его за непустой столик? Тогда мы займем место для какого-то из E. Можем ли мы как-то исправить ситуацию для I? Непонятно. А для E?

Мы можем попытаться пересадить E, который был посажен за непустой столик за новый столик, а затем посадить E. Отлично, тогда давайте хранить количество пустых столов, количество мест за непустыми столами, а также количество A, которые мы посадили за непустые столы (именно их мы можем пересаживать за пустые столы). Если встретили E или I, то решаем как обычно, а если A, то сначала пытаемся посадить его за непустой стол, а если не получилось, то пытаемся посадить за пустой стол.

Первое, на что я обратил внимание, что если все $$$a_i=0$$$, то это задача о Ханойских Башнях. Обычно, в подобных задачах, ее решают так: рекурсивно переносят первые $$$(n-1)$$$ слоев из первого места во второе, затем переносят $$$n$$$-й слой из первого слоя в третий, а потом оставшиеся $$$(n-1)$$$ слоев переносят из второго места в третье. Но здесь бывают случаи, когда $$$a_i \gt 0$$$. Какой есть простой случай, когда ответа нет?

Когда есть $$$a_i \gt i$$$ (в 0-индексации), тогда ответа нет, потому что мы не сможем никогда переместить этот слой никуда, потому что максимальное количество слоев над ним не может быть больше $$$i$$$. Хорошо, осталось рассмотреть случай, когда $$$a_i \le i$$$. Можем ли мы по аналогии с Ханойскими башнями решить задачу?

Пусть $$$k=a_{n-1} \lt n$$$, тогда чтобы переместить последний слой, нам надо сделать так, чтобы над ним было ровно $$$k$$$ слоев. Что мы можем сделать?

Мы можем переместить $$$n-1-k$$$ первых слоев с первого места на второе. После этого на первом месте будет ровно $$$(k+1)$$$ слой, тогда мы можем переместить последний слой из первого места в третье. А что теперь?

Если $$$k=0$$$, то по аналогии с Ханойскими башнями осталось переместить оставшиеся $$$(n-1)$$$ слоев из второго места в третье. А если $$$k \gt 0$$$? В таком случае, у нас есть три места, в каждом из которых есть сколько-то слоев. Причем, во втором месте лежат самые маленькие слои.

Мы можем попытаться переместить либо слои из первого места в третье, либо из второго места в первое. Можем ли мы сделать первый вариант? Не всегда. А второй вариант? Да, можем, тогда в конце нам останется опять переместить $$$(n-1)$$$ слой из первого места в третье. Сколько тогда мы сделаем операций?

Если $$$F(n)$$$ — количество операций при перемещении префикса длины $$$n$$$, тогда $$$F(1)=1$$$, а чему равно $$$F(n)$$$?

$$$F(n) = F(n-1-k) + 1 + F(n-1-k) + F(n-1) = 2F(n-1-k)+F(n-1)+1$$$, причем, если $$$k=0$$$, то $$$F(n)=F(n-1)+1+F(n-1)=2F(n-1)+1$$$. Верно ли, что $$$F(n) \lt 2^n$$$?

Да, верно, потому что $$$F(1)=1 \lt 2^1=2$$$. Далее, если $$$k=0$$$, то $$$F(n)=2F(n-1)+1\le 2\cdot(2^{n-1}-1)+1=2^n-2 \lt 2^n$$$. И если $$$k \gt 0$$$, то $$$F(n)=2F(n-1-k)+F(n-1)+1\le 2\cdot (2^{n-1-k}-1)+2^{n-1}-1+1 \le 2\cdot (2^{n-2}-1)+2^{n-1}=2^n-2 \lt 2^n$$$

Посмотрим на самую длинную змею. Как она выглядит? Где начинается и где заканчивается?

Она начинается в самом верхнем левом углу и заканчивается в самом правом нижнем углу. Если это не так, то ее никак не уместить в поле $$$n\times n$$$.

Дальше, я смотрю на антидиагонали:

01234
12345
23456
34567
45678

Здесь каждой цифрой обозначены диагонали. Сколько раз один путь вправо-вниз может проходить по одной диагонали?

По каждой диагонали не более одного раза. Хорошо, раз мы знаем где начинается и где заканчивается самый длинный путь, то пойдем дальше, а именно рассмотрим диагональ $$$1$$$. Что мы про нее знаем?

Мы знаем, что одна из клеток принадлежит самой длинной змее длины $$$2n-1$$$, а что мы можем сказать про вторую клетку?

Она принадлежит змее длины $$$2n-3$$$, потому что если нет, то мы не сможем расположить эту змею нигде больше. То есть мы нашли старт змеи $$$(2n-3)$$$, а где ее конец?

Ее конец где-то в предпоследней диагонали. Обозначим $$$X$$$ — змея длины $$$2n-1$$$, а $$$Y$$$ — змея длины $$$2n-3$$$, пусть мы знаем, что например картинка выглядит примерно так:

XX....
Y.....
.....?
....?X

Тогда как может выглядеть правый нижний угол?

Он может выглядеть только так:

XX....
Y.....
.....X
....YX

Потому что иначе две змеи пересекутся.

Продолжим процесс. Допустим, мы знаем про каждую клетку диагонали $$$i$$$, каким змеям они принадлежат. Тогда мы знаем, каким змеям принадлежат клетки симметричной диагонали (они там симметричны). Тогда мы по сути хотим итеративно найти стартовые клетки всех змей. Они однозначно зададут все пути. Почему?

Мы все знаем про диагональ $$$i$$$ (в 0-индексации), а именно знаем про каждую из $$$(i+1)$$$ клеток, какой змее они принадлежат. Мы хотим понять это для диагонали $$$(i+1)$$$. Во-первых, мы должны продолжить каждый из $$$(i+1)$$$ путей либо вниз, либо вправо. Причем некоторый префикс путей мы можем продолжить вниз, а оставшийся суффикс — вправо. Тогда останется ровно одна клетка, которую займет новая змея.

Тогда на каждой диагонали мы хотим найти отрезок клеток, где мы можем начать новую змею исходя из уже нарисованных путей. Пусть на диагонали $$$i$$$ отрезок имеет длину $$$L_i$$$, тогда ответ равен $$$L_0\cdot L_1\cdot \ldots \cdot L_{n-1}$$$.

Первое, на что я обратил внимание — на то, что в условии сказано, что мы хотим в итоге сделать так, чтобы все элементы стали равны некоторому числу $$$x$$$, то есть $$$a_1 = a_2 = \ldots = a_n = x$$$. В таких ситуациях мне удобно зафиксировать у себя в голове это число $$$x$$$. Дальше, я должен задать себе вопрос. Каким образом должны выглядеть операции, чтобы в итоге все элементы стали равны $$$x$$$?

Во всех таких операциях я должен выбрать зафиксированный $$$x$$$, потому что сама операция как-бы приближает все числа к этому числу. Хорошо, допустим я знаю $$$x$$$. Хорошо, теперь я смотрю на саму операцию. В условии сказано, что она приближает все $$$a_i$$$ к $$$x$$$, причем все элементы не зависят друг от друга. Тогда через сколько операций число $$$a_i$$$ станет равно $$$x$$$?

Через $$$|a_i - x|$$$ операций. Тогда через сколько операций все элементы станут равны $$$x$$$?

Через $$$\max\limits_{i=1}^{n}|a_i - x|$$$. Хорошо. Дальше, я смотрю на ограничения задачи. Я вижу, что $$$1 \le a_i \le 1000$$$. А еще $$$2 \le n \le 1000$$$. Тогда какие $$$x$$$ мне нужно перебрать?

Мне нужно перебрать $$$1 \le x \le 1000$$$, потому что сами $$$1 \le a_i \le 1000$$$. Тогда все будет работать за $$$1000\cdot n$$$. При заданных ограничениях задачи, такое решение будет работать меньше 1 сек.

Первое, что я делаю — это рисую массив $$$a$$$, а под ним массив $$$b$$$. Я вижу из условия, что мы меняем местами элементы $$$a_i$$$ и $$$b_i$$$. Влияет ли эта операция на другие элементы?

Нет, не влияет. То есть мне нужно для каждого $$$i$$$ выбрать, какой из двух элементов $$${a_i,b_i}$$$ пойдет в массив $$$a$$$, а какой в массив $$$b$$$. Дальше я смотрю на выражение, которое мне нужно максимизировать и на ограничения задачи. Вижу, что $$$1 \le a_i, b_i$$$ — положительные числа. В выражении есть слагаемое $$$\max(a)$$$, в таком случае мне удобно предположить, что максимум лежит где-нибудь в элементе $$$a_j$$$. Тогда как будет выглядеть выражение?

Выражение будет равно $$$a_j + \sum\limits_{i=1}^{n}b_i$$$. Раз я зафиксировал $$$a_j$$$, то я знаю $$$b_j$$$, а вот остальные $$$b_i, i\neq j$$$ я не знаю. Как мне выбрать остальные элементы $$$b_i$$$?

В качестве остальных элементов мне выгодно выбрать $$$max(a_i, b_i)$$$. Хоршо, тогда мне удобно в начале сделать так, чтобы $$$a_i \le b_i$$$ (с помощью операции из условия). Тогда я могу посчитать заранее $$$S = \sum\limits_{i=1}^{n}\max(a_i, b_i)$$$. Я ее считаю, потому что в будушем мне нужно будет вычислить второе слагаемое в выражении. Теперь, допустим, я считаю, что максимум лежит в $$$j$$$-м элементе. Причем возможно я опять сделаю операцию к $$$j$$$-му элементу. Тогда чему будет равна сумма $$$b$$$?

Она будет равна $$$S' = S - \max(a_i,b_i)+b_i$$$ — здесь я беру предподсчитанную сумму $$$S$$$, убираю $$$\max(a_i,b_i)$$$, потому что это слагаемое было в случае, если я предполагаю, что $$$a_i \le b_i$$$. А дальше добавляю текущий элемент $$$b_j$$$. Хорошо, тогда я могу обновить ответ с помощью числа $$$a_j + S'$$$. Но погодите. А что если $$$a_j$$$ не максимум? Все сломалось?

Нет, ничего не сломалось. Потому что наше выражение $$$a_j + S' \le ANS$$$, где ANS — ответ, потому что $$$a_j \le max(a)$$$. Но с другой стороны, в какой-то момент наш $$$a_j$$$ будет максимумом в оптимальном ответе и мы получим результат. Это частый метод — если мы хотим максимизировать что-то, где есть слагаемое $$$\max(a)$$$, то мы не обязаны делать так, чтобы $$$a_j$$$ был максимумом, а можем просто перебрать все возможные $$$a_i$$$, чтобы получить ответ.

Я очень часто в задачах в голове представляю оптимальный ответ. Как он может выглядеть в этой задаче?

В этой задаче в оптимальном ответе все $$$a_i \lt 0$$$. Могу ли я получить такой ответ?

Точно не знаю, но попробую его получить. Какое простое действие я могу сделать? Я могу взять например самый левый $$$i$$$, что $$$a_i \gt 0$$$ и поменять знак на префиксе, но тогда $$$a_i$$$ станет отрицательным а все элементы левее него станут положительными, нам это не подходит. Что еще могу простого сделать? Какой $$$a_i \gt 0$$$ выбрать?

Могу взять самый правый $$$i$$$, что $$$a_i \gt 0$$$, тогда правее него все элементы $$$a_j \lt 0, j \gt i$$$. Тогда после применения этой операции $$$a_i$$$ станет отрицательным, все элементы левее него поменяют знак, а элементы правее останутся отрицательными. Тогда где будет следующий положительный элемент?

Следующий положительный элемент будет левее $$$i$$$, а именно в некотором индексе $$$k \lt i$$$, потому что мы сделали $$$a_i \lt 0$$$, причем $$$a_j \lt 0$$$ для всех $$$j \gt i$$$. Что мы можем тогда сделать?

Мы можем опять взять самый правый положительный элемент и применить операцию к нему. Тогда в итоге мы получим все $$$a_i \lt 0$$$. Посмотрю на ограничения. $$$n \le 2\cdot 10^5$$$, здесь не зайдет $$$O(n^2)$$$, но зайдет $$$O(n)$$$. Как я буду тогда действиовать?

Раз индекс самого правого положительного элемента у меня уменьшается, то есть двигается влево, то как мне выгодно обходить массив?

Мне выгодно обходить массив справа налево. Но я не могу втупую выполнять операции, потому что в таком случае решение будет работать за $$$O(n^2)$$$. Хорошо, что мне вообще нужно знать?

Мне нужно знать, какой знак у текущего элемента $$$a_i$$$. Что мне для этого нужно?

Раз каждая операция меняет знак на префиксе, то мне нужно знать количство операций, которые я уже сделал. Допустим я сделал $$$C$$$ операций. Какой тогда будет знак у текущего $$$a_i$$$?

Если $$$C$$$ четное, то знак не поменяется, а если нечетное, то поменяется. Тогда я могу определить знак $$$a_i$$$ и если $$$a_i \gt 0$$$, то применить очередную операцию, увеличив $$$C$$$ на единицу.

В этой задаче все немного сложнее. Мы хотим сделать сумму как можно больше. Но применять операции мы можем только к $$$a_i \gt 0$$$. Мы уже знаем, что для любого массива мы можем получить все отрицательные элементы из предыдущей задачи. На какие элементы в массиве я могу посмотреть?

Могу посмотреть на последний элемент в массиве. Что если он отрицательный? То есть $$$a_n \lt 0$$$? Можно ли его сделать положительным?

Если $$$a_n \lt 0$$$, то он навсегда останется отрицательным. То есть по сути мы можем просто выкинуть его из массива и решать задачу для подмассива $$$[a_1, a_2, \ldots, a_{n-1}]$$$. Тогда я могу выкинуть некоторый суффикс отрицательных элементов. И считать, что $$$a_n \gt 0$$$. Какие есть варианты для дальнейших действий?

Я могу либо никогда не применять операцию к $$$a_n$$$ (тогда я могу его просто выкинуть) либо в какой-то момент применить и сделать его отрицательным, но тогда он станет $$$a_n \lt 0$$$ и я уже не смогу вернуть его в положительные числа. Представим, что я применю операцию к $$$a_n$$$. Какая тогда будет максимально возможная сумма?

Максимально возможно сумма может быть достигнута, если $$$a_1 \gt 0, a_2 \gt 0, \ldots, a_{n-1} \gt 0, a_n \lt 0$$$. Могу ли я получить такой массив?

Да, могу. Я могу сначала сделать все элементы $$$a_i \lt 0, i \lt n$$$ как в прошлой задаче, а потом применить операцию к $$$a_n$$$. Как тогда выглядит общее решение?

Общее решение выглядит так: я перебираю $$$i: a_i \gt 0$$$, что сумма $$$|a_1| + |a_2| + \ldots + |a_{i-1}| - a_i + (a_{i+1}+a_{i+2}+\ldots+a_n)$$$ максимальна. А затем строю последовательность операций так, чтобы сначала сделать $$$a_j \lt 0, j \lt i$$$, а затем применяю операцию к $$$a_i$$$. Как мне быстро для каждого $$$i$$$ находить такую сумму?

С помощью префиксных и суффиксных сумм. $$$P_i = P_{i-1}+|a_i|, S_i = S_{i+1}+a_i$$$.

Как я ранее говорил, я во многих задачах, в голове представляю, что у меня уже есть оптимальный ответ. Пусть в этой задаче он равен $$$x = \min(a_1,b_1)$$$. Тогда какие простые условия или наблюдения я могу сделать?

Я могу посмотреть, что написано в условии, получается, что мы хотим, чтобы в конце $$$a_1,b_1 \ge x$$$. То есть в конце остались элементы, не меньшие $$$x$$$. Теперь помотрю на саму операцию, в ней есть операции сравнения. Представим, что в массиве есть элементы $$$x$$$ и $$$x + 1$$$. Важно ли мне, что второй элемент больше первого?

Нет, не важно, я ведь хочу понять, могу ли я сделать ответ равным $$$x$$$. Тогда на какие две группы я могу разделить элементы массивов?

Я могу заменить элементы $$$a_i,b_i \ge x$$$ на $$$1$$$, а элементы $$$a_i,b_i \lt 0$$$ на $$$0$$$. Тогда как выглядит операция из условия?

Точно также, только теперь $$$S$$$ содержит нули и единицы. Тогда какие случаи бывают?

Из

00
00

получится

0
0

Запишу это так

00 0
00 0

Еще есть варианты

00 0 | 01 0 | 01 0
01 0 | 00 0 | 01 1

Отсюда видно, что можно предположить, что $$$a_i \le b_i$$$, т.к. если их поменять местами, то ничего не поменяется

Тогда есть все три вида пар $$$(a_i,b_i)$$$.

1. $$$(0,0)$$$ — обозначим за $$$0$$$
2. $$$(0,1)$$$ — обозначим за $$$1$$$
3. $$$(1,1)$$$ — обозначим за $$$2$$$

Обозначим за $$$\cdot$$$ операцию из условия. Например $$$0\cdot 0 = 0, 0\cdot 1 = 0, 0\cdot 2 = 1, \ldots$$$

Что мы хотим получить в конце?

Мы хотим получить $$$2$$$. Чтобы получить $$$2$$$, какая должна быть последняя операция?

$$$2\cdot 1 = 2$$$ или $$$2\cdot 2 = 2$$$, видно, что чтобы получить 2 нам нужна либо вторая 2, либо 1. Это значит, что в исходном массиве должна быть хотя бы одна 2. Пусть мы нашли самую левую 2. Тогда левее нее только 0 и 1. Нам мешают нули. Что с ними можно сделать?

$$$0\cdot 0 = 0,0\cdot 1 = 0, 0\cdot 2 = 1$$$. То есть чтобы уничтожить ноль, нам нужен второй ноль. То есть если есть хотя бы один ноль, то мы от него никогда не избавимся?

Можем избавиться, но потратив на это одну 2, превратив их в 1. Или смерджив два нуля вместе.

Тогда если у нас нет 2, то ответ точно не построить. Теперь считаем, что есть 2. Если нет 0, то ответ можно построить. Осталось разобраться со случаем, когда есть и 2, и 0. Если есть только одна 2, то ответа нет. Теперь пусть у нас есть две 2. Тогда нули между которыми нет 2, мы можем смерджить. Еще мы можем забыть про 1. Тогда останется несколько случаев. Каких?

02020 => NO
0202  => NO
022   => YES
202   => YES

Значит после объединения 0, количество 2 должно быть больше чем количество 0.

Первое, что я делаю, это представляю себе в голове процесс, описанный в условии. Получается, мы берем лист с максимальным индексом, а дальше удаляем другие листы, которые меньше него пока не образуется новый лист больше нашего. В таких ситуациях я смотрю на то, как начинается и как заканчивается процесс. Как закончится процесс этой задаче?

Процесс закочнится, когда останется вершина $$$n$$$. Обозначим множество $$$S = (s_1,s_2,\ldots,s_k)$$$, причем $$$s_1 \lt s_2 \lt \ldots \lt s_k$$$. Чем равны $$$s_1$$$ и $$$s_k$$$?

$$$s_1$$$ — максимальный лист в исходном дереве. $$$s_k = n$$$. В каком порядке мы будем выписывать числа из множества $$$S$$$?

В порядке возрастания. То есть сначала число $$$s_1$$$, потом $$$s_2$$$, и так далее до числа $$$s_k = n$$$. То есть нам надо научиться прыгать из $$$s_i$$$ в $$$s_{i+1}$$$. В задачах про деревья удобно подвешивать их за определенную вершину. За какую вершину нам выгодно подвесить дерево?

Нам выгодно подвесить дерево за вершину $$$n$$$, так как весь процесс закончится именно в ней. Изначально мы стоим в вершине $$$s_1$$$. Какое у нее есть свойство?

Это лист. Теперь мы хотм получить следующее число $$$s_2$$$. Как мы можем сделать так, чтобы следующий максимальный лист был $$$s_2$$$?

Мы хотим удалять листы $$$v \lt s_1 \lt s_2$$$ пока $$$s_2$$$ не станет листом, значит в поддереве вершины $$$s_2$$$ все веиршны имеют индексы $$$ \lt s_1$$$. Достаточное ли это условие?

Не совсем, тут есть еще один случай. Когда $$$s_2 = n$$$, в таком случае мы хотим удалить все поддервеья вершины $$$n$$$ кроме того, где лежит $$$s_1$$$.

Тогда общее решение выглядит так. Мы подвешиваем дерево за вершину $$$n$$$. С помощью dfs-а начитываем максимумы в поддереве в массив $$$f_v$$$. Дальше считаем динамику $$$dp_v$$$ — количество путей из прыжков из вершины $$$v$$$ в вершину $$$n$$$. Тогда ответ будет в $$$dp_{s_1}$$$. База динамики — это когда мы прыгаем в вершину $$$n$$$. Это значит, что максимум по всем вершинам в других поддеревьях должен быть меньше $$$v$$$, тогда можем инициализировать $$$dp_v = 1$$$. Дальше идем в порядке уменьшения $$$v$$$. Осталось обработать второй переход, когда мы прыгаем не в $$$n$$$, в некую другую вершину $$$n \gt u \gt v$$$, что $$$f_u \lt v$$$ и по всем таким $$$u$$$ берем сумму $$$dp_u$$$. Как это сделать быстро?

С помощью Дерева Отрезков (ДО) или Дерева Фенвика. После обновления динамики в позицию $$$f_v$$$ кладем $$$dp_v$$$, а когда вычисляем сумму, то берем сумму на отрезке $$$[1,v - 1]$$$.

Я представляю в голове себе процесс, описанный в условии. По сути у нас есть $$$k$$$ коробок, куда мы складываем элементы $$$a_i$$$ в некотором порядке, причем каждый раз кладем элементы в меньшую из коробок. Мы хотим, чтобы коробка с максимальной суммой имела максимально мозножную сумму по всем перестановкам массива $$$a$$$. Дальше я смотрю на ограничения задачи, вижу, что $$$n \le 18$$$, скорее всего ожидается решение за $$$O(2^n \cdot poly(n))$$$, где $$$poly(n)$$$ — некоторый полином от $$$n$$$, например $$$n^2$$$. Хорошо, теперь я представляю у себя в голове оптимальный ответ и беру коробку с максимальной суммой. Пусть в ней лежат элементы $$$a_1, a_2, \ldots, a_l$$$. Смотрим на условие, когда мы кладем элементы в коробку?

Мы кладем элементы в коробку, когда в коробке минимальная сумма, то есть наша коробка была минимумом $$$(l-1)$$$ раз. Пусть $$$A_1=a_1,A_2=a_1+a_2,\ldots,A_l = a_1+a_2+\ldots+a_l$$$. Пусть $$$S$$$ — миниальная сумма по всем остальным коробкам. Получается, когда мы добавляли $$$a_1$$$, должно быть верно, что $$$0 \le S$$$, а когда добавляем элемент $$$a_i$$$?

Тогда должно быть верно, что $$$A_{i-1} \le S$$$, причем для всех $$$i$$$. В том числе и для $$$a_l$$$, то сть $$$A_l - a_l$$$ должно быть $$$ \le S$$$. Тогда какой элемент нам выгоднее брать в качестве $$$a_l$$$?

$$$a_l$$$ — максимум в исходном массиве $$$a$$$, потому что с одной стороны мы оптимизируем неравенство $$$A_l - a_l$$$, а с другой стороны максимизируем сумму в нашей коробке. Хорошо, к чему тогда сводится задача?

Мы точно добавляем максимальный элемент в ответ и убираем его из исходного массива. Тогда оствшиеся элементы нужно разделить на $$$k$$$ групп так, чтобы максимизировать сумма минимальной коробки (куда мы и положим тот самый максимум). Как решить эту задачу?

С помощью бинарного поиска. Нам нужно научиться проверять, можно ли разбить массив на $$$k$$$ групп так, чтобы каждая группа имела сумму хотя бы $$$x$$$. Как сделать эту проверку?

Будем считать максимальное количество групп, на которое можно разбить массив, чтобы каждая группа имела сумму хтоя бы $$$x$$$. Будем делать это с помощью динамиеческого проргаммирования. Будем хранить в динамике пару $$$(cnt,last)$$$, где $$$cnt$$$ — максимальное число групп, а $$$last$$$ — сумма последней группы. База $$$dp_{mask} = (0, S_{mask})$$$. Тогда в каком случае мы можем разбить массив на $$$k$$$ групп, чтобы каждая группа имела сумму хотя бы $$$x$$$. Нужно, чтобы либо $$$dp_{all}.first \ge k$$$ или ($$$dp_{all}.first \ge k - 1$$$ и $$$dp_{all}.second \ge x$$$). Осталось только сделать переход. Как?

Мы будем перебирать маски (подмножества) в порядке возрастания. Пусть мы стоим в маске $$$mask$$$. Тогда нам нужно перебрать элемент $$$i \not\in mask$$$, который мы будем добавлять. Тогда какие есть переходы?

Мы либо создаем новую группу, либо добавляем элемент в текущую группу. Когда какой вариант использовать?

Если $$$dp_{mask}.second \ge x$$$, то создаем новую группу и обновляем $$$dp_{mask+i}$$$ бновляем парой $$$(dp_{mask}.first + 1, a_i)$$$. А ииначе обновляем значением $$$(dp_{mask}.first, dp_{mask}.second + a_i)$$$