Первое, на что я обратил внимание — на то, что в условии сказано, что мы хотим в итоге сделать так, чтобы все элементы стали равны некоторому числу $$$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)$$$