Всем Привет!↵
↵
↵
↵
Меня зовут Максим и я очень давно хочу достичь рейтинга 3000. Я верю, что для этого мне надо научиться мыслить, как человек, у которого уже есть 3000 рейтинга. Очень часто в разборах пишут фразы "заметим, что..." или "докажем вот такой факт..." и дальше идет долгое доказательство этого факта. А то, каким образом я должен к этому факту прийти, как эта мысль должна зародиться у меня в голове, никто нигде не пишет. Я думаю, что не только у меня есть эта проблема, поэтому вместо того, чтобы ждать понятный разбор, я решил начать с себя. Именно поэтому, я решил написать свой первый пошаговый разбор, где я буду описывать ход своих мыслей и действий, которые позволяют мне придумать эти самые идеи.↵
↵
Также, я создал группу по прокачке навыков спортивного программирования для людей с рейтингом 1200- , чтобы помочь им стать лучше и достигнуть рейтинга 1500+. Если хотите больше об этом узнать, рекомендую прочитать [ЭТОТ ПОСТ](https://mirror.codeforces.com/blog/entry/153213) или заполнить [ФОРМУ](https://forms.yandex.ru/u/69ea4ba0493639794fd019d8). Эту группу я назвал **Polaris** в честь путеводной звезды. В Polaris ребята решают специально подобранные контесты под их уровень, дорешивают их с помощью пошаговых разборов, изучают новую теорию, решают специально подготовленные для них подводящие упражения, а также получают подробные рекомендации на основе их участия в тренировочных контестах. Более того, специально для участников группы я делаю пошаговые разборы тех задач, которые интересны самим участникам. Также, в группе регулярно ведется обсуждение прошедших контестов, а в ближайшем будущем мы будем готовиться к предстоящим олимпиадам (как школьным, так и студенческим). Присоединяйтесь, я буду вам очень рад!↵
↵
А теперь перейдем к самому разбору контеста. Но перед этим, я бы хотел ввести несколько правил чтения разбора для того, чтобы вы смогли получить максимум пользы от него.↵
↵
1. Перед чтением разбора задачи, убедитесь, что вы прочитали задачу, подумали над ней, извлекли из свой головы и записали/нарисовали максимальное количество идей и больше уже ниечго не можете придумать.↵
2. Во время чтения разбора, если в какой-то момент, какое-то предложение в разборе навело вас на новую мысль, перестаньте читать разбор и вернитесь к пункту (1), а именно продолжите с этого места генерровать новые идеи. Это очень важно.↵
3. Если вы дочитали текст разбора до конца и не поняли, как решать задачу или остались вопросы, то их нужно обязательно задать в комментариях или спросить в Polaris. Там вам помогут я и ребята, кто справился с этой задачей. Также в этом случае, полезно прочитать код, который будет прикреплен в разбору.↵
4. После того, как вы решили задачу, обязательно посмотрите код других участников и код с разбора. Возможно, он наведет вас на мысль о том, как можно было проще и быстрее реализовать решение задачи.↵
↵
A. Слаймы на прямой↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, на что я обратил внимание — на то, что в условии сказано, что мы хотим в итоге сделать так, чтобы все элементы стали равны некоторому числу $x$, то есть $a_1 = a_2 = \ldots = a_n = x$. В таких ситуациях мне удобно зафиксировать у себя в голове это число $x$. Дальше, я должен задать себе вопрос. Каким образом должны выглядеть операции, чтобы в итоге все элементы стали равны $x$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Во всех таких операциях я должен выбрать зафиксированный $x$, потому что сама операция как-бы приближает все числа к этому числу. Хорошо, допустим я знаю $x$. Хорошо, теперь я смотрю на саму операцию. В условии сказано, что она приближает все $a_i$ к $x$, причем все элементы не зависят друг от друга. Тогда через сколько операций число $a_i$ станет равно $x$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Через $|a_i - x|$ операций. Тогда через сколько операций все элементы станут равны $x$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Через $\max\limits_{i=1}^{n}|a_i - x|$. Хорошо. Дальше, я смотрю на ограничения задачи. Я вижу, что $1 \le a_i \le 1000$. А еще $2 \le n \le 1000$. Тогда какие $x$ мне нужно перебрать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Мне нужно перебрать $1 \le x \le 1000$, потому что сами $1 \le a_i \le 1000$. Тогда все будет работать за $1000\cdot n$. При заданных ограничениях задачи, такое решение будет работать меньше 1 сек.↵
</spoiler>↵
↵
Решение: [submission:376063858 ]↵
↵
B. Это шедевр!↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, что я делаю — это рисую массив $a$, а под ним массив $b$. Я вижу из условия, что мы меняем местами элементы $a_i$ и $b_i$. Влияет ли эта операция на другие элементы?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Нет, не влияет. То есть мне нужно для каждого $i$ выбрать, какой из двух элементов $\{a_i,b_i\}$ пойдет в массив $a$, а какой в массив $b$. Дальше я смотрю на выражение, которое мне нужно максимизировать и на ограничения задачи. Вижу, что $1 \le a_i, b_i$ — положительные числа. В выражении есть слагаемое $\max(a)$, в таком случае мне удобно предположить, что максимум лежит где-нибудь в элементе $a_j$. Тогда как будет выглядеть выражение?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Выражение будет равно $a_j + \sum\limits_{i=1}^{n}b_i$. Раз я зафиксировал $a_j$, то я знаю $b_j$, а вот остальные $b_i, i\neq j$ я не знаю. Как мне выбрать остальные элементы $b_i$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
В качестве остальных элементов мне выгодно выбрать $max(a_i, b_i)$. Хоршо, тогда мне удобно в начале сделать так, чтобы $a_i \le b_i$ (с помощью операции из условия). Тогда я могу посчитать заранее $S = \sum\limits_{i=1}^{n}\max(a_i, b_i)$. Я ее считаю, потому что в будушем мне нужно будет вычислить второе слагаемое в выражении.↵
Теперь, допустим, я считаю, что максимум лежит в $j$-м элементе. Причем возможно я опять сделаю операцию к $j$-му элементу. Тогда чему будет равна сумма $b$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Она будет равна $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$ не максимум? Все сломалось?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Нет, ничего не сломалось. Потому что наше выражение $a_j + S' \le ANS$, где ANS — ответ, потому что $a_j \le max(a)$. ↵
Но с другой стороны, в какой-то момент наш $a_j$ будет максимумом в оптимальном ответе и мы получим результат. Это частый метод — если мы хотим максимизировать что-то, где есть слагаемое $\max(a)$, то мы не обязаны делать так, чтобы $a_j$ был максимумом, а можем просто перебрать все возможные $a_i$, чтобы получить ответ.↵
</spoiler>↵
↵
Решение: [submission:376063885 ]↵
↵
C1. Время переворотов (простая версия)↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Я очень часто в задачах в голове представляю оптимальный ответ. Как он может выглядеть в этой задаче?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
В этой задаче в оптимальном ответе все $a_i < 0$. Могу ли я получить такой ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Точно не знаю, но попробую его получить. Какое простое действие я могу сделать? Я могу взять например самый левый $i$, что $a_i > 0$ и поменять знак на префиксе, но тогда $a_i$ станет отрицательным а все элементы левее него станут положительными, нам это не подходит. Что еще могу простого сделать? Какой $a_i > 0$ выбрать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Могу взять самый правый $i$, что $a_i > 0$, тогда правее него все элементы $a_j < 0, j > i$. Тогда после применения этой операции $a_i$ станет отрицательным, все элементы левее него поменяют знак, а элементы правее останутся отрицательными. Тогда где будет следующий положительный элемент?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Следующий положительный элемент будет левее $i$, а именно в некотором индексе $k < i$, потому что мы сделали $a_i < 0$, причем $a_j < 0$ для всех $j > i$. Что мы можем тогда сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Мы можем опять взять самый правый положительный элемент и применить операцию к нему. Тогда в итоге мы получим все $a_i < 0$. Посмотрю на ограничения. $n \le 2\cdot 10^5$, здесь не зайдет $O(n^2)$, но зайдет $O(n)$. Как я буду тогда действиовать? ↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Раз индекс самого правого положительного элемента у меня уменьшается, то есть двигается влево, то как мне выгодно обходить массив?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Мне выгодно обходить массив справа налево. Но я не могу втупую выполнять операции, потому что в таком случае решение будет работать за $O(n^2)$. Хорошо, что мне вообще нужно знать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Мне нужно знать, какой знак у текущего элемента $a_i$. Что мне для этого нужно?↵
</spoiler>↵
↵
<spoiler summary="Шаг 10">↵
Раз каждая операция меняет знак на префиксе, то мне нужно знать количство операций, которые я уже сделал. Допустим я сделал $C$ операций. Какой тогда будет знак у текущего $a_i$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 11">↵
Если $C$ четное, то знак не поменяется, а если нечетное, то поменяется. Тогда я могу определить знак $a_i$ и если $a_i > 0$, то применить очередную операцию, увеличив $C$ на единицу.↵
</spoiler>↵
↵
Решение: [submission:376063904]↵
↵
C2. Время переворотов (сложная версия)↵
===================↵
↵
<spoiler summary="Шаг 1">↵
В этой задаче все немного сложнее. Мы хотим сделать сумму как можно больше. Но применять операции мы можем только к $a_i > 0$. Мы уже знаем, что для любого массива мы можем получить все отрицательные элементы из предыдущей задачи. На какие элементы в массиве я могу посмотреть?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Могу посмотреть на последний элемент в массиве. Что если он отрицательный? То есть $a_n < 0$? Можно ли его сделать положительным?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Если $a_n < 0$, то он навсегда останется отрицательным. То есть по сути мы можем просто выкинуть его из массива и решать задачу для подмассива $[a_1, a_2, \ldots, a_{n-1}]$. Тогда я могу выкинуть некоторый суффикс отрицательных элементов. И считать, что $a_n > 0$. Какие есть варианты для дальнейших действий?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Я могу либо никогда не применять операцию к $a_n$ (тогда я могу его просто выкинуть) либо в какой-то момент применить и сделать его отрицательным, но тогда он станет $a_n < 0$ и я уже не смогу вернуть его в положительные числа. Представим, что я применю операцию к $a_n$. Какая тогда будет максимально возможная сумма?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Максимально возможно сумма может быть достигнута, если $a_1 > 0, a_2 > 0, \ldots, a_{n-1} > 0, a_n<0$. Могу ли я получить такой массив?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Да, могу. Я могу сначала сделать все элементы $a_i < 0, i < n$ как в прошлой задаче, а потом применить операцию к $a_n$. Как тогда выглядит общее решение?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Общее решение выглядит так: я перебираю $i: a_i > 0$, что сумма $|a_1| + |a_2| + \ldots + |a_{i-1}| - a_i + (a_{i+1}+a_{i+2}+\ldots+a_n)$ максимальна. А затем строю последовательность операций так, чтобы сначала сделать $a_j < 0, j < i$, а затем применяю операцию к $a_i$. Как мне быстро для каждого $i$ находить такую сумму?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
С помощью префиксных и суффиксных сумм. $P_i = P_{i-1}+|a_i|, S_i = S_{i+1}+a_i$.↵
</spoiler>↵
↵
Решение: [submission:376063922]↵
↵
D. Я, когда задача на медиану↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Как я ранее говорил, я во многих задачах, в голове представляю, что у меня уже есть оптимальный ответ. Пусть в этой задаче он равен $x = \min(a_1,b_1)$. Тогда какие простые условия или наблюдения я могу сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Я могу посмотреть, что написано в условии, получается, что мы хотим, чтобы в конце $a_1,b_1 \ge x$. То есть в конце остались элементы, не меньшие $x$. Теперь помотрю на саму операцию, в ней есть операции сравнения. Представим, что в массиве есть элементы $x$ и $x + 1$. Важно ли мне, что второй элемент больше первого?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Нет, не важно, я ведь хочу понять, могу ли я сделать ответ равным $x$. Тогда на какие две группы я могу разделить элементы массивов?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Я могу заменить элементы $a_i,b_i \ge x$ на $1$, а элементы $a_i,b_i < 0$ на $0$. Тогда как выглядит операция из условия?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Точно также, только теперь $S$ содержит нули и единицы. Тогда какие случаи бывают?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Из ↵
↵
~~~~~↵
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$↵
↵
Что мы хотим получить в конце?↵
↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Мы хотим получить $2$. Чтобы получить $2$, какая должна быть последняя операция?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
$2\cdot 1 = 2$ или $2\cdot 2 = 2$, видно, что чтобы получить 2 нам нужна либо вторая 2, либо 1. Это значит, что в исходном массиве должна быть хотя бы одна 2. Пусть мы нашли самую левую 2. Тогда левее нее только 0 и 1. Нам мешают нули. Что с ними можно сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
$0\cdot 0 = 0,0\cdot 1 = 0, 0\cdot 2 = 1$. То есть чтобы уничтожить ноль, нам нужен второй ноль. То есть если есть хотя бы один ноль, то мы от него никогда не избавимся?↵
</spoiler>↵
↵
<spoiler summary="Шаг 10">↵
Можем избавиться, но потратив на это одну 2, превратив их в 1. Или смерджив два нуля вместе. ↵
</spoiler>↵
↵
<spoiler summary="Шаг 11">↵
Тогда если у нас нет 2, то ответ точно не построить. Теперь считаем, что есть 2. Если нет 0, то ответ можно построить.↵
Осталось разобраться со случаем, когда есть и 2, и 0. Если есть только одна 2, то ответа нет. Теперь пусть у нас есть две 2. Тогда нули между которыми нет 2, мы можем смерджить. Еще мы можем забыть про 1. Тогда останется несколько случаев. Каких?↵
</spoiler>↵
↵
<spoiler summary="Шаг 12">↵
↵
~~~~~↵
02020 => NO↵
0202 => NO↵
022 => YES↵
202 => YES↵
~~~~~↵
↵
Значит после объединения 0, количество 2 должно быть больше чем количество 0.↵
↵
</spoiler>↵
↵
Решение: [submission:376063934]↵
↵
E. Дерево деструкции↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, что я делаю, это представляю себе в голове процесс, описанный в условии. Получается, мы берем лист с максимальным индексом, а дальше удаляем другие листы, которые меньше него пока не образуется новый лист больше нашего.↵
В таких ситуациях я смотрю на то, как начинается и как заканчивается процесс. Как закончится процесс этой задаче?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Процесс закочнится, когда останется вершина $n$. Обозначим множество $S = (s_1,s_2,\ldots,s_k)$, причем $s_1 < s_2 < \ldots < s_k$. Чем равны $s_1$ и $s_k$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
$s_1$ — максимальный лист в исходном дереве. $s_k = n$. В каком порядке мы будем выписывать числа из множества $S$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
В порядке возрастания. То есть сначала число $s_1$, потом $s_2$, и так далее до числа $s_k = n$.↵
То есть нам надо научиться прыгать из $s_i$ в $s_{i+1}$. В задачах про деревья удобно подвешивать их за определенную вершину. За какую вершину нам выгодно подвесить дерево?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Нам выгодно подвесить дерево за вершину $n$, так как весь процесс закончится именно в ней.↵
Изначально мы стоим в вершине $s_1$. Какое у нее есть свойство?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Это лист. Теперь мы хотм получить следующее число $s_2$. Как мы можем сделать так, чтобы следующий максимальный лист был $s_2$? ↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Мы хотим удалять листы $v < s_1 < s_2$ пока $s_2$ не станет листом, значит в поддереве вершины $s_2$ все веиршны имеют индексы $<s_1$. Достаточное ли это условие?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Не совсем, тут есть еще один случай. Когда $s_2 = n$, в таком случае мы хотим удалить все поддервеья вершины $n$ кроме того, где лежит $s_1$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Тогда общее решение выглядит так. Мы подвешиваем дерево за вершину $n$. С помощью dfs-а начитываем максимумы в поддереве в массив $f_v$. Дальше считаем динамику $dp_v$ — количество путей из прыжков из вершины $v$ в вершину $n$. Тогда ответ будет в $dp_{s_1}$. База динамики — это когда мы прыгаем в вершину $n$. Это значит, что максимум по всем вершинам в других поддеревьях должен быть меньше $v$, тогда можем инициализировать $dp_v = 1$. Дальше идем в порядке уменьшения $v$. Осталось обработать второй переход, когда мы прыгаем не в $n$, в некую другую вершину $n > u > v$, что $f_u < v$ и по всем таким $u$ берем сумму $dp_u$. Как это сделать быстро?↵
</spoiler>↵
↵
<spoiler summary="Шаг 10">↵
С помощью Дерева Отрезков (ДО) или Дерева Фенвика. После обновления динамики в позицию $f_v$ кладем $dp_v$, а когда вычисляем сумму, то берем сумму на отрезке $[1,v - 1]$.↵
</spoiler>↵
↵
Решение: [submission:375933658]↵
↵
F. Дисбаланс нагрузки↵
===================↵
↵
<spoiler summary="Шаг 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$. Смотрим на условие, когда мы кладем элементы в коробку?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Мы кладем элементы в коробку, когда в коробке минимальная сумма, то есть наша коробка была минимумом $(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$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Тогда должно быть верно, что $A_{i-1} \le S$, причем для всех $i$. В том числе и для $a_l$, то сть $A_l - a_l$ должно быть $ \le S$. Тогда какой элемент нам выгоднее брать в качестве $a_l$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
$a_l$ — максимум в исходном массиве $a$, потому что с одной стороны мы оптимизируем неравенство $A_l - a_l$, а с другой стороны максимизируем сумму в нашей коробке. Хорошо, к чему тогда сводится задача?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Мы точно добавляем максимальный элемент в ответ и убираем его из исходного массива. Тогда оствшиеся элементы нужно разделить на $k$ групп так, чтобы максимизировать сумма минимальной коробки (куда мы и положим тот самый максимум).↵
Как решить эту задачу?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
С помощью бинарного поиска. Нам нужно научиться проверять, можно ли разбить массив на $k$ групп так, чтобы каждая группа имела сумму хотя бы $x$. Как сделать эту проверку?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Будем считать максимальное количество групп, на которое можно разбить массив, чтобы каждая группа имела сумму хтоя бы $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$). Осталось только сделать переход. Как?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Мы будем перебирать маски (подмножества) в порядке возрастания. Пусть мы стоим в маске $mask$. Тогда нам нужно перебрать элемент $i \not\in mask$, который мы будем добавлять. Тогда какие есть переходы?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Мы либо создаем новую группу, либо добавляем элемент в текущую группу. Когда какой вариант использовать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 10">↵
Если $dp_{mask}.second \ge x$, то создаем новую группу и обновляем $dp_{mask+i}$ бновляем парой $(dp_{mask}.first + 1, a_i)$. А ииначе обновляем значением $(dp_{mask}.first, dp_{mask}.second + a_i)$↵
</spoiler>↵
↵
Решение: [submission:375942904]↵
↵
![ ](
↵
Меня зовут Максим и я очень давно хочу достичь рейтинга 3000. Я верю, что для этого мне надо научиться мыслить, как человек, у которого уже есть 3000 рейтинга. Очень часто в разборах пишут фразы "заметим, что..." или "докажем вот такой факт..." и дальше идет долгое доказательство этого факта. А то, каким образом я должен к этому факту прийти, как эта мысль должна зародиться у меня в голове, никто нигде не пишет. Я думаю, что не только у меня есть эта проблема, поэтому вместо того, чтобы ждать понятный разбор, я решил начать с себя. Именно поэтому, я решил написать свой первый пошаговый разбор, где я буду описывать ход своих мыслей и действий, которые позволяют мне придумать эти самые идеи.↵
↵
Также, я создал группу по прокачке навыков спортивного программирования для людей с рейтингом 1200- , чтобы помочь им стать лучше и достигнуть рейтинга 1500+. Если хотите больше об этом узнать, рекомендую прочитать [ЭТОТ ПОСТ](https://mirror.codeforces.com/blog/entry/153213) или заполнить [ФОРМУ](https://forms.yandex.ru/u/69ea4ba0493639794fd019d8). Эту группу я назвал **Polaris** в честь путеводной звезды. В Polaris ребята решают специально подобранные контесты под их уровень, дорешивают их с помощью пошаговых разборов, изучают новую теорию, решают специально подготовленные для них подводящие упражения, а также получают подробные рекомендации на основе их участия в тренировочных контестах. Более того, специально для участников группы я делаю пошаговые разборы тех задач, которые интересны самим участникам. Также, в группе регулярно ведется обсуждение прошедших контестов, а в ближайшем будущем мы будем готовиться к предстоящим олимпиадам (как школьным, так и студенческим). Присоединяйтесь, я буду вам очень рад!↵
↵
А теперь перейдем к самому разбору контеста. Но перед этим, я бы хотел ввести несколько правил чтения разбора для того, чтобы вы смогли получить максимум пользы от него.↵
↵
1. Перед чтением разбора задачи, убедитесь, что вы прочитали задачу, подумали над ней, извлекли из свой головы и записали/нарисовали максимальное количество идей и больше уже ниечго не можете придумать.↵
2. Во время чтения разбора, если в какой-то момент, какое-то предложение в разборе навело вас на новую мысль, перестаньте читать разбор и вернитесь к пункту (1), а именно продолжите с этого места генерровать новые идеи. Это очень важно.↵
3. Если вы дочитали текст разбора до конца и не поняли, как решать задачу или остались вопросы, то их нужно обязательно задать в комментариях или спросить в Polaris. Там вам помогут я и ребята, кто справился с этой задачей. Также в этом случае, полезно прочитать код, который будет прикреплен в разбору.↵
4. После того, как вы решили задачу, обязательно посмотрите код других участников и код с разбора. Возможно, он наведет вас на мысль о том, как можно было проще и быстрее реализовать решение задачи.↵
↵
A. Слаймы на прямой↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, на что я обратил внимание — на то, что в условии сказано, что мы хотим в итоге сделать так, чтобы все элементы стали равны некоторому числу $x$, то есть $a_1 = a_2 = \ldots = a_n = x$. В таких ситуациях мне удобно зафиксировать у себя в голове это число $x$. Дальше, я должен задать себе вопрос. Каким образом должны выглядеть операции, чтобы в итоге все элементы стали равны $x$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Во всех таких операциях я должен выбрать зафиксированный $x$, потому что сама операция как-бы приближает все числа к этому числу. Хорошо, допустим я знаю $x$. Хорошо, теперь я смотрю на саму операцию. В условии сказано, что она приближает все $a_i$ к $x$, причем все элементы не зависят друг от друга. Тогда через сколько операций число $a_i$ станет равно $x$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Через $|a_i - x|$ операций. Тогда через сколько операций все элементы станут равны $x$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Через $\max\limits_{i=1}^{n}|a_i - x|$. Хорошо. Дальше, я смотрю на ограничения задачи. Я вижу, что $1 \le a_i \le 1000$. А еще $2 \le n \le 1000$. Тогда какие $x$ мне нужно перебрать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Мне нужно перебрать $1 \le x \le 1000$, потому что сами $1 \le a_i \le 1000$. Тогда все будет работать за $1000\cdot n$. При заданных ограничениях задачи, такое решение будет работать меньше 1 сек.↵
</spoiler>↵
↵
Решение: [submission:376063858 ]↵
↵
B. Это шедевр!↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, что я делаю — это рисую массив $a$, а под ним массив $b$. Я вижу из условия, что мы меняем местами элементы $a_i$ и $b_i$. Влияет ли эта операция на другие элементы?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Нет, не влияет. То есть мне нужно для каждого $i$ выбрать, какой из двух элементов $\{a_i,b_i\}$ пойдет в массив $a$, а какой в массив $b$. Дальше я смотрю на выражение, которое мне нужно максимизировать и на ограничения задачи. Вижу, что $1 \le a_i, b_i$ — положительные числа. В выражении есть слагаемое $\max(a)$, в таком случае мне удобно предположить, что максимум лежит где-нибудь в элементе $a_j$. Тогда как будет выглядеть выражение?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Выражение будет равно $a_j + \sum\limits_{i=1}^{n}b_i$. Раз я зафиксировал $a_j$, то я знаю $b_j$, а вот остальные $b_i, i\neq j$ я не знаю. Как мне выбрать остальные элементы $b_i$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
В качестве остальных элементов мне выгодно выбрать $max(a_i, b_i)$. Хоршо, тогда мне удобно в начале сделать так, чтобы $a_i \le b_i$ (с помощью операции из условия). Тогда я могу посчитать заранее $S = \sum\limits_{i=1}^{n}\max(a_i, b_i)$. Я ее считаю, потому что в будушем мне нужно будет вычислить второе слагаемое в выражении.↵
Теперь, допустим, я считаю, что максимум лежит в $j$-м элементе. Причем возможно я опять сделаю операцию к $j$-му элементу. Тогда чему будет равна сумма $b$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Она будет равна $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$ не максимум? Все сломалось?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Нет, ничего не сломалось. Потому что наше выражение $a_j + S' \le ANS$, где ANS — ответ, потому что $a_j \le max(a)$. ↵
Но с другой стороны, в какой-то момент наш $a_j$ будет максимумом в оптимальном ответе и мы получим результат. Это частый метод — если мы хотим максимизировать что-то, где есть слагаемое $\max(a)$, то мы не обязаны делать так, чтобы $a_j$ был максимумом, а можем просто перебрать все возможные $a_i$, чтобы получить ответ.↵
</spoiler>↵
↵
Решение: [submission:376063885 ]↵
↵
C1. Время переворотов (простая версия)↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Я очень часто в задачах в голове представляю оптимальный ответ. Как он может выглядеть в этой задаче?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
В этой задаче в оптимальном ответе все $a_i < 0$. Могу ли я получить такой ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Точно не знаю, но попробую его получить. Какое простое действие я могу сделать? Я могу взять например самый левый $i$, что $a_i > 0$ и поменять знак на префиксе, но тогда $a_i$ станет отрицательным а все элементы левее него станут положительными, нам это не подходит. Что еще могу простого сделать? Какой $a_i > 0$ выбрать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Могу взять самый правый $i$, что $a_i > 0$, тогда правее него все элементы $a_j < 0, j > i$. Тогда после применения этой операции $a_i$ станет отрицательным, все элементы левее него поменяют знак, а элементы правее останутся отрицательными. Тогда где будет следующий положительный элемент?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Следующий положительный элемент будет левее $i$, а именно в некотором индексе $k < i$, потому что мы сделали $a_i < 0$, причем $a_j < 0$ для всех $j > i$. Что мы можем тогда сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Мы можем опять взять самый правый положительный элемент и применить операцию к нему. Тогда в итоге мы получим все $a_i < 0$. Посмотрю на ограничения. $n \le 2\cdot 10^5$, здесь не зайдет $O(n^2)$, но зайдет $O(n)$. Как я буду тогда действиовать? ↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Раз индекс самого правого положительного элемента у меня уменьшается, то есть двигается влево, то как мне выгодно обходить массив?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Мне выгодно обходить массив справа налево. Но я не могу втупую выполнять операции, потому что в таком случае решение будет работать за $O(n^2)$. Хорошо, что мне вообще нужно знать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Мне нужно знать, какой знак у текущего элемента $a_i$. Что мне для этого нужно?↵
</spoiler>↵
↵
<spoiler summary="Шаг 10">↵
Раз каждая операция меняет знак на префиксе, то мне нужно знать количство операций, которые я уже сделал. Допустим я сделал $C$ операций. Какой тогда будет знак у текущего $a_i$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 11">↵
Если $C$ четное, то знак не поменяется, а если нечетное, то поменяется. Тогда я могу определить знак $a_i$ и если $a_i > 0$, то применить очередную операцию, увеличив $C$ на единицу.↵
</spoiler>↵
↵
Решение: [submission:376063904]↵
↵
C2. Время переворотов (сложная версия)↵
===================↵
↵
<spoiler summary="Шаг 1">↵
В этой задаче все немного сложнее. Мы хотим сделать сумму как можно больше. Но применять операции мы можем только к $a_i > 0$. Мы уже знаем, что для любого массива мы можем получить все отрицательные элементы из предыдущей задачи. На какие элементы в массиве я могу посмотреть?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Могу посмотреть на последний элемент в массиве. Что если он отрицательный? То есть $a_n < 0$? Можно ли его сделать положительным?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Если $a_n < 0$, то он навсегда останется отрицательным. То есть по сути мы можем просто выкинуть его из массива и решать задачу для подмассива $[a_1, a_2, \ldots, a_{n-1}]$. Тогда я могу выкинуть некоторый суффикс отрицательных элементов. И считать, что $a_n > 0$. Какие есть варианты для дальнейших действий?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Я могу либо никогда не применять операцию к $a_n$ (тогда я могу его просто выкинуть) либо в какой-то момент применить и сделать его отрицательным, но тогда он станет $a_n < 0$ и я уже не смогу вернуть его в положительные числа. Представим, что я применю операцию к $a_n$. Какая тогда будет максимально возможная сумма?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Максимально возможно сумма может быть достигнута, если $a_1 > 0, a_2 > 0, \ldots, a_{n-1} > 0, a_n<0$. Могу ли я получить такой массив?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Да, могу. Я могу сначала сделать все элементы $a_i < 0, i < n$ как в прошлой задаче, а потом применить операцию к $a_n$. Как тогда выглядит общее решение?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Общее решение выглядит так: я перебираю $i: a_i > 0$, что сумма $|a_1| + |a_2| + \ldots + |a_{i-1}| - a_i + (a_{i+1}+a_{i+2}+\ldots+a_n)$ максимальна. А затем строю последовательность операций так, чтобы сначала сделать $a_j < 0, j < i$, а затем применяю операцию к $a_i$. Как мне быстро для каждого $i$ находить такую сумму?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
С помощью префиксных и суффиксных сумм. $P_i = P_{i-1}+|a_i|, S_i = S_{i+1}+a_i$.↵
</spoiler>↵
↵
Решение: [submission:376063922]↵
↵
D. Я, когда задача на медиану↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Как я ранее говорил, я во многих задачах, в голове представляю, что у меня уже есть оптимальный ответ. Пусть в этой задаче он равен $x = \min(a_1,b_1)$. Тогда какие простые условия или наблюдения я могу сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Я могу посмотреть, что написано в условии, получается, что мы хотим, чтобы в конце $a_1,b_1 \ge x$. То есть в конце остались элементы, не меньшие $x$. Теперь помотрю на саму операцию, в ней есть операции сравнения. Представим, что в массиве есть элементы $x$ и $x + 1$. Важно ли мне, что второй элемент больше первого?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Нет, не важно, я ведь хочу понять, могу ли я сделать ответ равным $x$. Тогда на какие две группы я могу разделить элементы массивов?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Я могу заменить элементы $a_i,b_i \ge x$ на $1$, а элементы $a_i,b_i < 0$ на $0$. Тогда как выглядит операция из условия?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Точно также, только теперь $S$ содержит нули и единицы. Тогда какие случаи бывают?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Из ↵
↵
~~~~~↵
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$↵
↵
Что мы хотим получить в конце?↵
↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Мы хотим получить $2$. Чтобы получить $2$, какая должна быть последняя операция?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
$2\cdot 1 = 2$ или $2\cdot 2 = 2$, видно, что чтобы получить 2 нам нужна либо вторая 2, либо 1. Это значит, что в исходном массиве должна быть хотя бы одна 2. Пусть мы нашли самую левую 2. Тогда левее нее только 0 и 1. Нам мешают нули. Что с ними можно сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
$0\cdot 0 = 0,0\cdot 1 = 0, 0\cdot 2 = 1$. То есть чтобы уничтожить ноль, нам нужен второй ноль. То есть если есть хотя бы один ноль, то мы от него никогда не избавимся?↵
</spoiler>↵
↵
<spoiler summary="Шаг 10">↵
Можем избавиться, но потратив на это одну 2, превратив их в 1. Или смерджив два нуля вместе. ↵
</spoiler>↵
↵
<spoiler summary="Шаг 11">↵
Тогда если у нас нет 2, то ответ точно не построить. Теперь считаем, что есть 2. Если нет 0, то ответ можно построить.↵
Осталось разобраться со случаем, когда есть и 2, и 0. Если есть только одна 2, то ответа нет. Теперь пусть у нас есть две 2. Тогда нули между которыми нет 2, мы можем смерджить. Еще мы можем забыть про 1. Тогда останется несколько случаев. Каких?↵
</spoiler>↵
↵
<spoiler summary="Шаг 12">↵
↵
~~~~~↵
02020 => NO↵
0202 => NO↵
022 => YES↵
202 => YES↵
~~~~~↵
↵
Значит после объединения 0, количество 2 должно быть больше чем количество 0.↵
↵
</spoiler>↵
↵
Решение: [submission:376063934]↵
↵
E. Дерево деструкции↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, что я делаю, это представляю себе в голове процесс, описанный в условии. Получается, мы берем лист с максимальным индексом, а дальше удаляем другие листы, которые меньше него пока не образуется новый лист больше нашего.↵
В таких ситуациях я смотрю на то, как начинается и как заканчивается процесс. Как закончится процесс этой задаче?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Процесс закочнится, когда останется вершина $n$. Обозначим множество $S = (s_1,s_2,\ldots,s_k)$, причем $s_1 < s_2 < \ldots < s_k$. Чем равны $s_1$ и $s_k$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
$s_1$ — максимальный лист в исходном дереве. $s_k = n$. В каком порядке мы будем выписывать числа из множества $S$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
В порядке возрастания. То есть сначала число $s_1$, потом $s_2$, и так далее до числа $s_k = n$.↵
То есть нам надо научиться прыгать из $s_i$ в $s_{i+1}$. В задачах про деревья удобно подвешивать их за определенную вершину. За какую вершину нам выгодно подвесить дерево?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Нам выгодно подвесить дерево за вершину $n$, так как весь процесс закончится именно в ней.↵
Изначально мы стоим в вершине $s_1$. Какое у нее есть свойство?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Это лист. Теперь мы хотм получить следующее число $s_2$. Как мы можем сделать так, чтобы следующий максимальный лист был $s_2$? ↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Мы хотим удалять листы $v < s_1 < s_2$ пока $s_2$ не станет листом, значит в поддереве вершины $s_2$ все веиршны имеют индексы $<s_1$. Достаточное ли это условие?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Не совсем, тут есть еще один случай. Когда $s_2 = n$, в таком случае мы хотим удалить все поддервеья вершины $n$ кроме того, где лежит $s_1$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Тогда общее решение выглядит так. Мы подвешиваем дерево за вершину $n$. С помощью dfs-а начитываем максимумы в поддереве в массив $f_v$. Дальше считаем динамику $dp_v$ — количество путей из прыжков из вершины $v$ в вершину $n$. Тогда ответ будет в $dp_{s_1}$. База динамики — это когда мы прыгаем в вершину $n$. Это значит, что максимум по всем вершинам в других поддеревьях должен быть меньше $v$, тогда можем инициализировать $dp_v = 1$. Дальше идем в порядке уменьшения $v$. Осталось обработать второй переход, когда мы прыгаем не в $n$, в некую другую вершину $n > u > v$, что $f_u < v$ и по всем таким $u$ берем сумму $dp_u$. Как это сделать быстро?↵
</spoiler>↵
↵
<spoiler summary="Шаг 10">↵
С помощью Дерева Отрезков (ДО) или Дерева Фенвика. После обновления динамики в позицию $f_v$ кладем $dp_v$, а когда вычисляем сумму, то берем сумму на отрезке $[1,v - 1]$.↵
</spoiler>↵
↵
Решение: [submission:375933658]↵
↵
F. Дисбаланс нагрузки↵
===================↵
↵
<spoiler summary="Шаг 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$. Смотрим на условие, когда мы кладем элементы в коробку?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Мы кладем элементы в коробку, когда в коробке минимальная сумма, то есть наша коробка была минимумом $(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$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Тогда должно быть верно, что $A_{i-1} \le S$, причем для всех $i$. В том числе и для $a_l$, то сть $A_l - a_l$ должно быть $ \le S$. Тогда какой элемент нам выгоднее брать в качестве $a_l$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
$a_l$ — максимум в исходном массиве $a$, потому что с одной стороны мы оптимизируем неравенство $A_l - a_l$, а с другой стороны максимизируем сумму в нашей коробке. Хорошо, к чему тогда сводится задача?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Мы точно добавляем максимальный элемент в ответ и убираем его из исходного массива. Тогда оствшиеся элементы нужно разделить на $k$ групп так, чтобы максимизировать сумма минимальной коробки (куда мы и положим тот самый максимум).↵
Как решить эту задачу?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
С помощью бинарного поиска. Нам нужно научиться проверять, можно ли разбить массив на $k$ групп так, чтобы каждая группа имела сумму хотя бы $x$. Как сделать эту проверку?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Будем считать максимальное количество групп, на которое можно разбить массив, чтобы каждая группа имела сумму хтоя бы $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$). Осталось только сделать переход. Как?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Мы будем перебирать маски (подмножества) в порядке возрастания. Пусть мы стоим в маске $mask$. Тогда нам нужно перебрать элемент $i \not\in mask$, который мы будем добавлять. Тогда какие есть переходы?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Мы либо создаем новую группу, либо добавляем элемент в текущую группу. Когда какой вариант использовать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 10">↵
Если $dp_{mask}.second \ge x$, то создаем новую группу и обновляем $dp_{mask+i}$ бновляем парой $(dp_{mask}.first + 1, a_i)$. А ииначе обновляем значением $(dp_{mask}.first, dp_{mask}.second + a_i)$↵
</spoiler>↵
↵
Решение: [submission:375942904]↵
