Бинарный поиск по ответу

Есть $n$ верёвок, каждую можно резать на куски целой длины. Нужно получить $k$ кусков одинаковой длины — какой наибольшей?

Здесь нечего искать: списка ответов не существует. Зато есть кое-что не хуже — проверка. Для конкретной длины $L$ легко сказать, годится ли она:

def enough(L):
    return sum(a_i // L for a_i in a) >= k

Один проход, $O(n)$ действий. Перебрать все длины от 1 до $10^9$ мы не можем — это миллиард проходов. Но посмотрим, как выглядят ответы проверки, если выписать их подряд:

L:        1    2    3    4    5    6    7    8
enough:  да   да   да   да   нет  нет  нет  нет

Это тот же упорядоченный массив, что и на прошлом занятии. Только он виртуальный: мы его не храним, а вычисляем любой элемент по требованию за $O(n)$. И искать в нём границу между «да» и «нет» можно ровно тем же делением пополам.

Получается $O(n \log C)$, где $C$ — размах возможных ответов. Для $n = 2 \cdot 10^5$ и $C = 10^9$ это примерно шесть миллионов действий вместо двухсот триллионов.

Приём работает не всегда, и условие применимости одно.

Проверка должна быть монотонной. То есть массив её ответов должен выглядеть как да да да нет нет нет или как нет нет нет да да да, но не как да нет да нет.

Проверить это можно вопросом к себе: «если ответ $x$ годится, годится ли $x - 1$?» (или $x + 1$ — смотря в какую сторону). Если да — приём применим. Если ответ «когда как» — нет.

Где монотонность есть

Где её нет

Вопрос «существует ли кусок с суммой ровно $x$» немонотонен: сумма 10 может быть достижима, 11 — нет, 12 — снова да. Делить отрезок пополам тут бессмысленно: ответ «нет» в середине ничего не говорит о половинах.

Немонотонна и такая формулировка: «при каком $x$ значение $f(x)$ наибольшее», если $f$ сначала растёт, потом убывает. Это другая задача — и другой приём.

Так что первым делом формулируйте проверку и убеждайтесь в её монотонности. Всё остальное — техника.

Решение почти всегда собирается из одних и тех же четырёх шагов.

1. Переформулировать вопрос. Было: «найдите наименьшее $x$, при котором…». Стало: «умею ли я для данного $x$ ответить да или нет?».

2. Написать проверку. Обычно это простой проход за $O(n)$ — посчитать сумму, набрать жадно, сложить количества.

3. Убедиться в монотонности. Вслух, одним предложением.

4. Выбрать границы и поискать. Границы берутся заведомо верными, с запасом.

left = 0                 # заведомо "да"
right = 10 ** 9 + 1      # заведомо "нет"

while right - left > 1:
    mid = (left + right) // 2
    if enough(mid):
        left = mid
    else:
        right = mid

print(left)              # наибольшее подходящее

Это тот же инвариант, что и на прошлом занятии: left — заведомо годится, right — заведомо нет. Разница только в том, что вместо a[mid] < x стоит вызов проверки.

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

Какой из вопросов можно решать бинарным поиском по ответу?

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

Ищем наибольшее подходящее

Проверка выглядит как да да да нет нет. Границы: left — заведомо да, right — заведомо нет. Ответ — left.

if enough(mid):
    left = mid
else:
    right = mid
print(left)

Ищем наименьшее подходящее

Проверка выглядит как нет нет да да да. Границы: left — заведомо нет, right — заведомо да. Ответ — right.

if enough(mid):
    right = mid
else:
    left = mid
print(right)

Различие в двух местах: куда идёт mid при успешной проверке и какую границу печатать. Если помнить инвариант — «left заведомо одно, right заведомо другое», — перепутать нельзя: печатаем ту границу, которая заведомо годится.

Про запас в границах

Границу берут не «примерно достаточной», а точно верной. Несколько лишних шагов ничего не стоят — логарифм растёт медленно, — а недостаточная граница ломает ответ.

Типичный промах: в задаче «поднять минимум, раздав $k$ единиц» правой границей взяли $\max(a)$. Но если $k$ велико, ответ спокойно окажется больше любого элемента.

В стопках 3, 6, 7 и 11 документов. За час берут одну стопку и обрабатывают из неё не больше $v$ документов; неполный час считается за целый.

Сколько часов уйдёт при $v = 4$? Введите целое число.

Иногда ответ — не целое число, а длина, скорость или среднее. Схема та же, но с двумя оговорками.

Не пишите while right - left > eps. Такой цикл может не закончиться: когда числа большие, а eps маленький, разность границ перестаёт уменьшаться из-за ограниченной точности вещественных чисел, и программа зависает.

Вместо этого делайте фиксированное число шагов:

left = 0.0
right = 1000.0

for _ in range(100):
    mid = (left + right) / 2
    if enough(mid):
        left = mid
    else:
        right = mid

print("%.9f" % left)

Сколько шагов нужно? Каждый шаг уменьшает отрезок вдвое. Чтобы из отрезка длины $10^9$ получить точность $10^{-6}$, нужно $\log_2(10^{15}) \approx 50$ шагов. Сто шагов — с большим запасом и всё равно мгновенно.

Выводите с запасом знаков. Если требуется точность $10^{-6}$, печатайте девять знаков после точки: "%.9f" % x. Округление до шести знаков само по себе съедает часть точности.

И помните про границы. В задаче «найти $x$, для которого $x^3 = c$» при $c = 0.001$ ответ равен $0.1$ — он больше самого $c$. Отрезок $[0, c]$ здесь не годится.

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

Печатается не та граница. Искали минимум, а вывели left. Ответ стабильно отличается на единицу — и это заметно только на тестах, где проверка меняется резко.

Проверка немонотонна. Приём применили там, где он не работает. Ответы получаются «почти правильными» и разными на похожих тестах.

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

Проверка считает слишком много. В задачах, где складывают x - a_i, сумма может стать астрономической, хотя ответ давно ясен. Выходите из цикла досрочно, как только стало понятно «нет».

Как проверять себя

• параметр минимально возможный и максимально возможный;
• список из одного элемента;
• случай, когда ответа не существует;
• случай, когда ответ равен границе отрезка.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

В каждой задаче начинайте одинаково: сформулируйте проверку одним предложением и скажите вслух, почему она монотонна. Код после этого пишется почти сам.

Две задачи — вещественные. В них считайте фиксированное число шагов и выводите девять знаков после точки.

Задача: «есть $n$ верёвок с целыми длинами; нужно получить $k$ кусков одинаковой целой длины; найдите наибольшую такую длину». Гарантируется, что длина 1 всегда подходит.

Ученик написал:

n, k = map(int, input().split())
a = list(map(int, input().split()))

def enough(length):
    return sum(value // length for value in a) >= k

left = 1
right = max(a)
while left < right:
    mid = (left + right) // 2
    if enough(mid):
        left = mid
    else:
        right = mid - 1

print(left)

Проверка написана правильно, и на маленьких примерах программа отвечает верно. Но на некоторых тестах она не выводит ничего и работает до самого конца отведённого времени.

Объясните, что происходит, приведите конкретное состояние границ, при котором это случается, и скажите, как исправить.