Занятие 2. Параллель B' — Поиски

1. Бинарный поиск по отсортированному массиву 0:09

Задача. Есть массив, отсортированный по возрастанию. Нужно найти в нём число $x$.

Наивно — цикл по всему массиву (или std::ranges::find) — работает за $O(n)$. Но массив отсортирован, этим можно воспользоваться.

Идея. Посмотрим на средний элемент. Если он меньше $x$, то всё, что левее, тоже меньше $x$ — левую половину можно отбросить. Иначе отбрасываем правую. Каждый шаг уменьшает отрезок вдвое, поэтому число шагов $O(\log n)$.

Интерактив: ползунок или ▶ — шаги бинпоиска. L зелёный, R оранжевый, mid жёлтый.

2. Инвариант — сердце бинпоиска 4:56

Чтобы писать бинпоиск всегда без ошибок, нужно держать в голове инвариант — свойство, которое выполняется на каждом шаге. Без него придётся «угадывать» границы, и это источник вечных off-by-one ошибок.

Для поиска $x$ в отсортированном массиве удобен такой инвариант:

Считаем, что $x$ гарантированно есть в массиве. На каждом шаге берём $mid = \lfloor (L+R)/2 \rfloor$ и смотрим на $a[mid]$:

• если $a[mid] \le x$ — двигаем левую границу: $L = mid$ (ответ где-то в $[mid, R)$);
• иначе $a[mid] > x$ — двигаем правую: $R = mid$.

Останавливаемся, когда $R - L = 1$. В этот момент $L$ и указывает на ответ.

// поиск x в отсортированном массиве a (x гарантированно есть)
int L = 0, R = n;                 // полуинтервал [0, n)
while (R - L > 1) {
    int mid = (L + R) / 2;
    if (a[mid] <= x) L = mid;      // ответ не левее mid
    else             R = mid;      // ответ строго левее mid
}
// теперь a[L] == x

Почему границы именно $0$ и $n$ 10:34

• После работы алгоритма в L лежит ответ, а R = L + 1.
• Значит, $L$ может принять любое значение от $0$ до $n-1$ — если начать с $0$ и $n$, можно «обнаружить» любой элемент.
• Если взять $L=-1$ или $R=n+1$, пришлось бы следить за выходом за границы массива при обращении $a[mid]$.

Что происходит на самом деле: мы нашли самый правый $x$ 15:43

Наш инвариант $a[L]\le x < a[R]$ на самом деле держит $L$ на последнем (самом правом) вхождении $x$, а $R$ — сразу после него. Если $x$ нет в массиве, $L$ укажет на самый правый элемент, меньший $x$, а $R$ — на самый левый, больший $x$.

3. Разновидности: левая и правая границы, подсчёт 19:28

Если в условии вместо a[mid] <= x написать a[mid] < x, инвариант сменится на $a[L] < x \le a[R]$, и по итогу:

• $L$ укажет на самый правый элемент строго меньший $x$;
• $R$ укажет на самый левый элемент $\ge x$ (то есть первое вхождение $x$).

То есть, меняя только знак сравнения, мы получаем либо левую, либо правую границу блока равных элементов.

Подсчёт количества вхождений $x$ 22:19

Чтобы посчитать, сколько раз встречается $x$ в отсортированном массиве, найдём два индекса:

Это разность двух бинпоисков. В терминах C++ — upper_bound(x) - lower_bound(x).

4. Бинпоиск по монотонному предикату, а не по сортировке (интерактив) 24:34

Задача 1: найти первую единицу 24:34

Массив размера $10^9$ нельзя ввести целиком. Но можно за одно действие спрашивать у жюри любой элемент. Гарантируется, что массив выглядит как «сначала нули, потом единицы». Дано $30$ запросов.

Так как $\log_2 10^9 \approx 30$, решаем обычным бинпоиском, только вместо чтения $a[mid]$ спрашиваем жюри.

Задача 2: массив не отсортирован 26:05

Теперь сортированность не гарантируется. Вместо неё даны три гарантии (1-индексация):

1. каждый элемент равен либо $0$, либо $1$;
2. $a_1 = 0$;
3. $a_n = 1$.

Нужно найти любое $i$, такое что $a_i = 0$ и $a_{i+1} = 1$.

Решение. Инвариант: $a_L = 0$ и $a_R = 1$. Берём середину:

• если $a_{mid} = 0$ — двигаем $L = mid$;
• если $a_{mid} = 1$ — двигаем $R = mid$.

Каждый шаг отрезок делится пополам, и за $\log n \le 30$ шагов сходимся к двум соседним элементам $0$ и $1$.

33:46 Если же гарантий нет (просто «в массиве есть $0$ и $1$»), то по случайному массиву за логарифм найти пару $0\,1$ нельзя: глядя на ноль, вы не знаете, куда двигать границу — единичка может быть и слева, и справа. Такая постановка решается только за линейное время.

5. Функции C++: binary_search, lower_bound, upper_bound 34:45

Все эти функции лежат в <algorithm> и работают на отсортированном диапазоне за $O(\log n)$.

Если lower_bound/upper_bound ничего не нашли, они возвращают второй переданный аргумент (обычно end).

Подсчёт вхождений и «правый строго меньший»

// количество элементов, равных x:
int cnt = upper_bound(a.begin(), a.end(), x) - lower_bound(a.begin(), a.end(), x);

// самый правый элемент, строго меньший x:
auto it = lower_bound(a.begin(), a.end(), x);
if (it == a.begin()) { /* все >= x */ }
else { --it; /* *it — правый строго меньший x */ }

Опасность: lower_bound по set/map 40:40

Для set/map/multiset/multimap нужно использовать метод контейнера:

auto it = s.lower_bound(x);   // O(log n) — правильно!
// а НЕ: std::lower_bound(s.begin(), s.end(), x)  → O(n)

Причина — категории итераторов: у vector итератор random access (можно прыгать на произвольную позицию), а у set — bidirectional (только на единичку).

6. Бинпоиск по ответу 49:20

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

Идея: множество возможных ответов разбивается на две части — «не подходит» и «подходит» (монотонность). Мы ищем границу между ними.

Схема решения:

Сложность: $O(\log(\text{диапазон}) \cdot T_\text{checker})$.

6.1. Задача про дипломы 52:13

Условие. Есть $n$ одинаковых дипломов размером $w \times h$ (переворачивать нельзя). Нужно найти минимальную сторону $a$ квадратной доски, на которую поместятся все $n$ дипломов.

Границы. Если взять $a = n \cdot \max(w, h)$ — заведомо хватит (положить все в ряд). Значит, берём $L$ — слишком маленький, $R = n \cdot \max(w,h)$ — точно хватит.

Чекер. На доску $a\times a$ в ряд по горизонтали помещается $\lfloor a / w \rfloor$ дипломов, по вертикали $\lfloor a / h \rfloor$. Итого мест:

// чекер: можно ли разместить n дипломов w×h на доске a×a
bool check(long long a, long long w, long long h, long long n) {
    return (a / w) * (a / h) >= n;   // осторожно с переполнением!
}

// бинпоиск по ответу
long long L = 0, R = n * max(w, h);  // L — не хватает, R — хватает
while (R - L > 1) {
    long long M = L + (R - L) / 2;
    if (check(M, w, h, n)) R = M;
    else                   L = M;
}
cout << R;   // минимальная сторона

Вычисление середины без переполнения 54:50

Способ (L + R) / 2 опасен: если $L+R$ выходит за диапазон типа (например, два числа порядка $2\cdot10^9$ в int), произойдёт переполнение. Безопаснее:

6.2. Задача про лесорубов 1:02:40

Условие. Два лесоруба рубят $n$ деревьев. Первый рубит $a$ деревьев в день, но каждый $k$-й день отдыхает. Второй рубит $b$ деревьев в день, но каждый $m$-й день отдыхает. Найти минимальное число дней $d$, за которое будет срублено $\ge n$ деревьев.

Чекер. За $d$ дней первый срубит $a \cdot (d - d/k)$ (вычитаем дни отдыха), второй — $b \cdot (d - d/m)$:

Границы: за $0$ дней не успеют; в качестве $R$ можно взять большое число (например, $10^{18}$, но аккуратно с переполнением).

bool check(long long d, long long a, long long k, long long b, long long m, long long n) {
    long long p = a * (d - d / k) + b * (d - d / m);
    return p >= n;   // возможны промежуточные переполнения — см. §9
}

6.3. Задача про коров (стойла) 1:08:14

Условие. На прямой есть $n$ стойл в координатах $a_1 < a_2 < \dots < a_n$. Нужно расставить $m$ коров по стойлам так, чтобы максимизировать минимальное расстояние между соседними коровами.

Бинпоиск по ответу $D$ — «можно ли расставить $m$ коров с расстоянием хотя бы $D$».

Чекер (жадно). Ставим первую корову в первое стойло. Дальше идём по стойлам и ставим корову в очередное стойло, если расстояние от последней поставленной коровы хотя бы $D$. Если в итоге поставили $\ge m$ коров — $D$ подходит.

// можно ли расставить m коров с минимальным расстоянием >= D
bool check(vector<long long>& a, long long D, int m) {
    int placed = 1;
    long long last = a[0];
    for (int i = 1; i < a.size(); ++i)
        if (a[i] - last >= D) { placed++; last = a[i]; }
    return placed >= m;
}

Сложность: $O(\log A \cdot n)$, где $A$ — диапазон координат.

7. Вещественные числа и точность 1:18:08

Вещественные числа хранятся по стандарту IEEE 754. Тип double занимает $64$ бита:

Число представляется как $(\pm)\ \text{мантисса} \times 2^{\text{экспонента}}$. Главное следствие: не все числа можно представить точно.

• $\tfrac12 = 0.5$ в двоичной системе представимо точно.
• $0.1$ в двоичной записи — бесконечная периодическая дробь, её обрезают, поэтому хранится приближённо.

Правило: float (32 бита) почти не нужен, double хватает для точности ~15 значащих цифр; если нужна большая точность — long double (80 бит). По умолчанию пишите double.

Сравнение с эпсилон 1:25:41

Из-за погрешности сравнивать вещественные числа на равенство нельзя. Вместо a == b:

bool eq(double x, double y) {
    return fabs(x - y) < 1e-9;
}

8. Бинпоиск по вещественным числам 1:28:20

8.1. Ноль кубической функции

Нужно найти любой ноль функции $f(x) = x^3 + bx^2 + cx + d$ при $a > 0$. Инвариант: $f(L) < 0$, $f(R) > 0$. Так как при $x\to-\infty$ значение $f\to-\infty$, а при $x\to+\infty$ значение $f\to+\infty$, такие границы существуют. Берём середину и двигаем границу, сохраняя знаки:

double L = /* точка, где f  0 */;
for (int it = 0; it < 200; ++it) {   // фиксированное число итераций
    double M = (L + R) / 2;
    if (f(M) < 0) L = M;
    else          R = M;
}
// ответ: L (или R) — корень с точностью ~ (R0-L0)/2^200

Вместо условия остановки «пока $R-L$ большое» используют фиксированное число итераций: каждая итерация делит отрезок пополам, поэтому:

Например, если начальный отрезок длины $\sim 10^{18}$ и нужно получить точность $10^{-9}$, достаточно $\log_2(10^{27}) \approx 90$ итераций; обычно пишут $200$ и не считают.

8.2. Квадратный корень 1:39:37

Найти $\sqrt{2}$ с заданной точностью. Функция $f(x) = x^2 - 2$, ищем ноль на отрезке $[0, 2]$ (где $f(0) = -2 < 0$, $f(2) = 2 > 0$). Тот же вещественный бинпоиск.

Вывод вещественных чисел 1:40:55

#include <iomanip>
cout << fixed << setprecision(9) << x;   // 9 знаков после запятой

9. Переполнение, __int128 и «голопинг» 1:43:12

9.1. __int128 1:44:55

В чекере лесорубов (и подобных) промежуточные значения типа $a \cdot d$ могут выйти за пределы long long ($\approx 9\cdot10^{18}$). Для промежуточных вычислений можно использовать __int128:

__int128 p = (__int128)a * (d - d / k) + (__int128)b * (d - d / m);
if (p >= n) ...

Ограничение: __int128 нельзя напрямую вводить (cin) и выводить (cout) — для этого его нужно вручную преобразовывать в long long. Но для промежуточных вычислений он годится.

9.2. «Голопинг» — экспоненциальный поиск границы 1:47:00

Если вы не знаете, какую верхнюю границу $R$ взять для бинпоиска по ответу, используйте голопинг (удвоение):

long long R = 1;
while (!check(R)) R *= 2;   // удваиваем, пока не найдём «хорошую» границу

Это работает за тот же логарифм: найденный $R$ не более чем в $2$ раза больше минимально нужного. После этого запускаем обычный бинпоиск на $[R/2, R]$.

10. Бинпоиск по производной и тернарный поиск 1:50:30

10.1. Унимодальная функция и бинпоиск по производной

Есть массив, который сначала строго возрастает, а потом строго убывает (одна «вершина»). Нужно найти пик. Такая функция называется унимодальной (имеет ровно один максимум или минимум).

Идея. Рассмотрим разности соседних элементов $a_i - a_{i+1}$: до пика они отрицательны, после пика — положительны. Это снова «0...0 1...1»-подобная структура, только на знаке производной. Инвариант: $a_L < a_{L+1}$ (мы в возрастающей части) и $a_R > a_{R+1}$ (в убывающей); для этого считаем $a_{-1}=a_n=-\infty$ и начинаем с $L=-1$, $R=n-1$. Когда $R-L=1$, пик стоит в $R$.

int L = -1, R = n - 1;                // a[-1] = a[n] = -∞ (виртуальные)
while (R - L > 1) {
    int M = (L + R) / 2;
    if (a[M] < a[M + 1]) L = M;   // мы слева от пика — идём вправо
    else                  R = M;   // мы на пике или справа — идём влево
}
// R — индекс пика

10.2. Тернарный поиск 1:55:44

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

Пусть ищем максимум. Берём две точки $m_1 < m_2$ внутри $[L, R]$. Если $f(m_1) < f(m_2)$ — максимум точно не в $[L, m_1]$, двигаем $L = m_1$. Иначе максимум не в $[m_2, R]$, двигаем $R = m_2$.

Чтобы отрезок уменьшался равномерно, точки берут на расстоянии трети:

// тернарный поиск максимума унимодальной функции f на вещественном отрезке
double L = ..., R = ...;
for (int it = 0; it < 200; ++it) {
    double m1 = L + (R - L) / 3;
    double m2 = R - (R - L) / 3;
    if (f(m1) < f(m2)) L = m1;
    else               R = m2;
}

Сложность. Каждый шаг отрезок уменьшается в $2/3$ раза, поэтому число итераций $\approx \log_{3/2}\!\left(\frac{R-L}{\varepsilon}\right)$. Это хуже, чем у бинпоиска по производной (там основание $2$), но тернарный поиск «позволяет меньше думать».

10.3. Унимодальность и выпуклость 2:06:36

• Выпуклая функция (график «чашечкой») унимодальна; сумма выпуклых функций тоже выпукла и унимодальна.
• Сумма модулей $\sum |x - a_i|$ — выпуклая функция (график из ломаных), у неё есть минимум, и его можно искать тернарником.
• Если функция не унимодальна (несколько «горбов»), никакие пробы точек не подскажут, куда двигаться — тернарный поиск не сработает.

10.4. Пример: сумма парабол 2:08:13

Нужно найти $x$, минимизирующий $\displaystyle\sum_{j} (i_j - x)^2 \cdot a_{i_j}$ для фиксированных $a_i > 0$. Каждое слагаемое — парабола ветвями вверх; сумма парабол — тоже парабола ветвями вверх, то есть выпуклая и унимодальная. Значит, можно применить тернарный поиск.

// подсчёт значения функции при заданном x (O(n))
double f(double x, vector<double>& a, vector<int>& idx) {
    double s = 0;
    for (int j = 0; j < idx.size(); ++j) {
        double d = idx[j] - x;
        s += d * d * a[idx[j]];
    }
    return s;
}
// дальше — тернарный поиск минимума (меняется только сравнение f(m1) > f(m2))

11. Разбор контеста 2:15:44

После перерыва разбирался контест. Здесь перечислены задачи и ключевые идеи.

Задача A. Сортировка вагонов (тупик) 2:18:55

Вагоны заезжают в тупик (стек) и выезжают из него. Нужно получить на выходе последовательность $1, 2, \dots, n$.

Идея. Симуляция стека. Пока не встретили вагон с нужным номером — отправляем вагоны в тупик. Когда нужный вагон сверху — выводим. Если последовательность закончилась, а стек не пуст — невозможно.

Задача B. Рыбки (аквариумы) 2:22:03

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

Идея. В set кладём события «рождение ближайшей рыбки». Достаём самое раннее, проверяем, успеваете ли дойти по времени (разница времён $\ge$ разница позиций). Не успели — стоп; успели — кладём следующее событие и обновляем позицию.

Задача C. Множества 2:24:21

Поддерживаем несколько множеств чисел; операции: добавить элемент, удалить, вывести множество. Для каждого числа храним, в каких множествах оно лежит (и наоборот). Всё на set/map.

Задача D. Рецепты 2:26:24

Есть рецепты блюд и запас ингредиентов. При «приготовить блюдо» — проверить, хватает ли каждого ингредиента; если хватает — вычесть. Классическая работа с map<ингредиент, количество>.

Задача E. Автобус (сидячие/стоячие) 2:28:28

Люди заходят в автобус по времени, у каждого свой пункт назначения; часть сидит, часть стоит. Нужно поддерживать оптимальное размещение.

Идея. Два множества: «сидящие» и «стоящие». По выходу пассажира удаляем его из соответствующего множества; новых, кому «выгоднее», пересаживаем. Работа с set туда-сюда.

Задача F. Гемоглобин (стек с суммой) 2:32:47

Нужно добавлять числа в стек, удалять и отвечать на сумму $k$ последних.

Идея. Храним параллельно стек префиксных сумм. Если в стеке лежит $1, 2, 3$, то в стеке сумм — $1, 3, 6$. Сумма последних $k$ = (верхнее значение) $-$ (значение на $k$ позиций ниже). При удалении просто делаем pop из обоих.

Задача G. Защитники (ладьи) 2:35:22

Клетчатое поле, операции: поставить ладью, убрать, спросить «побит ли весь прямоугольник». Ладья бьёт строку и столбец. Прямоугольник побит, если в каждой его строке ИЛИ в каждом столбце есть ладья.

Идея. Храним множества свободных строк и свободных столбцов, плюс счётчики ладей в каждой строке/столбце. Добавили ладью — убрали строку/столбец из «свободных»; удалили и счётчик стал $0$ — вернули обратно. Ответ на запрос: в прямоугольнике нет свободной строки или нет свободного столбца (проверяется lower_bound за логарифм).

Задача H. Гоблины (очередь с вставкой в середину) 2:40:40

Есть очередь: добавляют в конец, но «привилегированные» встают в середину; из начала уходят.

Идея. Две дека: первая и вторая половины очереди. Вставка в середину — это добавление в конец первой дека (или начало второй). Поддерживаем, чтобы половины отличались не более чем на один; при выходе/вставке перекидываем элемент между деками.

Задача I. Тетрис 2:42:45

Блоки с заданными левым и правым краями нужно разложить по «строчкам» так, чтобы в строчке блоки не пересекались, минимизируя число строчек.

Идея. Сортируем блоки по левому краю. Жадно кладём очередной блок в строчку, где он помещается (первая свободная). Для каждой строчки храним «первое свободное место» (правый край последнего блока).

Задача J. Память (аллокатор) 2:44:42

Есть память размера $n$ и запросы «занять $k$» и «освободить ранее занятое». Нужно выдавать подходящий свободный кусок.

Идея. Храним свободные куски в set, отсортированном по длине. На «занять» берём самый близкий по размеру кусок (меньший, но достаточный) — он «менее ценен» для будущего; отрезаем нужное, остаток возвращаем. На «освободить» — возвращаем кусок и, если рядом есть свободные, склеиваем.