Тренировочная сессия 23: экзамен — три задачи возрастающей сложности без разбора по шагам СЕССИЯ

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

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

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

Как проходить сессию:

1. Прочитай все три условия сразу, до того как начнёшь что-то решать. Оцени каждую задачу: что примерно требуется и сколько это займёт.
2. Реши сам, в каком порядке браться. Порядок «A, B, C» в статье — по возрастанию сложности, но твоё личное «легче/тяжелее» может отличаться, и доверять стоит ему.
3. Заведи таймер на три часа. Это средняя длина раунда, и ограничение по времени — половина упражнения.
4. Разборы читай только после того, как сдался или решил. Причём даже после успешного решения читать полезно: способ может отличаться, а разница между твоим и разобранным решением — самое ценное, что можно вынести из контеста.

Задачи подобраны из верхней части коридора «Пика»: одна на CF ~2300 и две на CF ~2400. Все три — на технику, знакомую по предыдущим тренировкам, но ни в одной приём не назван в условии.

Раздел «Теория» сегодня тоже про другое: не про алгоритмы (это было бы подсказкой), а про два контестных приёма, которые работают на любой задаче.

---

Теория

Приём 1. Читать ограничения как подсказку к нужной сложности.

Ограничения в условии — не формальность, а самая сильная подсказка из всех доступных. Автор задачи выбирает их так, чтобы задуманное решение проходило, а более простое — нет. Значит по величине входа можно с хорошей точностью восстановить, какой сложности решение от вас ждут.

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

Как решать. Ориентир — примерно $10^8$ элементарных операций в секунду для C++ (для Python смело делите на десять-двадцать). Отсюда таблица:

Мини-пример. В условии стоит $n \le 200$ и $k \le 1000$. Произведение $n \cdot n \cdot k = 4 \cdot 10^7$ — как раз укладывается. Это почти прямая надпись: «нужна динамика с тремя измерениями, два из которых по $n$, третье по $k$». Заметьте, насколько это сужает поиск ещё до того, как вы поняли, о чём задача.

Отдельно стоит смотреть на два ограничения рядом. Если написано $n \le 3 \cdot 10^5$ и $m \le 8$, то восьмёрка почти наверняка означает $2^m$ или $4^m$ где-то внутри. Маленькое число рядом с большим — всегда сигнал.

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

Приём 2. Стресс-тест: поймать ошибку до отправки, а не после.

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

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

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

Как решать:

1. Написать генератор маленьких случайных тестов — настолько маленьких, чтобы ответ можно было проверить перебором (обычно $n \le 6$, значения до 8).
2. Написать эталон — заведомо верное решение перебором, без оптимизаций и без ума. Оно может работать экспоненциальное время, это нормально.
3. Гонять цикл: сгенерировали тест, прогнали оба решения, сравнили вывод. Как только вывод разошёлся — остановиться и распечатать тест.
4. Полученный контрпример почти всегда крошечный, и на нём ошибка видна руками.

Генератор:

# gen.py — маленький случайный тест по номеру запуска
import random
import sys

random.seed(int(sys.argv[1]))
n = random.randint(1, 6)
print(n)
print(*[random.randint(1, 8) for _ in range(n)])

Цикл сравнения:

for i in $(seq 1 500); do
    python3 gen.py $i > test.txt
    ./solution < test.txt > fast.txt          # проверяемое решение
    python3 brute.py < test.txt > slow.txt    # заведомо верный перебор
    if ! diff -q fast.txt slow.txt > /dev/null; then
        echo "Расхождение на тесте $i:"
        cat test.txt
        break
    fi
done
echo "готово"

Мини-пример. Решение с жадностью «брать самый дешёвый элемент» прошло оба примера из условия. Стресс-тест на пятистах случайных входах из шести чисел находит контрпример на четвёртом же тесте — и на четырёх числах сразу видно, почему жадность неверна. Без стресс-теста та же ошибка стоила бы получаса и нескольких отправок.

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

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

---

Экзамен: три задачи

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

Задача A — CF ~2300 — «Sonya and Problem Wihtout a Legend»

Дан массив из n чисел. За одну операцию разрешается увеличить или уменьшить любой элемент на единицу; каждая операция стоит одну единицу. Нужно минимальной суммарной стоимостью сделать массив строго возрастающим.

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

• Строка 1: число n ($1 \le n \le 3000$).
• Строка 2: n чисел a[1] … a[n] ($1 \le a_i \le 10^9$).

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

Пример 1:

Ввод:
7
2 1 5 11 5 9 11

Вывод:
9

Пример 2:

Ввод:
5
5 4 3 2 1

Вывод:
12

Задача B — CF ~2400 — «Tree and Queries»

Дано дерево из n вершин, подвешенное за вершину 1. Каждая вершина покрашена в некоторый цвет. Далее следуют m запросов вида «v, k»: сколько различных цветов встречается в поддереве вершины v не менее k раз.

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

• Строка 1: два числа n и m ($1 \le n, m \le 10^5$).
• Строка 2: n чисел — цвета вершин ($1 \le c_i \le 10^5$).
• Каждая из следующих n − 1 строк: два числа — концы ребра.
• Каждая из следующих m строк: два числа v и k.

Формат вывода: m строк — ответы на запросы в порядке их поступления.

Пример:

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

Вывод:
2
2
1
0
1

Задача C — CF ~2400 — «Group Projects»

Есть n участников, у каждого известен числовой уровень a[i]. Всех нужно разбить на группы: групп может быть сколько угодно, каждый участник попадает ровно в одну. Несбалансированность группы — разность наибольшего и наименьшего уровня внутри неё (для группы из одного участника это ноль).

Сколько существует разбиений, у которых сумма несбалансированностей всех групп не превосходит k? Ответ вывести по модулю $10^9 + 7$. Два разбиения различны, если какие-то два участника оказались вместе в одном и порознь в другом.

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

• Строка 1: два числа n и k ($1 \le n \le 200$, $0 \le k \le 1000$).
• Строка 2: n чисел a[1] … a[n] ($1 \le a_i \le 500$).

Формат вывода: одно число — количество разбиений по модулю $10^9 + 7$.

Пример 1:

Ввод:
3 1
1 2 3

Вывод:
3

Пример 2:

Ввод:
4 0
1 1 2 2

Вывод:
4

---

Разбор задачи A — «Sonya and Problem Wihtout a Legend»

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

Возьмём второй пример: 5 4 3 2 1. Массив убывает, а нужен строго возрастающий. Наивная мысль — «поднять каждый следующий чуть выше предыдущего» — сразу упирается в вопрос: а насколько поднимать, если менять можно и в другую сторону?

Первым делом избавимся от слова «строго». Если массив b строго возрастает, то b[i] ≥ b[i-1] + 1, то есть b[i] − i не убывает. Значит достаточно заменить a[i] на a[i] − i (нумерация с нуля) и искать неубывающий массив — стоимость при этом не меняется, потому что каждый элемент сдвигается на константу вместе со своей целью.

Для 5 4 3 2 1 вычитаем 0, 1, 2, 3, 4 и получаем 5 3 1 −1 −3. Теперь надо сделать этот массив неубывающим минимальной суммой изменений.

Попробуем угадать ответ руками. Сделать всё равным одному числу x стоит $|5-x| + |3-x| + |1-x| + |-1-x| + |-3-x|$ — минимум достигается на медиане, то есть при x = 1, и равен $4 + 2 + 0 + 2 + 4 = 12$. Совпадает с ожидаемым ответом. Значит здесь оптимум — сделать все элементы одинаковыми, и это неслучайно: массив убывает целиком, «разложить» его на возрастающие куски негде.

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

Идея решения

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

Почему «строго возрастающий» сводится к «неубывающему». Массив b строго возрастает тогда и только тогда, когда b[i] − i не убывает: неравенство b[i] > b[i-1] для целых чисел равносильно b[i] ≥ b[i-1] + 1, то есть b[i] − i ≥ b[i-1] − (i-1). Стоимость $\sum |a[i] - b[i]|$ не меняется, если из обеих частей каждой разности вычесть i.

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

Переход динамики. dp[i][j] = |a[i] − b[j]| + min(dp[i-1][0..j]): i-й элемент можно приравнять к j-му кандидату, если предыдущий приравнен к любому кандидату не больше j-го. Минимум по префиксу считается на лету одной переменной, поэтому один слой обходится за $O(n)$, а вся динамика — за $O(n^2)$.

Почему $O(n^2)$ достаточно. При $n \le 3000$ это $9 \cdot 10^6$ операций — с запасом.

Про типы. Значения до $10^9$, элементов до 3000: суммарная стоимость доходит до $3 \cdot 10^{12}$, 32-битный тип переполняется.

Псевдокод

прочитать n, a
для i от 0 до n-1: a[i] -= i             // строго возрастающая -> неубывающая

b = отсортированный набор различных значений a
m = размер b

prev[j] = 0 для всех j                   // до первого элемента ограничений нет
для i от 0 до n-1:
    best = бесконечность
    для j от 0 до m-1:
        best = min(best, prev[j])        // минимум dp[i-1][0..j]
        cur[j] = best + |a[i] - b[j]|
    prev = cur

вывести min(prev)

Код решения

Комментарии по реализации. Минимум по префиксу dp[i-1][0..j] не пересчитывается заново для каждого j — он накапливается одной переменной по ходу того же цикла. Без этого решение было бы $O(n^3)$ и на трёх тысячах не прошло бы. Начальный слой заполнен нулями: до первого элемента никаких ограничений нет, поэтому «предыдущий» может быть любым. В C++ слои меняются местами через swap, а не переприсваиваются — это избавляет от лишнего выделения памяти на каждой из трёх тысяч итераций.

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

Пример 2: 5 4 3 2 1. После вычитания индексов — 5 3 1 −1 −3. Кандидаты: −3, −1, 1, 3, 5. Разбор выше показал, что оптимум — сделать все элементы равными 1, стоимость $4 + 2 + 0 + 2 + 4 = 12$. Наш вывод: 12 — совпадает с ожидаемым.

Пример 1: 2 1 5 11 5 9 11. После вычитания индексов — 2 0 3 8 1 4 5. Массив почти неубывающий: портят его вторая позиция (0 после 2) и пятая (1 после 8). Оптимальный неубывающий массив — 0 0 3 3 3 4 5, стоимость $2 + 0 + 0 + 5 + 2 + 0 + 0 = 9$. Наш вывод: 9 — совпадает с ожидаемым.

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

• n = 1. Массив из одного элемента уже строго возрастает; ответ 0.
• Массив уже строго возрастает. После вычитания индексов он неубывающий, стоимость 0.
• Массив строго убывает. Худший случай по стоимости: оптимум обычно сводит всё к одному значению.
• Все элементы равны. После вычитания индексов массив строго убывает — тот же случай, что выше.
• Значения до $10^9$ при n = 3000. Суммарная стоимость до $3 \cdot 10^{12}$; 64-битный тип обязателен.
• Отрицательные значения после сдвига. a[i] − i уходит ниже нуля — это нормально и не требует отдельной обработки.

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

1. Забыть про «строго». Без вычитания индексов решается задача про неубывающий массив, и ответ занижается.
2. Пытаться поднимать элементы только вверх. Уменьшать тоже можно, и в примере 1 оптимум именно уменьшает первый элемент.
3. Пересчитывать минимум по префиксу заново для каждого j. $O(n^3)$ вместо $O(n^2)$.
4. Считать стоимость в 32-битном типе. До $3 \cdot 10^{12}$.
5. Перебирать значения из всего диапазона $1..10^9$. Кандидатов достаточно n штук, и это отдельное утверждение, которое надо доказать, а не угадать.
6. Не убирать дубликаты из набора кандидатов. Работать будет, но лишние равные значения замедляют внутренний цикл вдвое-втрое.
7. Инициализировать нулевой слой бесконечностями. До первого элемента ограничений нет — там должны быть нули.

Сложность

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

---

Разбор задачи B — «Tree and Queries»

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

В примере дерево такое: к вершине 1 подвешены вершины 2 и 5; к вершине 2 — вершины 3 и 4; к вершине 5 — вершины 6, 7 и 8. Цвета по порядку: 1 2 2 3 3 2 3 3.

Посчитаем для каждого поддерева, сколько вершин какого цвета:

Теперь ответы: запрос 1 2 — цветов, встречающихся хотя бы дважды в поддереве 1, ровно два (цвета 2 и 3). Запрос 1 3 — тоже два (три и четыре вхождения). Запрос 1 4 — только цвет 3, ответ 1. Запрос 2 3 — в поддереве вершины 2 максимум два вхождения, ответ 0. Запрос 5 3 — цвет 3 встречается трижды, ответ 1.

Что мешает решить в лоб. Для каждого запроса обойти поддерево — $10^5$ запросов по $10^5$ вершин, то есть $10^{10}$. Не проходит.

Идея в другом. Заметим: если завести массив f, где f[j] — количество цветов, встречающихся не менее j раз в текущем рассматриваемом множестве вершин, то ответ на запрос (v, k) — это просто f[k]. И массив f очень легко поддерживать: когда счётчик какого-то цвета вырастает с x до x + 1, этот цвет впервые начинает удовлетворять условию «не менее x + 1», значит увеличивается ровно одна ячейка — f[x+1].

Осталось так организовать обход дерева, чтобы «текущее множество» вовремя оказывалось равно нужному поддереву — и чтобы суммарных добавлений и удалений было не $O(n^2)$, а $O(n\log n)$. Это и делает приём из предыдущей тренировки, только в варианте с явными операциями «добавить вершину» и «убрать вершину».

Идея решения

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

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

1. Обработать все лёгкие поддеревья по очереди, каждое — с полной очисткой счётчиков после себя.
2. Обработать тяжёлое поддерево без очистки — его счётчики остаются.
3. Добавить в счётчики все вершины лёгких поддеревьев и саму v. Теперь в счётчиках ровно поддерево v.
4. Ответить на все запросы вершины v.
5. Если v сама была лёгкой для своего предка — вычистить всё поддерево v из счётчиков.

Почему это $O(n\log n)$. Вершина добавляется заново каждый раз, когда она лежит в лёгком поддереве на пути к корню. Каждый переход по лёгкому ребру как минимум удваивает размер поддерева (иначе ребро было бы тяжёлым), а удвоений от 1 до n бывает не больше $\log_2 n$. Значит на вершину приходится не более $\log_2 n$ добавлений, и всего операций $O(n\log n)$ — около $1.7 \cdot 10^6$ при $n = 10^5$.

Почему ответ равен f[k]. По построению f[j] — количество цветов с числом вхождений не меньше j. Это ровно то, что спрашивают. Поддерживается f при добавлении вершины цвета c строчкой f[++cnt[c]] += 1, а при удалении — f[cnt[c]--] -= 1. Заметьте симметрию: добавление сначала увеличивает счётчик, потом трогает f, удаление — наоборот.

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

Про запрос с большим k. Если k больше n, ответ заведомо ноль; массив f такого индекса не содержит, и проверку надо ставить явно.

Псевдокод

прочитать дерево и цвета, запросы сгруппировать по вершине
обойти дерево из вершины 1 нерекурсивно, получив flat[] и tin[] так,
    чтобы поддерево v занимало отрезок [tin[v], tin[v] + size[v] - 1]
посчитать size[v] и тяжёлую дочернюю вершину heavy[v]

cnt[цвет] = 0, f[j] = 0

стек = [(1, сохранять, стадия 0)]
пока стек не пуст:
    (v, keep, стадия) = снять со стека
    если стадия == 0:
        положить (v, keep, стадия 1)
        положить (heavy[v], сохранять, стадия 0)          // если есть
        положить каждую лёгкую дочернюю (to, не сохранять, стадия 0)
        // лёгкие лежат выше — они и обработаются первыми
    иначе:
        для каждой лёгкой дочерней to:
            для i от tin[to] до tin[to] + size[to] - 1:
                c = цвет(flat[i]); cnt[c] += 1; f[cnt[c]] += 1
        c = цвет(v); cnt[c] += 1; f[cnt[c]] += 1
        для каждого запроса (k, номер) вершины v:
            ответ[номер] = f[k], если k <= n, иначе 0
        если не keep:
            для i от tin[v] до tin[v] + size[v] - 1:
                c = цвет(flat[i]); f[cnt[c]] -= 1; cnt[c] -= 1

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

Код решения

Комментарии по реализации. Обход развёрнут в цикл со стеком состояний (вершина, сохранять ли, стадия): стадия 0 раскладывает потомков, стадия 1 выполняет саму работу. Порядок укладки на стек существенный — тяжёлая вершина кладётся раньше лёгких, поэтому снимается позже, и лёгкие успевают полностью отработать и вычиститься до неё. Массив cnt размеряется по максимальному цвету, а не по n: цвета в условии независимы от количества вершин. Проверка k <= n перед обращением к f[k] обязательна — запрос вправе спросить про k, которого не бывает.

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

Пример из условия. Проследим момент, когда в счётчиках лежит поддерево вершины 5 ({5,6,7,8}, цвета 3, 2, 3, 3):

Запрос 5 3 читает f[3] = 1 — верно, только цвет 3 встречается не меньше трёх раз.

Для корня счётчики становятся cnt[1] = 1, cnt[2] = 3, cnt[3] = 4, а значит f[1] = 3, f[2] = 2, f[3] = 2, f[4] = 1. Запросы 1 2, 1 3, 1 4 дают 2, 2 и 1. Запрос 2 3 в поддереве вершины 2 читает f[3] = 0.

Наш вывод: 2 2 1 0 1 по строкам — совпадает с ожидаемым.

Проверим ещё вырожденный вход:

Ввод:
1 2
3
1 1
1 2

Вывод:
1
0

Одна вершина цвета 3: один цвет встречается хотя бы раз и ни одного — хотя бы дважды.

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

• n = 1. Рёбер нет; тяжёлой вершины тоже нет, и стадия 0 не кладёт на стек ничего лишнего.
• k > n. Ответ 0; без явной проверки — обращение за границу массива.
• Все цвета различны. Тогда f[1] = размер поддерева, а f[2] и дальше — нули.
• Все цвета одинаковы. f[j] = 1 для всех j до размера поддерева.
• Дерево-цепочка на $10^5$ вершин. Тяжёлая вершина всегда одна, лёгких поддеревьев нет — добавлений ровно n. Одновременно тест на нерекурсивность.
• Звезда. Все лучи лёгкие, но каждый размера 1 — добавлений тоже около n.
• Цвет больше n. Массив счётчиков должен размеряться по максимальному цвету.

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

1. Обходить поддерево на каждый запрос. $10^{10}$ операций.
2. Не сохранять счётчики тяжёлого поддерева. Тогда каждая вершина пересчитывается на каждом уровне — снова квадрат.
3. Перепутать порядок в f при удалении. При добавлении сначала растёт cnt, потом f; при удалении сначала уменьшается f, потом cnt.
4. Забыть проверку k <= n. Выход за границу массива.
5. Размерить cnt по n. Цвета могут быть больше количества вершин.
6. Отвечать на запросы не в тот момент. Ответ читается ровно тогда, когда в счётчиках лежит поддерево v — до очистки и после добавления лёгких.
7. Рекурсивный обход. Цепочка из $10^5$ вершин.
8. Класть тяжёлую вершину на стек после лёгких. Тогда она обработается первой, а лёгкие затрут её счётчики своей очисткой.

Сложность

Время: $O(n\log n + m)$ — каждая вершина добавляется не более $\log n$ раз. Память: $O(n)$.

---

Разбор задачи C — «Group Projects»

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

Возьмём первый пример: уровни 1 2 3, порог k = 1. Выпишем все разбиения трёх участников и посчитаем несбалансированность:

Ответ 3. Обратите внимание на строку {1,3} {2}: группа из уровней 1 и 3 стоит два, хотя внутри неё всего два участника. Несбалансированность зависит только от крайних значений, а не от количества.

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

Второе, менее очевидное. Разность «последний минус первый» можно разложить по промежуткам между соседними отсортированными значениями. Пусть отсортированные уровни $a_0 \le a_1 \le \dots \le a_{n-1}$, и $d_i = a_i - a_{i-1}$. Тогда несбалансированность группы — это сумма $d_i$ по всем промежуткам, которые группа «накрывает», то есть промежуткам между её первым и последним участником.

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

Проверим на разбиении {1,2} {3}: промежутков два, оба размера 1. Первый промежуток (между уровнями 1 и 2) накрывает одна группа — {1,2}. Второй (между 2 и 3) — ни одной. Сумма $1 \cdot 1 + 1 \cdot 0 = 1$. Совпадает.

Значит можно идти по отсортированным участникам слева направо и хранить в состоянии, сколько групп сейчас «открыто». Это и есть решение.

Идея решения

Алгоритм в одну фразу: отсортировать уровни и считать динамику dp[j][t] — количество способов разложить первых участников так, чтобы сейчас было j незакрытых групп, а накопленная сумма несбалансированностей равнялась t.

Что такое «незакрытая группа». Группа считается открытой с момента, когда в неё попал первый (то есть наименьший) её участник, и закрытой, когда в неё попал последний (наибольший). Промежуток между соседними участниками накрывается ровно теми группами, которые в этот момент открыты.

Переход. Перед обработкой i-го участника все j открытых групп «переваливают» через промежуток $d_i = a_i - a_{i-1}$, добавляя к сумме $j \cdot d_i$. Дальше у участника четыре возможности:

1. Открыть новую группу и оставить её открытой: одним способом, j увеличивается на единицу.
2. Составить группу из себя одного (открыл и сразу закрыл): одним способом, j не меняется.
3. Войти в одну из j открытых групп, не закрывая её: j способов, j не меняется.
4. Войти в одну из j открытых групп и закрыть её: j способов, j уменьшается на единицу.

Варианты 2 и 3 дают вместе множитель j + 1 при неизменном j — именно так они и записаны в коде.

Ответ. Сумма dp[0][t] по всем t от 0 до k после обработки всех участников: незакрытых групп остаться не должно.

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

Про равные уровни. Если $a_i = a_{i-1}$, то $d_i = 0$, и промежуток ничего не стоит. Порядок среди равных участников фиксируется сортировкой, и двойного счёта это не создаёт: участники различимы, а решения принимаются в фиксированном порядке.

Оценка размера. Состояний $n \cdot k$ на слой, слоёв n, переходов четыре — около $4 \cdot 10^7$ при $n = 200$, $k = 1000$. Ровно то, на что намекают ограничения.

Псевдокод

прочитать n, k, отсортировать a

dp[0][0] = 1                                 // ни одного участника, ноль открытых групп
для i от 0 до n-1:
    d = a[i] - a[i-1], если i > 0, иначе 0
    ndp = нули
    для j от 0 до i:
        доп = j * d                          // все открытые группы переваливают промежуток
        если доп > k: пропустить
        для t от 0 до k - доп:
            val = dp[j][t]
            если val == 0: продолжить
            nt = t + доп
            ndp[j+1][nt] += val              // открыть новую группу
            ndp[j][nt]   += val * (j + 1)    // группа из себя одного либо войти в открытую
            если j > 0:
                ndp[j-1][nt] += val * j      // войти в открытую и закрыть её
    dp = ndp

вывести сумму dp[0][t] по всем t, по модулю 10^9 + 7

Код решения

Комментарии по реализации. Пропуск нулевых состояний (if not val: continue) — не косметика: на реальных входах заполнена лишь малая часть таблицы, и без пропуска решение работает в разы дольше. Проверка add > k отсекает целые строки сразу, не заходя во внутренний цикл. Внутренний цикл ограничен так, чтобы t + add не превышало k — это избавляет от проверки внутри тела. Слои меняются местами, а не копируются: таблица размера $200 \times 1001$ пересоздаётся двести раз, и лишнее копирование было бы заметно.

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

Пример 1: n = 3, k = 1, уровни 1 2 3 (уже отсортированы, оба промежутка равны 1). Проследим по слоям, оставляя только достижимые состояния:

Ручной перебор в разборе выше дал те же 3 разбиения. Наш вывод: 3 — совпадает с ожидаемым.

Пример 2: n = 4, k = 0, уровни 1 1 2 2. Нулевой порог означает, что каждая группа обязана состоять из участников одного уровня. Две единицы можно разложить двумя способами (вместе или порознь), две двойки — тоже двумя, и выборы независимы: $2 \cdot 2 = 4$. Наш вывод: 4 — совпадает с ожидаемым.

Проверим ещё границу:

Ввод:
1 0
7

Вывод:
1

Один участник — единственное разбиение, несбалансированность ноль.

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

• n = 1. Ответ всегда 1 при любом k.
• k = 0. Группы обязаны быть из одинаковых уровней; ответ — произведение чисел Белла по группам равных значений.
• Все уровни равны. Все промежутки нулевые, ограничение не работает вовсе, и ответ — число Белла от n по модулю.
• k заведомо больше максимально возможной суммы. Ответ — снова число Белла от n: подходят все разбиения.
• Максимальные размеры. $n = 200$, $k = 1000$ — таблица из $200 \times 1001$ ячеек и двести слоёв.
• Большой разброс уровней. Промежутки быстро превышают k, и почти все состояния отсекаются — решение работает заметно быстрее худшей оценки.

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

1. Не сортировать уровни. Вся конструкция «промежуток накрывается открытыми группами» опирается на порядок.
2. Считать несбалансированность по всем парам внутри группы. Она определяется только крайними значениями.
3. Забыть вариант «группа из себя одного». Он даёт единицу, которая складывается с j в множитель j + 1; без него теряется целый класс разбиений.
4. Перепутать множители при входе в открытую группу. Войти можно в любую из j, поэтому множитель именно j, а не 1.
5. Прибавлять $j \cdot d$ после решения участника, а не до. Промежуток проходят те группы, которые открыты на подходе к участнику.
6. Считать ответ по всем j, а не только по j = 0. Незакрытые группы означают, что кто-то так и не получил максимума, — такого разбиения не существует.
7. Не брать модуль при умножении. Значение val * j при j до 200 и val до $10^9$ выходит за 32 бита.
8. Обходить все состояния подряд без пропуска нулей. Формально сложность та же, на практике — разница в разы.

Сложность

Время: $O(n^2 k)$ в худшем случае — около $4 \cdot 10^7$ переходов. Память: $O(nk)$ на два слоя.

---

Что дальше

Двадцать три тренировки — от разминки на прямой симуляции до экзамена с задачами CF ~2400. Если пройти маршрут глазами, видно, как менялся не столько список алгоритмов, сколько характер работы.

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

Что делать дальше — без цикла и без расписания:

• Регулярные раунды. Обычные соревнования на Codeforces раз в неделю дают то, чего не даёт никакой разбор: решение под таймером, когда неизвестно, какой приём нужен. Это ровно то, что репетировала сегодняшняя сессия.
• Разбор своих неудач, а не чужих решений. Самое ценное после раунда — не прочитать официальный разбор, а понять, в какой момент своя мысль свернула не туда. Обычно это одно конкретное место: неверно оценил ограничения, не проверил крайний случай, поленился доказать жадность.
• Возврат к отложенным задачам. Если по ходу цикла какая-то задача самостоятельной тренировки осталась нерешённой — сейчас удобный момент. За двадцать три сессии инструментов прибавилось, и часть отложенного решается уже без сопротивления.
• Заготовки. Двоичные подъёмы, система непересекающихся множеств, Дейкстра, слияние от меньшего к большему — стоит держать их написанными и уметь воспроизвести по памяти за несколько минут. На контесте это экономит не код, а внимание.

Цикл на этом закончен. Дальше — обычная практика, свои раунды и свои разборы; и если по ходу застрянешь на задаче, разобрать её можно с AI-партнёром на codepal.ru — он не выдаёт готовое решение, а доводит до него вопросами.