Тренировочная сессия 5: бинарный поиск по ответу и монотонный предикат — первое знакомство СЕССИЯ

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

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

Это одна из самых важных техник во всём алгоритмическом наборе инструментов: она превращает задачи, где неясно, как посчитать ответ напрямую, в задачи вида «есть быстрая проверка — есть и быстрый поиск». Вместо того чтобы придумывать формулу, вы задаёте вопрос «подходит ли значение x?», и если ответ монотонно меняется с ростом x (сначала всегда «да», потом всегда «нет» — или наоборот), можно применять бинарный поиск и получить решение за $O(\log)$ проверок вместо перебора.

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

---

Теория

Бинарный поиск по ответу. Формулы для ответа нет или её сложно вывести, зато легко проверить: «а если ответ равен $x$ — подходит ли это?». Тогда вместо формулы перебираем возможные значения ответа бинарным поиском.

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

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

Как решать:

1. Придумываем проверку ok(x) — «подходит ли значение $x$» (в задаче это называют предикатом — просто «да/нет»-проверкой).
2. Проверяем: как только ok(x) становится «нет», дальше оно остаётся «нет» для всех бо́льших (или меньших) $x$. Такое свойство называют монотонностью — по сути, «более лёгкую цель выполнить не сложнее, чем сложную».
3. Если монотонность есть — ищем границу «да»/«нет» обычным бинарным поиском за $O(\log)$ проверок вместо полного перебора.

Например: если хватило ресурсов на стенку высотой 10, то и на стенку высотой 5 точно хватит — это и есть монотонность, которая делает применённым бинарный поиск.

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

---

Задача 1 — CF ~1100 — «Building an Aquarium»

Что дано

У вас есть коралл из $n$ столбиков, $i$-й столбик имеет высоту $a_i$. Вы строите аквариум: с двух сторон коралла ставите стенки высотой $h \geq 1$, а затем заливаете воду так, чтобы уровень воды над каждым столбиком поднялся до высоты $h$ — если столбик уже выше $h$, вода в этом месте не нужна.

Дано ограничение: воды можно использовать не больше $x$ единиц. Нужно найти максимальную высоту $h$, при которой суммарный расход воды не превышает $x$. Гарантируется, что подходящее $h \geq 1$ всегда существует.

Формат ввода: первая строка — число тестов $t$ ($1 \leq t \leq 10^4$). В каждом тесте: строка с $n$ и $x$ ($1 \leq n \leq 2 \cdot 10^5$; $1 \leq x \leq 10^9$), затем строка с $n$ высотами столбиков $a_i$ ($1 \leq a_i \leq 10^9$). Сумма $n$ по всем тестам не превышает $2 \cdot 10^5$.

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

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

Первый пример: $a = [3, 1, 2, 4, 6, 2, 5]$, $x = 9$.

Попробуем $h = 4$. Для каждого столбика считаем, сколько воды нужно долить, если столбик ниже 4:

Сумма: $1+3+2+0+0+2+0 = 8 \leq 9$ — подходит.

Попробуем $h = 5$: доливка $2+4+3+1+0+3+0 = 13 > 9$ — не подходит.

Значит, ответ — $h = 4$: это максимальная высота, при которой воды хватает. Обратите внимание: мы даже не пытались вывести формулу «сколько столбиков ниже какого уровня» — просто попробовали конкретное значение и посчитали, хватает ли воды.

Идея решения

Алгоритм в одну фразу: бинарным поиском ищем максимальное $h$, при котором функция water(h) (суммарный расход воды на высоту $h$) не превышает $x$.

Формально: $\text{water}(h) = \sum_i \max(h - a_i,\ 0)$.

Почему это работает — монотонность. Присмотримся к каждому слагаемому $\max(h - a_i, 0)$ отдельно. Когда $h$ увеличивается на 1, это слагаемое либо остаётся тем же (если столбик всё ещё выше $h$), либо тоже увеличивается на 1 — но никогда не уменьшается. Значит, и вся сумма water(h) не убывает при росте $h$.

Из этого прямо следует главное свойство, которое нужно бинарному поиску: предикат «water(h) ≤ x» истинен для маленьких $h$ (близко к 1 воды почти не нужно) и, начиная с некоторого порога, становится ложным — и уже никогда не станет истинным снова, потому что расход воды с ростом $h$ может только расти. Ряд ответов выглядит как истина, истина, ..., истина, ложь, ложь, ..., ложь — классическая форма для бинарного поиска по ответу: мы ищем именно точку излома.

Заметьте: при уменьшении цели требование ослабляется — если для высоты $h$ воды хватило, то для любой меньшей высоты $h' < h$ воды точно хватит ещё с запасом (каждому столбику нужно долить не больше, чем для $h$). Эта же логика — «меньшая цель требует не больше ресурса» — будет ключевой идеей и во второй задаче сегодня, просто в другой одежде.

Псевдокод

прочитать n, x, массив a[1..n]
maxA = максимум по a

лог lo = 1, hi = maxA + x   // верхняя граница: если бы все столбики были высоты maxA,
                             // на прирост от maxA хватило бы ровно x
ans = 1
пока lo <= hi:
    mid = (lo + hi) / 2
    water = 0
    для каждого a_i в a:
        если a_i < mid:
            water += mid - a_i
    если water <= x:
        ans = mid       // mid подходит — пробуем больше
        lo = mid + 1
    иначе:
        hi = mid - 1     // mid не подходит — пробуем меньше
вывести ans

Обоснование верхней границы hi = maxA + x: если бы существовал только один столбик и он был высоты maxA, то долив x воды поднял бы его ровно на maxA + x. Для нескольких столбиков ответ не может быть выше этого значения (воды физически не хватит на большее для самого высокого столбика).

Код решения

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

Официальные примеры задачи — все 5 тестов:

Второй пример проверим руками: все столбики высоты 1, $h=4$ → доливка $3 \times (4-1) = 9 \leq 10$; $h=5$ → $3 \times 4 = 12 > 10$. Ответ 4 — сходится.

Пятый пример — крайний случай с одним столбиком: доливка равна $h - 1 \leq x = 10^9$, откуда максимальное $h = 10^9 + 1$ — то есть верхняя граница maxA + x достигается ровно, без запаса.

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

• $n = 1$. Формула вырождается в одно слагаемое — важно, чтобы код не спотыкался на массиве из одного элемента (пример 5 выше).
• Все столбики одинаковой высоты. Расход воды считается синхронно для всех — проверяйте, что цикл суммирования не завязан на порядок сортировки (сортировка тут вообще не нужна).
• Ответ упирается ровно в верхнюю границу maxA + x. Если binary search стартует с недостаточно большого hi, правильный ответ может быть отрезан — использовать именно maxA + x, а не произвольную константу вроде $2 \cdot 10^9$ «на глаз» (хотя с long long такая константа тоже сработает, maxA + x — точнее и говорит явно, откуда взялась граница).
• $x = 1$ (минимальный бюджет воды). Ответ может быть равен просто maxA или чуть выше — проверьте, что предикат для h = maxA (доливка 0) всегда истинен.

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

1. int вместо long long. Сумма воды может достигать $n \cdot h \sim 2 \cdot 10^5 \cdot 2 \cdot 10^9 \approx 4 \cdot 10^{14}$ — это далеко за пределами 32-битного int (макс. $\approx 2.1 \cdot 10^9$). Верхняя граница hi = maxA + x тоже может достигать $2 \cdot 10^9$ — на грани переполнения int, использовать long long везде, а не только для суммы.
2. Неверная граница бинарного поиска. Если использовать hi = maxA (забыть добавить x), ответы вроде примера 5 ($10^9 + 1$) будут обрезаны — граница поиска должна учитывать весь доступный запас воды.
3. while lo < hi вместо while lo <= hi — с другой схемой обновления границ теряется последний кандидат; в шаблоне выше используется вариант «сохраняем лучший ответ и двигаем границу», где lo <= hi обязательно.
4. Пересчёт water_needed без needed оптимизации на больших n. Каждый вызов предиката — $O(n)$, и с бинарным поиском это $O(n \log(\text{maxA}+x))$ — для данных ограничений укладывается с запасом, но если по невнимательности сделать сортировку внутри предиката на каждой итерации — тайм-лимит превысится.

Сложность

Время: $O(n \log(\text{maxA} + x))$ на тест (примерно 30 итераций бинарного поиска, каждая — проход по массиву). Память: $O(n)$ на хранение массива.

---

Задача 2 — CF ~1100 — «Two Teams Composing»

Что дано

У вас есть $n$ участников, у каждого есть навык $a_i$ ($1 \leq a_i \leq n$, значения могут повторяться). Нужно собрать две команды одинакового размера $x$:

• в первой команде все навыки должны быть различны;
• во второй команде все навыки должны быть одинаковы (все члены — с одним и тем же значением навыка).

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

Формат ввода: первая строка — число тестов $t$ ($1 \leq t \leq 10^4$). В каждом тесте: строка с $n$ ($1 \leq n \leq 2 \cdot 10^5$), затем строка с $n$ значениями навыков $a_i$ ($1 \leq a_i \leq n$). Сумма $n$ по тестам — не более $2 \cdot 10^5$.

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

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

Первый пример: $n = 7$, навыки $[4, 2, 4, 1, 4, 3, 4]$.

Различных значений навыка — четыре: $\{1, 2, 3, 4\}$. Навык 4 встречается чаще всех — четыре раза.

Попробуем $x = 3$: вторая команда — три участника с навыком 4 (осталось ещё одно значение 4 про запас). Первая команда — три участника с разными навыками из оставшегося пула $\{1, 2, 3, 4\}$, например $[1, 2, 4]$ (используя тот самый «запасной» экземпляр 4). Обе команды по 3 человека, ограничения выполнены — подходит.

Попробуем $x = 4$: вторая команда заберёт все четыре экземпляра навыка 4 — тогда в пуле для первой команды навык 4 больше не доступен, остаются только $\{1, 2, 3\}$ — это лишь 3 различных значения, а нужно 4. Не подходит.

Ответ — 3.

Идея решения

Алгоритм в одну фразу: предпосчитаем количество различных навыков $d$ и максимальную частоту одного навыка $f$, а дальше бинарным поиском найдём максимальный размер команды $x$, для которого проверка canBuild(x) истинна.

Проверка canBuild(x):

1. Нужно хотя бы $x$ экземпляров одного навыка для второй команды — то есть $f \geq x$.
2. После того как вторая команда «съела» $x$ экземпляров самого частого навыка, для первой команды остаётся пул различных навыков. Если $x$ строго меньше $f$ — хотя бы один экземпляр самого частого навыка остаётся неиспользованным, и он всё ещё доступен первой команде как одно из различных значений: пул равен $d$. Но если $x$ равно $f$ — вторая команда забирает все экземпляры целиком, и первая команда больше не может использовать это значение вовсе: пул уменьшается до $d - 1$.
3. Проверка: пул $\geq x$.

Почему canBuild(x) монотонна. Здесь самое красивое рассуждение во всей сессии: если пара команд размера $x$ существует, то пара команд размера $x - 1$ существует всегда — просто уберите по одному произвольному участнику из каждой команды. Первая команда останется с различными навыками (удаление элемента не портит различность), вторая — с одинаковыми (удаление элемента не портит одинаковость), а размеры команд по-прежнему равны. Это общий приём для любой задачи вида «можно ли упаковать что-то размера $x$»: если упаковка размера $x$ существует, отбросив лишнее, получаем упаковку любого меньшего размера. Значит ответы снова идут «истина, истина, ..., истина, ложь, ложь, ...» по мере роста $x$ — и снова можно применять бинарный поиск.

Заметьте параллель с задачей 1: там тоже работал принцип «меньшая цель — не больше ресурса нужно», только там ресурс был непрерывным (вода), а здесь дискретным (участники). Форма рассуждения — одна и та же.

Псевдокод

прочитать n, массив a[1..n]        // 1 <= a_i <= n

freq[1..n] = 0
для каждого a_i:
    freq[a_i] += 1

distinct = количество v, у которых freq[v] > 0
maxFreq = максимум по freq

функция canBuild(x):
    если maxFreq < x:
        вернуть ложь
    pool = distinct
    если maxFreq == x:
        pool = pool - 1        // самый частый навык полностью ушёл во вторую команду
    вернуть pool >= x

lo = 0, hi = maxFreq, ans = 0
пока lo <= hi:
    mid = (lo + hi) / 2
    если canBuild(mid):
        ans = mid
        lo = mid + 1
    иначе:
        hi = mid - 1
вывести ans

Код решения

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

Все 4 официальных примера:

Разберём третью строку руками: единственный участник, $d=1$, $f=1$. canBuild(1): maxFreq >= 1 — истина, но pool = 1 - 1 = 0 (потому что maxFreq == x), а нужно pool >= 1 — ложь. canBuild(0) — истина тривиально (пустые команды всегда допустимы). Ответ 0 — единственного участника не хватает даже на команды по одному человеку с двух разных ролей одновременно.

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

• $n = 1$. Ни на одну полноценную пару команд размера ≥ 1 ресурсов не хватает — ответ всегда 0 (см. пример 3 выше).
• Все навыки одинаковые ($d = 1$, $f = n$). Вторая команда может забрать почти всех, но первой команде тогда не хватит различных значений — ответ обычно 1 (если $n \geq 2$: команда первая — один экземпляр навыка, команда вторая — ещё один экземпляр того же навыка) либо 0 (если $n = 1$).
• Все навыки различны ($f = 1$). Вторая команда не может быть больше 1 человека — ответ либо 1 (если $n \geq 2$), либо 0 (если $n = 1$).
• maxFreq == x на границе поиска. Это самый частый источник ошибок (см. ниже) — обязательно проверяйте отдельно ветку, где самый частый навык используется вторым составом целиком.

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

1. Забыть вычесть 1 из пула, когда maxFreq == x. Самая коварная ошибка в этой задаче: если считать пул просто как distinct без поправки, ответ окажется завышен на единицу именно в пограничном случае (когда вторая команда выбирает ровно столько экземпляров, сколько всего есть у самого частого навыка).
2. Границы бинарного поиска lo = 1 вместо lo = 0. Ответ 0 — валидный результат (пустая пара команд), пропускать его нельзя, иначе для вырожденных тестов (например, $n=1$) код даст неверный результат или зациклится.
3. Размер freq-массива меньше n + 1. Так как $a_i \leq n$ по условию, массив частот должен быть размера хотя бы n + 1, а не max(a) + 1 — иначе можно случайно выйти за границы, если полагаться на «наблюдаемый максимум», а не на формальное ограничение задачи.
4. Путаница, какое значение брать за «самое частое». Работает только максимум частоты — если по ошибке взять сумму двух наибольших частот или считать по количеству различных «частых» значений, монотонность предиката ломается и бинарный поиск даёт неверный ответ.

Сложность

Время: $O(n)$ на подсчёт частот и минимума/максимума на тест, плюс $O(\log f)$ итераций бинарного поиска с $O(1)$ проверкой каждая — итоговое время доминируется линейным подсчётом, $O(n)$. Память: $O(n)$ на массив частот.

---

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

• Codeforces 1832B «Maximum Sum» (~CF 1100) — дан массив различных чисел, нужно выполнить ровно $k$ операций (каждая — либо удалить два минимальных элемента, либо удалить один максимальный) так, чтобы сумма оставшихся элементов была максимальной.
• Codeforces 1899C «Yarik and Array» (~CF 1100) — найти подотрезок массива с максимальной суммой при условии, что соседние элементы подотрезка должны чередоваться по чётности.
• Codeforces 258A «Little Elephant and Bits» (~CF 1100) — дано число в двоичной записи; нужно удалить ровно одну цифру так, чтобы получившееся число было максимально возможным.
• Codeforces 68A «Irrational problem» (~CF 1100) — по четырём числам-модулям и диапазону $[a, b]$ найти, сколько чисел $x$ в диапазоне удовлетворяют условию с достаточно высокой вероятностью по всем порядкам взятия остатка.

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

---

Что дальше

На следующей тренировке поднимаем сложность до ~CF 1200 и меняем ракурс: увидим, как отсортированный массив вместе с префиксными суммами превращает похожую на сегодняшнюю задачу в прямую формулу без единого бинарного поиска.