Тренировочная сессия 16: динамика по префиксам отсортированных данных СЕССИЯ

Что тренируем сегодня

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

Сегодняшний приём — динамика по префиксам отсортированных данных, и обе задачи показывают его в двух типовых обстановках.

В первой из нескольких списков надо набрать элементы, и выгода растёт с их величиной. Обменный аргумент даёт: если из списка взято x элементов, то это ровно x наибольших. После этого состояние сжимается до «сколько взято из каждого списка» — какие именно, уже известно.

Во второй объекты надо назначить на позиции. Обменный аргумент даёт другое: оптимальное сопоставление не «пересекается», то есть после сортировки обеих сторон назначение идёт по порядку. И снова состояние — пара префиксов.

Коридор сегодня ~CF 1800 — верхняя граница «Плато». Впереди «Пик», и обе сегодняшние задачи — хорошая репетиция его стиля: половину работы делает доказательство, вторую — аккуратная таблица.

---

Теория

Динамика по префиксам отсортированных данных. Схема из трёх шагов: отсортировать, доказать обменом, что оптимум согласован с этим порядком, и только после этого выписывать таблицу — состоянием будут длины префиксов.

Форма 1 — набираем элементы из нескольких списков.

Когда применять:

• есть несколько наборов элементов, из которых составляются пары (или тройки), и выгода пары растёт по каждому её элементу;
• каждый элемент используется не более одного раза, а брать все не обязательно;
• размеры наборов невелики (сотни), но перебор сочетаний всё равно исключён.

Ключевая лемма: если из набора использовано ровно x элементов, то в оптимуме это x наибольших. Доказательство обменом: пусть использован элемент u, а неиспользованный v больше него. Заменим u на v в той паре, где u стоял. Выгода пары не уменьшится, потому что она возрастает по каждому элементу, а остальные пары не изменились.

Что это даёт: набор можно отсортировать по убыванию, и состояние динамики становится вектором «сколько элементов взято из каждого набора» — сами элементы определяются по индексу. Для трёх наборов состояние — тройка (i, j, k), а переходы соответствуют тому, какую пару мы составляем следующей.

Направление переходов удобнее прямое: из состояния (i, j, k) «выпускаем» переходы во все состояния, куда можно попасть, добавив одну пару. Так не нужно думать о том, какие ячейки уже посчитаны, — важно лишь, что индексы только растут.

Каркас приёма для двух наборов (для трёх добавляется третий индекс):

Где ошибаются: сортируют по возрастанию и берут префиксы — тогда лемма перестаёт работать, потому что «первые x» превращаются в наименьшие. Или наоборот, доказывают лемму для одного набора и молча переносят на остальные, не проверив, что выгода растёт по каждому аргументу.

Сложность приёма: произведение размеров наборов, умноженное на число видов переходов.

Форма 2 — назначаем объекты на позиции.

Когда применять:

• нужно назначить объекты на позиции один-к-одному, стоимость назначения — расстояние (модуль разности) или другая «выпуклая» мера;
• позиций больше, чем объектов, — часть позиций остаётся пустой;
• надо минимизировать суммарную стоимость.

Ключевое свойство: в оптимуме назначение не пересекается. Если объект a не больше объекта b, а назначенные им позиции идут в обратном порядке, то обмен позиций местами не увеличит суммарную стоимость. Для расстояний это проверяется разбором случаев: два отрезка, соединяющих точки «крест-накрест», всегда можно «расплести», и суммарная длина при этом не вырастет.

Следствие: если отсортировать и объекты, и позиции по возрастанию, то оптимальное назначение сохраняет порядок — i-й по величине объект получает позицию, которая правее позиции (i−1)-го. А значит задача решается динамикой:

dp[i][j] — минимальная стоимость, если рассмотрены первые i позиций и назначены первые j объектов:

• позиция i остаётся пустой: dp[i−1][j];
• позиция i отдана объекту j: dp[i−1][j−1] + расстояние(позиция i, объект j).

Ответ — dp[всего позиций][всего объектов].

Сколько позиций рассматривать, если их формально бесконечно много: достаточно ограничиться диапазоном, за пределы которого оптимум заведомо не выходит. Если объектов n и все их «желаемые» позиции не превышают n, то никакой объект не имеет смысла отправлять дальше позиции 2n: даже в худшем случае все n объектов помещаются в первые 2n позиций, а уводить объект дальше — только увеличивать расстояние.

Каркас приёма:

Где ошибаются: пытаются решать жадно — «каждому объекту ближайшую свободную позицию». Такая жадность неверна: занятая позиция может понадобиться другому объекту сильнее, и оптимум требует смотреть вперёд.

Сложность приёма: $O(\text{позиции} \times \text{объекты})$.

Как выписывать обменный аргумент. Оба доказательства сегодня устроены по одному шаблону, и его стоит запомнить целиком — он закрывает большинство задач, где «надо сначала отсортировать»:

1. Предположить, что оптимум существует и нарушает предполагаемый порядок: нашлась пара элементов, стоящих «не так».
2. Поменять эту пару местами, оставив всё остальное без изменений.
3. Показать неравенством, что итог не ухудшился. Обычно это одна строка вида $(x_2 - x_1)(y_2 - y_1) \ge 0$ или разбор двух-трёх случаев по взаимному расположению.
4. Заключить: раз каждое нарушение можно устранить, не ухудшив итог, существует оптимум без нарушений — а среди таких уже можно искать перебором по префиксам.

Ключевая тонкость третьего шага — «не ухудшился», а не «улучшился». Строгое улучшение доказать обычно нельзя (бывают равные варианты), но его и не требуется: достаточно, чтобы существовал хотя бы один упорядоченный оптимум.

Почему после доказательства состояние сжимается. Пока порядок не зафиксирован, состояние должно описывать, какие именно элементы взяты, — это подмножество, то есть экспоненциальный перебор. Как только доказано, что берутся наибольшие (или что назначение идёт по порядку), от подмножества остаётся одно число — его размер. Это и есть главный выигрыш приёма: доказательство не ускоряет код, оно уменьшает состояние, а уже это превращает перебор в таблицу.

Где приём перестаёт работать. Сортировка ничего не теряет ровно до тех пор, пока выгода монотонна по величине элемента. Как только выгода немонотонна — «слишком большой элемент штрафуется», «нужны элементы, чья сумма делится на три», — обменный аргумент не выписывается, и сортировка становится вредной: она перемешивает индексы и рушит связь с исходными позициями. Признак, что приём выбран неверно: доказательство «очевидно» на словах, но при попытке записать неравенство упирается в контрпример.

С чем путают. Внешне это похоже на жадность: там тоже сортируют и тоже доказывают обменом. Разница в том, что жадность после сортировки берёт элементы по одному правилу и не возвращается, а здесь после сортировки всё ещё остаётся выбор, который приходится перебирать таблицей. Практический признак: если после доказательства ответ выписывается формулой или одним проходом — это жадность (как в сессии 13); если остаётся вопрос «сколько взять из каждого списка» или «сколько позиций пропустить» — динамика.

---

Задача 1 — CF ~1800 — «Colored Rectangles»

Что дано

Есть палки трёх цветов: R красных, G зелёных и B синих, у каждой известна длина. Из двух палок разных цветов можно собрать прямоугольник — его площадь равна произведению длин. Каждая палка используется не более одного раза; собирать прямоугольники не обязательно из всех палок.

Нужно максимизировать суммарную площадь собранных прямоугольников.

Формат ввода:

• Строка 1: три числа R, G, B ($1 \le R, G, B \le 200$).
• Строка 2: R чисел — длины красных палок.
• Строка 3: G чисел — длины зелёных.
• Строка 4: B чисел — длины синих. Все длины от 1 до 2000.

Формат вывода: одно число — максимальная суммарная площадь.

Пример 1:

Ввод:
1 1 1
3
5
4

Вывод:
20

Пример 2:

Ввод:
2 1 3
9 5
1
2 8 5

Вывод:
99

Пример 3:

Ввод:
10 1 1
11 7 20 15 19 14 2 4 13 14
8
11

Вывод:
372

Разберём на примере

Пример 1: по одной палке каждого цвета — 3, 5 и 4. Можно собрать ровно один прямоугольник, и выгоднее взять две самые длинные палки: 5 · 4 = 20. Красная палка длины 3 остаётся неиспользованной, и это нормально — использовать всё условие не требует.

Пример 3 показывает то же самое в большем масштабе: красных палок десять, зелёная и синяя по одной. Значит прямоугольников не больше двух (каждый использует ровно одну не-красную палку), и оптимально соединить самые длинные красные с имеющимися: 20 · 11 = 220 и 19 · 8 = 152, итого 372.

А теперь пример 2, где начинается собственно задача: красные 9, 5, зелёная 1, синие 8, 5, 2. Соблазн — жадно брать самую выгодную пару из оставшихся: 9 · 8 = 72, затем 5 · 5 = 25, итого 97. Но можно лучше: после тех же двух прямоугольников остаётся зелёная палка 1 и синяя 2, из них собирается ещё один прямоугольник площадью 2 — итого 99. Жадность «взять самую большую пару» здесь не ошиблась, но легко построить тест, где ошибётся: важен не только вес пары, но и то, какие цвета она расходует.

Зато работает другое наблюдение. Если в оптимальном ответе использовано, скажем, две красные палки — то это две самые длинные красные. Иначе можно заменить более короткую использованную на более длинную неиспользованную: площадь прямоугольника, куда она входит, только вырастет. Значит после сортировки по убыванию нам достаточно знать, сколько палок каждого цвета израсходовано, — какие именно, определяется само.

Идея решения

Алгоритм в одну фразу: отсортировать каждый список по убыванию и посчитать dp[i][j][k] — максимальную площадь, если израсходованы i первых красных, j первых зелёных и k первых синих, с переходами «добавить прямоугольник из двух ещё не израсходованных палок разных цветов».

Почему это работает. Лемма о наибольших (доказана обменом выше) говорит, что множество использованных палок каждого цвета — это префикс отсортированного по убыванию списка. Поэтому состояние (i, j, k) полностью описывает ситуацию: какие палки уже потрачены, известно, а порядок, в котором собирались прямоугольники, на результат не влияет.

Переходов ровно три — по числу пар цветов:

• красная + зелёная: dp[i+1][j+1][k] ← dp[i][j][k] + r[i] · g[j];
• красная + синяя: dp[i+1][j][k+1] ← dp[i][j][k] + r[i] · b[k];
• зелёная + синяя: dp[i][j+1][k+1] ← dp[i][j][k] + g[j] · b[k].

Индексация с нуля здесь удобна: r[i] — это первая ещё не израсходованная красная палка, ровно та, которую лемма предписывает взять следующей.

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

Псевдокод

прочитать R, G, B и три списка длин
отсортировать каждый список по убыванию

dp[i][j][k] = 0 для всех i, j, k
ответ = 0

для i от 0 до R:
    для j от 0 до G:
        для k от 0 до B:
            текущее = dp[i][j][k]
            ответ = max(ответ, текущее)

            если i < R и j < G:
                dp[i+1][j+1][k] = max(dp[i+1][j+1][k], текущее + r[i] * g[j])
            если i < R и k < B:
                dp[i+1][j][k+1] = max(dp[i+1][j][k+1], текущее + r[i] * b[k])
            если j < G и k < B:
                dp[i][j+1][k+1] = max(dp[i][j+1][k+1], текущее + g[j] * b[k])

вывести ответ

Код решения

Комментарии по реализации. Переходы записаны «вперёд»: из посчитанной ячейки мы улучшаем три следующие. Так не нужно проверять, посчитаны ли источники, — все индексы только растут. Ответ обязан быть 64-битным: до 200 прямоугольников площадью до $2000 \cdot 2000 = 4 \cdot 10^6$ каждый, то есть до $8 \cdot 10^8$ — на грани 32-битного типа, а промежуточные значения лучше не проверять на прочность. Размер таблицы — до $201^3 \approx 8.1$ миллиона ячеек; в C++ это проходит с запасом, в Python такой объём уже требует терпения, и решение стоит писать с минимумом обращений по индексам (в коде выше строка dp[i][j] вынесена в переменную ровно для этого).

Проверка на примерах

Пример 1: r = [3], g = [5], b = [4]. Возможные переходы из dp[0][0][0]: красная+зелёная 3·5 = 15, красная+синяя 3·4 = 12, зелёная+синяя 5·4 = 20. Дальше ни из одного состояния перехода нет (осталась одна палка). Максимум — 20.

Наш вывод: 20 — совпадает с ожидаемым.

Пример 2: после сортировки r = [9, 5], g = [1], b = [8, 5, 2].

Дальше палок разных цветов не осталось. Максимум по таблице — 99. Наш вывод: 99 — совпадает с ожидаемым.

Пример 3: после сортировки r = [20, 19, 15, 14, 14, 13, 11, 7, 4, 2], g = [8], b = [11]. Зелёная и синяя палки по одной, значит прямоугольников не больше двух и оба обязаны включать красную. Лучшее: 20 · 11 = 220 и 19 · 8 = 152.

Наш вывод: 372 — совпадает с ожидаемым.

Крайние случаи

• По одной палке каждого цвета. Ровно один прямоугольник из двух наибольших.
• Один цвет в изобилии, два других по одной палке. Прямоугольников не больше двух (пример 3).
• Все палки одинаковой длины. Ответ равен количество прямоугольников · длина²; проверка того, что переходы не «застревают».
• Максимальный размер. $R = G = B = 200$ — 8.1 миллиона состояний, тест на время и память.
• Оптимум не использует все палки. Всегда, когда один цвет в избытке; поэтому ответ берётся как максимум по таблице.
• Максимальные длины. Все палки по 2000 — суммарная площадь до $8 \cdot 10^8$.

Типичные ошибки

1. Сортировать по возрастанию. Лемма о наибольших требует именно убывания, иначе префикс состояния указывает на самые короткие палки.
2. Жадно брать самую выгодную пару. Игнорирует расход цветов: пара может «съесть» палку, которая нужнее в другой комбинации.
3. Брать ответ из дальнего угла таблицы. Собирать прямоугольники из всех палок не требуется и часто невозможно; ответ — максимум по всем состояниям.
4. Разрешить пару из одного цвета. Условие требует ровно два разных цвета.
5. Считать в 32-битном типе. Суммарная площадь до $8 \cdot 10^8$; при неаккуратной реализации промежуточные значения могут подойти к границе вплотную.
6. Хранить таблицу неэффективно в Python. Восемь миллионов ячеек в списках списков — тяжело; в C++ то же самое проходит спокойно.

Сложность

Время: $O(R \cdot G \cdot B)$ — по три перехода на состояние. Память: $O(R \cdot G \cdot B)$.

---

Задача 2 — CF ~1800 — «Chef Monocarp»

Что дано

В духовке одновременно готовятся n блюд. Для каждого блюда известно его идеальное время готовности t[i]. Доставать блюда можно только в целые положительные минуты, и за одну минуту — не более одного блюда.

Если блюдо достали в минуту T, его «неудачность» равна |T − t[i]|. Нужно достать все блюда, минимизировав сумму неудачностей.

Формат ввода:

• Строка 1: число тестов.
• Для каждого теста: строка с числом n ($1 \le n \le 200$) и строка с n числами t[i] ($1 \le t_i \le n$). Сумма n по всем тестам не превышает 200.

Формат вывода: для каждого теста — минимальная суммарная неудачность.

Пример (пять тестов из примера в условии, собранные в один пакет):

Ввод:
5
6
4 2 4 4 5 2
7
7 7 7 7 7 7 7
1
1
5
5 1 2 4 3
4
1 4 4 4

Вывод:
4
12
0
0
2

Разберём на примере

Возьмём первый тест: t = [4, 2, 4, 4, 5, 2]. Отсортируем: 2, 2, 4, 4, 4, 5. Блюд шесть, минут доступно сколько угодно, но каждая — не больше одного блюда.

Попробуем очевидное назначение «по порядку, начиная с первой минуты»:

Сумма 4 — и это ответ. Заметьте, что «каждому блюду ближайшую свободную минуту» дало бы другой результат: первое блюдо с идеальным временем 2 заняло бы минуту 2, второе такое же — минуту 1 или 3, и дальше конфликт разрастается. Жадность здесь неверна принципиально: занять «свою» минуту может блюдо, которому она нужна меньше.

Второй тест — семь блюд, у всех идеальное время 7. Минуты обязаны быть разными, поэтому идеально попасть может только одно блюдо. Лучшее — расположить их симметрично вокруг семёрки: минуты 4, 5, 6, 7, 8, 9, 10, что даёт 3 + 2 + 1 + 0 + 1 + 2 + 3 = 12.

Отсюда видно и главное структурное свойство: если оба списка — блюда и минуты — отсортированы, то оптимальное назначение идёт по порядку, без «перекрещиваний». Действительно, если бы блюдо с меньшим идеальным временем получило минуту позже, чем блюдо с большим, обмен этих двух минут не увеличил бы сумму: два «перекрещенных» отрезка на прямой всегда можно расплести, не удлинив их суммарно.

Осталось понять, какие минуты вообще рассматривать. Идеальные времена не превышают n, блюд ровно n, поэтому дальше минуты 2n уводить блюдо смысла нет: все блюда помещаются в первые 2n минут, а любой выход дальше только увеличивает расстояние.

Идея решения

Алгоритм в одну фразу: отсортировать идеальные времена и посчитать dp[i][j] — минимальную суммарную неудачность, если рассмотрены первые i минут (из 2n) и расставлены первые j блюд, с переходом «минуту пропустить» или «отдать минуту i блюду j».

Почему это работает. Свойство непересечения (обмен выше) означает, что в оптимуме j-е по возрастанию блюдо занимает минуту, которая строго правее минуты (j−1)-го блюда. Значит, просматривая минуты слева направо и блюда в порядке возрастания, мы ничего не теряем: любое оптимальное назначение представимо как последовательность решений «пропустить минуту» / «поставить сюда следующее по порядку блюдо».

Переход состоит ровно из этих двух вариантов:

• минута i не используется: dp[i][j] = dp[i−1][j];
• минута i отдана блюду j: dp[i][j] = dp[i−1][j−1] + |i − t[j]|.

Ответ — dp[2n][n]. Верхняя граница 2n обоснована выше; брать её больше безвредно, меньше — опасно.

Про недостижимые состояния. Если минут просмотрено меньше, чем блюд расставлено (i < j), состояние невозможно — его помечают «бесконечностью», иначе динамика насчитает несуществующие расстановки.

Псевдокод

для каждого теста:
    прочитать n, массив t
    отсортировать t по возрастанию
    M = 2 * n                          // достаточно рассмотреть столько минут

    dp[0][0] = 0
    dp[0][j] = БЕСКОНЕЧНОСТЬ для j >= 1

    для i от 1 до M:
        dp[i][0] = 0
        для j от 1 до min(i, n):
            пропустить = dp[i-1][j]
            поставить  = dp[i-1][j-1] + |i - t[j-1]|
            dp[i][j] = min(пропустить, поставить)
        для j от i+1 до n:
            dp[i][j] = БЕСКОНЕЧНОСТЬ

    вывести dp[M][n]

Код решения

Комментарии по реализации. Таблица свёрнута до двух строк: значение для минуты i зависит только от минуты i − 1. Внутренний цикл ограничен min(i, n) — состояния, где блюд расставлено больше, чем просмотрено минут, недостижимы и остаются «бесконечностью». В C++ перед сложением проверяется, не равен ли источник бесконечности: иначе прибавление расстояния переполнит значение. Суммарные ограничения мягкие (сумма n по всем тестам не больше 200), поэтому даже прямолинейная реализация укладывается в лимиты с огромным запасом — и в C++, и в Python.

Проверка на примерах

Тест 1: t = [2, 2, 4, 4, 4, 5] после сортировки, n = 6, минут рассматриваем 12. Оптимальное назначение — минуты 1…6 подряд:

Сумма 4. Наш вывод: 4 — совпадает с ожидаемым.

Тест 2: семь блюд с идеальным временем 7; лучшее расположение — минуты 4…10, неудачности 3, 2, 1, 0, 1, 2, 3. Сумма 12. Наш вывод: 12 — совпадает с ожидаемым.

Тест 3: одно блюдо с идеальным временем 1 — минута 1, неудачность 0. Наш вывод: 0 — совпадает с ожидаемым.

Тест 4: t = [1, 2, 3, 4, 5] после сортировки — каждое блюдо попадает в свою минуту. Наш вывод: 0 — совпадает с ожидаемым.

Тест 5: t = [1, 4, 4, 4] после сортировки. Блюдо с временем 1 занимает минуту 1; три блюда с временем 4 — минуты 3, 4, 5, неудачности 1, 0, 1. Сумма 2. Наш вывод: 2 — совпадает с ожидаемым.

Крайние случаи

• n = 1. Единственное блюдо получает свою идеальную минуту, ответ 0.
• Все идеальные времена различны и образуют 1…n. Ответ 0 — каждому своя минута.
• Все идеальные времена совпадают. Блюда расходятся симметрично вокруг общего значения (тест 2).
• Все идеальные времена равны 1. Раньше первой минуты уйти нельзя, поэтому блюда занимают минуты 1…n, и ответ равен 0 + 1 + … + (n−1).
• Все идеальные времена равны n. Симметричный случай; здесь и нужен запас минут до 2n.
• Много тестов подряд. Массивы обязаны переинициализироваться для каждого теста — классическая ошибка «состояние протекло из предыдущего теста».

Типичные ошибки

1. Жадность «каждому ближайшую свободную минуту». Неверна: занятая минута могла быть нужнее другому блюду.
2. Не отсортировать идеальные времена. Свойство непересечения работает только для отсортированных данных, иначе динамика по порядку теряет варианты.
3. Ограничить минуты числом n. При всех идеальных временах, равных n, часть блюд обязана уйти правее — ответ завысится.
4. Инициализировать недостижимые состояния нулём. Тогда динамика «расставит» блюда в несуществующие минуты и занизит ответ.
5. Прибавлять расстояние к бесконечности. В C++ это переполнение и отрицательное значение, которое побеждает в min.
6. Забыть про несколько тестов. Ответ выводится на каждый тест, а массивы очищаются между ними.
7. Считать минуты с нуля. По условию минуты положительные; сдвиг на единицу даёт систематически неверный ответ.

Сложность

Время: $O(n^2)$ на тест — 2n минут на n блюд. Память: $O(n)$ при свёртке до двух строк.

---

Самостоятельная тренировка

Все четыре — на сегодняшний приём: сначала сортировка, затем обменный аргумент, и только потом таблица по префиксам.

• Codeforces 4D «Mysterious Present» (~CF 1700) — из набора конвертов нужно построить самую длинную цепочку, где каждый следующий строго больше предыдущего по обоим измерениям и все они больше заданной открытки. Классическая пара «сортировка плюс динамика»: после упорядочивания по одному измерению задача превращается в поиск наибольшей возрастающей подпоследовательности по второму. Обратите внимание на строгость неравенств — здесь на ней ломается больше решений, чем на самой динамике.
• Codeforces 1256E «Yet Another Division Into Teams» (~CF 2000) — участников нужно разбить на группы не менее чем по три человека, минимизируя суммарный разброс внутри групп. Самая сложная в наборе, но обменный аргумент здесь особенно наглядный: докажите, что в оптимуме каждая группа — непрерывный отрезок отсортированного списка, и после этого динамика по префиксу выписывается за пару строк.
• Codeforces 1475D «Cleaning the Phone» (~CF 1800) — у каждого приложения есть занимаемая память и «ценность», равная 1 или 2; нужно освободить не менее m памяти, удалив приложения с минимальной суммарной ценностью. Подсказка: разделите приложения на два списка по ценности, отсортируйте оба по убыванию и переберите, сколько взято из первого, — остальное добирается префиксом второго.
• Codeforces 830A «Office Keys» (~CF 1800) — на прямой стоят люди и лежат ключи; каждому человеку нужно взять ключ и дойти до офиса, ключей не меньше, чем людей; нужно минимизировать момент, когда последний человек добрался до офиса. Подсказка: отсортируйте и людей, и ключи — оптимальное назначение не пересекается, а значит достаточно перебрать сдвиг «окна» ключей.

Прорешай их самостоятельно — если застрянешь, разбери с AI-партнёром на codepal.ru: он не даёт готовый ответ, а подводит к решению вопросами.

---

Что дальше

Обе задачи сегодня начинались одинаково: отсортировать и доказать, что после сортировки достаточно смотреть на префиксы или на порядок. Это не украшение решения, а его фундамент — без леммы о наибольших состояние (i, j, k) не имело бы смысла, а без свойства непересечения динамика по минутам теряла бы часть расстановок.

Следующая тренировка — последняя на «Плато»: перекладка корня дерева, когда ответ нужен сразу для всех вершин. Приём уже почти «пиковый» по технике, и он же — хороший мост к «Пику».