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

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

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

Обе задачи на эту связку, но маска в них работает по-разному. В первой она сжимает объект: у каждого объекта мало признаков, поэтому сотни тысяч объектов схлопываются в не более чем 256 различных масок, и квадратичный перебор пар становится перебором пар масок. Во второй маска — это состояние перебора: она отвечает, какие из восьми значений уже уложены, и заменяет собой перебор всех сорока тысяч порядков.

Заодно во второй задаче встретится приём, полезный далеко за её пределами: если одна из компонент состояния монотонна, её переносят из индекса динамики в её значение — и таблица из двухсот тысяч ячеек превращается в две тысячи.

---

Теория

Бинарный поиск по ответу с проверкой через маски. Сам поиск занимает пять строк и всегда одинаков; вся задача прячется в проверке «достижимо ли значение $x$», и именно её маски делают дешёвой.

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

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

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

Как решать:

1. Убедиться в монотонности: если значение $x$ достижимо, то и любое меньшее достижимо. Обычно это очевидно, но проговорить стоит.
2. Написать проверку check(x): пройти по объектам, для каждого построить маску «какие требования закрыты при пороге $x$».
3. Для каждой маски запомнить одного представителя. Разных масок не больше $2^m$, дубликаты не нужны — они ничего не добавляют.
4. Перебрать пары масок и проверить, покрывают ли они вместе все требования. Пар — $4^m$, что при $m = 8$ равно 65 536: мгновенно.

Мини-пример. Требований три, объектов пять. При пороге $x$ маски объектов вышли 110, 101, 110, 000, 011. Разных масок четыре, представителей четыре. Ищем пару, дающую 111: подходит 110 и 101, а также 110 и 011. Значит порог $x$ достижим — и то, что объектов с маской 110 было два, никак на ответ не повлияло.

Где ошибаются в узнавании: видят «максимизировать минимум» и правильно берут бинарный поиск, а проверку пишут перебором пар объектов — и получают $n^2\log$. Признак того, что нужны маски, всегда один и тот же: маленькое второе измерение. Если в ограничениях рядом с $n \le 3 \cdot 10^5$ стоит $m \le 8$, эта восьмёрка написана не случайно.

Сложность приёма: $O((n \cdot m + 4^m)\log C)$, где $C$ — диапазон значений ответа.

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

Два способа применить маски внутри проверки. Маска — это подмножество, упакованное в число, и внутри проверки бинпоиска она появляется в двух ролях. Различать их полезно, потому что от роли зависит и сложность:

1. Маска как сжатие объекта. У каждого объекта мало признаков (до 20–25), и объект целиком заменяется числом — набором его признаков. Тогда объектов становится не $n$, а не больше $2^k$ различных, и перебор пар из квадратичного по $n$ становится квадратичным по числу масок. Так устроена сегодняшняя первая задача.
2. Маска как состояние перебора. Объектов мало (до 20), но важен порядок или сочетание, и маска отвечает на вопрос «какие из них уже использованы». Перебор всех порядков ($20!$) заменяется перебором подмножеств ($2^{20}$). Так устроена вторая задача.

Как понять, что маски вообще уместны. Признак почти всегда стоит прямо в ограничениях: k ≤ 8, n ≤ 16, m ≤ 20, «значения не превосходят 8». Такие числа в условии — это не случайность и не забота о слабых машинах, а прямое указание на экспоненту от маленького параметра. Полезная привычка: увидев в ограничениях подозрительно маленькое число, сразу прикинуть $2^k$ и понять, влезает ли оно в лимит.

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

Где искать: по значениям или по индексам. Две почти одинаковые записи, и путать их не стоит. Если кандидаты — произвольные числа из большого диапазона, ищем по значению и получаем логарифм от диапазона. Если же ответ обязан быть одним из имеющихся чисел (как часто бывает в задачах «максимизировать минимум по парам»), удобнее отсортировать значения и искать по индексу — тогда проверок ровно $\log n$, а заодно исчезают вопросы про вещественные числа и точность.

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

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

Сложность приёма: $O(\log(\text{диапазон}) \cdot \text{стоимость проверки})$; всё, что дальше, зависит только от того, насколько дёшево удалось сделать проверку.

---

Задача 1 — CF ~2000 — «Minimax Problem»

Что дано

Дано n массивов, в каждом ровно m чисел. Нужно выбрать два индекса i и j (можно взять один и тот же дважды) и построить из них массив b длины m по правилу «в каждой позиции берём большее из двух»: b[k] = max(a[i][k], a[j][k]).

Требуется выбрать пару так, чтобы минимальный элемент получившегося массива b был как можно больше. Вывести сами индексы.

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

• Строка 1: два числа n и m ($1 \le n \le 3 \cdot 10^5$, $1 \le m \le 8$).
• Каждая из следующих n строк: m чисел — очередной массив ($0 \le a_{ik} \le 10^9$).

Формат вывода: два числа — индексы i и j (нумерация с единицы). Если подходящих пар несколько, годится любая.

Пример:

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

Вывод:
1 5

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

Проверим ответ руками. Первый массив — 5 0 3 1 2, пятый — 2 3 0 6 3. Берём поэлементный максимум:

Минимум получившейся строки равен 3. Полный перебор всех 36 пар подтверждает, что лучше 3 не бывает.

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

Вопрос «достижимо ли 3» превратился в «есть ли две маски, у которых объединение — все единицы». Маски 1 и 5: 10100 объединить с 01011 даёт 11111 — да, достижимо. А для порога 4 маска первого массива станет 10000, третьего — 00011, и подходящей пары уже не найдётся.

Отсюда и весь алгоритм: значение достижимости монотонно (если 3 достижимо, то и 2 достижимо — маски при уменьшении порога только «набирают» единицы), значит его можно искать бинарным поиском, а внутри проверки перебирать не пары массивов, а пары масок. Масок при m = 5 не более 32, при m = 8 — не более 256.

Идея решения

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

Почему предикат монотонен. Если при пороге x пара (i, j) подходит, то при любом x' < x она подходит тем более: неравенство a[i][k] ≥ x влечёт a[i][k] ≥ x'. Значит множество достижимых значений — отрезок от нуля до искомого максимума, и бинарный поиск корректен.

Почему условие переписывается через объединение масок. Минимум массива b не меньше x в точности тогда, когда каждый элемент b не меньше x, то есть в каждой позиции k хотя бы одно из чисел a[i][k], a[j][k] не меньше x. Позиция k попадает в маску массива ровно при этом условии, поэтому «в каждой позиции хотя бы один» — это и есть «объединение масок равно полной маске».

Почему достаточно одного представителя на маску. Проверка зависит только от значений масок, а не от того, сколько массивов их дало. Два массива с одинаковой маской взаимозаменяемы, и хранить оба незачем — таблица представителей размера $2^m$ заменяет весь список из n массивов.

Почему разрешено брать i = j. Условие это допускает, и наш перебор пар масок естественно включает случай s = t — если одна маска уже полная, ответом будет пара из одного и того же индекса.

Почему не подойдёт перебор пар. Пар массивов до $4.5 \cdot 10^{10}$ — безнадёжно даже без бинарного поиска.

Псевдокод

прочитать n, m и все массивы; полная = (1 << m) - 1

функция проверить(x):
    представитель[маска] = 0 для всех 2^m масок
    для i от 1 до n:
        маска = 0
        для k от 0 до m-1:
            если a[i][k] >= x: маска |= (1 << k)
        представитель[маска] = i          // любой подойдёт
    для s от 0 до полная:
        если представитель[s] == 0: продолжить
        нужно = полная XOR s              // чего не хватает
        для t от нужно до полная:
            если представитель[t] != 0 и (t И нужно) == нужно:
                вернуть (представитель[s], представитель[t])
    вернуть «нет»

lo = 0, hi = максимум по всем числам, лучшее = (1, 1)
пока lo <= hi:
    mid = (lo + hi) / 2
    если проверить(mid) вернуло пару:
        лучшее = эта пара
        lo = mid + 1
    иначе:
        hi = mid - 1

вывести лучшее

Код решения

Комментарии по реализации. Внутренний перебор второй маски начинается не с нуля, а с need: любая подходящая маска обязана содержать все недостающие биты, а значит численно не меньше need. Экономия небольшая, но бесплатная. Представитель перезаписывается без проверки «уже есть» — какой именно массив останется, неважно. Массив в C++ хранится плоско (a[i * m + k]), а не вектором векторов: при $2.4 \cdot 10^6$ чисел разница по времени заметна.

Отдельно про Python. Маски собираются по столбцам списковыми включениями со zip, а не двойным циклом по элементам: тот же объём работы уходит внутрь интерпретатора и выполняется в несколько раз быстрее. Но честно: на максимальном входе ($3 \cdot 10^5$ массивов по 8 чисел) это всё равно порядка $2.4$ млн сравнений на каждый из тридцати шагов бинарного поиска, и такое решение на CPython держится на грани лимита — на Codeforces его стоит отправлять на PyPy либо переписывать на C++. Алгоритм при этом ровно тот же; узкое место — только скорость интерпретатора.

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

Пример из условия. Максимум по всем числам — 9, ищем в диапазоне от 0 до 9.

Бинарный поиск сходится к 3 и запоминает пару, найденную на последней успешной проверке. Наш вывод: 1 5 — совпадает с ожидаемым.

Проверим ещё два случая, которых в условии нет:

Ввод:
1 3
4 4 4

Вывод:
1 1

Массив один, брать можно только его дважды — ответ 1 1, минимум равен 4.

Ввод:
2 2
5 0
0 5

Вывод:
1 2

По отдельности каждый массив даёт минимум 0, вместе — 5 5 с минимумом 5. Ровно тот случай, ради которого разрешено брать два разных индекса.

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

• n = 1. Единственный вариант — пара из одного и того же индекса; код обязан его находить, а не отвечать «нет».
• m = 1. Масок всего две (0 и 1), ответ — индекс максимального числа, взятый дважды.
• Все числа нулевые. Ответ — любая пара, максимум минимума равен нулю. Начальное значение best = (1, 1) гарантирует, что мы выведем хоть что-то даже если первая же проверка провалится.
• Один массив закрывает всё сам. Тогда s = t — пара из одинаковых индексов; перебор пар масок такое допускает, потому что t начинается с need, а не с s + 1.
• Максимальный вход. $3 \cdot 10^5$ массивов по 8 чисел — $2.4$ млн чисел; чтение должно быть буферизованным.
• Ответ равен максимальному числу входа. Проверка на верхней границе бинарного поиска обязана отрабатывать: hi берётся как максимум по всем числам, а не как $10^9$ «на всякий случай».

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

1. Перебирать пары массивов внутри проверки. Именно этот шаг и надо было заменить масками; без замены решение — $n^2\log$.
2. Хранить список всех массивов с данной маской. Достаточно одного: проверка зависит только от значений масок.
3. Запрещать i = j. Условие это разрешает, и на входе из одного массива других вариантов просто нет.
4. Не сохранять пару с последней успешной проверки. Бинарный поиск заканчивается на неудачной проверке, и если пару не запоминать по ходу, её придётся искать заново.
5. Брать hi = 10^9 без надобности. Не ошибка, но лишние шаги: максимум по входу — более честная верхняя граница.
6. Сравнивать маски как s | t == full в языке с приоритетами операций. В C++ | ниже по приоритету, чем ==, и выражение s | t == full тихо считает совсем другое. Скобки обязательны.
7. Читать ввод построчно на $2.4$ млн чисел. Ввод здесь заметная часть времени работы.

Сложность

Время: $O((n \cdot m + 4^m)\log C)$, где $C$ — максимальное значение. При $m = 8$ и $n = 3 \cdot 10^5$ — около $7 \cdot 10^7$ элементарных операций. Память: $O(n \cdot m + 2^m)$.

---

Задача 2 — CF ~2200 — «Vladik and cards»

Что дано

Дана последовательность из n чисел, каждое от 1 до 8. Нужно выбрать из неё самую длинную подпоследовательность, удовлетворяющую двум условиям:

1. количества вхождений любых двух значений от 1 до 8 в выбранной подпоследовательности различаются не больше чем на единицу (значение, не вошедшее совсем, считается имеющим ноль вхождений);
2. все вхождения одного значения идут в подпоследовательности подряд — одним непрерывным блоком (в исходной последовательности они, разумеется, могут стоять вразброс).

Нужна длина такой подпоследовательности.

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

• Строка 1: целое n ($1 \le n \le 1000$).
• Строка 2: n целых чисел от 1 до 8.

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

Пример 1:

Ввод:
3
1 1 1

Вывод:
1

Пример 2:

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

Вывод:
8

Пример 3:

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

Вывод:
17

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

Начнём с первого примера — он маленький, но объясняет условие лучше любых слов. Последовательность 1 1 1. Возьмём две единицы: тогда у значения 1 два вхождения, а у значения 2 — ноль, разница два, первое условие нарушено. Значит больше одной карточки взять нельзя, ответ 1. Второй пример зеркальный: все восемь значений присутствуют по разу, разница нулевая — берём всё.

Теперь третий пример, где и прячется задача. Двадцать четыре карточки, ответ 17. Заметим: $17 = 8 \cdot 2 + 1$. Это подсказывает структуру ответа вообще: если обозначить наименьшее из восьми количеств за c, то каждое значение входит c или c + 1 раз, и общая длина равна $8c + e$, где e — количество значений, взятых по c + 1 разу. То есть ответ описывается всего двумя числами.

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

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

Соберём наблюдения. Решение описывается: числом c, порядком, в котором идут восемь значений, и тем, какие из них получили лишнюю копию. Порядок — это $8! = 40320$ вариантов, что уже многовато, а вместе с перебором c и подавно. Здесь и появляются маски: какие значения уже уложены — это подмножество восьмиэлементного множества, то есть число от 0 до 255, и перебирать порядок целиком незачем.

Идея решения

Алгоритм в одну фразу: бинарным поиском найти наибольшее c, при котором все восемь значений удаётся уложить блоками по c копий, а проверку выполнить динамикой по маске уложенных значений; ответ — $8c + e$, где e — максимальное число блоков, которым при этом c хватило на лишнюю копию.

Почему по c можно искать бинарным поиском. Если удалось разложить блоки по c копий, то по c − 1 тем более: достаточно выкинуть из каждого блока по одной карточке, порядок и непрерывность от этого не пострадают. Значит множество допустимых c — это отрезок от нуля, и применим бинарный поиск. Само c не превосходит n / 8.

Почему достаточно посмотреть только на наибольшее c. Пусть C — максимальное допустимое. Любой ответ с меньшим c не длиннее $8c + 8 \le 8C$, а ответ с C не короче $8C$. Значит оптимум достигается на C, и для него нужно лишь максимизировать число лишних копий.

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

$dp[\text{маска}][e] = \text{минимальная длина префикса, на которой уложены значения маски, причём }e\text{ из них получили лишнюю копию}$

Состояний становится $256 \cdot 9 = 2304$, переходов из каждого восемь — вся проверка занимает меньше двадцати тысяч операций вместо двух миллионов. Приём общий и стоит его запомнить: если одна из компонент состояния монотонна и её хочется минимизировать, её переносят из индекса в значение.

Переход. Из состояния (маска, e) с префиксом i берём любое значение v, ещё не уложенное, и решаем, взять c или c + 1 его копий. Позиция, где закончится блок, находится по заранее сохранённому списку позиций значения v: ищем в нём первую позицию не левее i, отсчитываем нужное количество вперёд и берём следующий индекс. Если копий не хватает — переход невозможен.

Вырожденный случай c = 0. Тогда «взять ноль копий» означает, что значение вовсе не входит в подпоследовательность, и префикс не сдвигается. Формула это учитывает сама, если аккуратно обработать k = 0: конец блока равен его началу.

Псевдокод

прочитать n и массив a (значения 1..8)
pos[v] = список позиций значения v

функция проверить(c):
    dp[маска][e] = бесконечность для всех
    dp[0][0] = 0
    для маска от 0 до 255:
        для e от 0 до 8:
            начало = dp[маска][e]
            если начало > n: пропустить
            для v от 0 до 7, если v не в маске:
                j = первая позиция v не левее «начало»
                для лишняя из (0, 1):
                    надо = c + лишняя
                    если надо == 0: конец = начало
                    иначе если в pos[v] есть «надо» позиций начиная с j:
                        конец = pos[v][j + надо - 1] + 1
                    иначе: пропустить
                    dp[маска | бит v][e + лишняя] = min(..., конец)
    вернуть максимальное e с dp[255][e] <= n, либо «нет»

бинарный поиск наибольшего c, при котором проверить(c) != «нет»
вывести 8 * c + проверить(c)

Код решения

Комментарии по реализации. Маска обходится в порядке возрастания числа — этого достаточно, потому что переход всегда добавляет бит, а значит идёт от меньшего значения к большему; отдельная сортировка по числу единиц не нужна. Списки позиций строятся один раз на весь запуск, а не внутри проверки: иначе логарифм в бинарном поиске потерялся бы на фоне пересборки. Обратите внимание, что при таком состоянии проверка получается настолько дешёвой, что бинарный поиск здесь — скорее правильная привычка, чем необходимость: при $n \le 1000$ прошёл бы и прямой перебор всех c от нуля до 125. Но проверять монотонность до написания кода полезно всегда — на большем n перебор бы уже не прошёл, а сама проверка не изменилась бы ни на строчку.

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

Пример 1: 1 1 1. Наибольшее c равно нулю: чтобы взять хотя бы по одной копии каждого значения, нужны все восемь значений, а есть только единицы. При c = 0 укладываем все восемь значений «пустыми блоками», и лишнюю копию удаётся дать ровно одному из них — самой единице. Ответ $8 \cdot 0 + 1 = 1$.

Пример 2: 8 7 6 5 4 3 2 1. При c = 1 каждое значение встречается ровно раз, и блоки укладываются в порядке появления. Лишних копий не остаётся: e = 0. Ответ $8 \cdot 1 + 0 = 8$.

Пример 3: двадцать четыре карточки. Проверим ключевые значения c:

Бинарный поиск останавливается на c = 2, для него максимум лишних копий равен единице, и ответ $8 \cdot 2 + 1 = 17$ — совпадает с эталоном. Обратите внимание на строку c = 1: там лишнюю копию получают все восемь значений, и итог тоже 16 — меньше, чем 17. Это ровно та ситуация, которую мы разбирали в идее решения: наибольшее c не хуже любого меньшего.

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

• n < 8. Все восемь значений набрать по разу невозможно, c = 0, ответ равен числу различных значений в последовательности.
• Все карточки одинаковые. c = 0, лишнюю копию получает одно значение — ответ 1 независимо от n.
• n = 1. Ответ 1. Проверка, что вырожденный случай c = 0 обрабатывается, а не отбрасывается.
• Ровно по k копий каждого значения. Тогда c = k, e = 0, ответ $8k$ — вся последовательность целиком, если она уже упорядочена блоками.
• Значение встречается ровно c раз, но слишком право. Блок может не поместиться из-за порядка: позиции нужного значения кончились раньше, чем префикс дошёл до них. Именно поэтому переход проверяет наличие копий, а не только их общее количество.
• n = 1000, все значения перемешаны. Верхняя граница: c до 125, бинарный поиск делает семь проверок.

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

1. Состояние «позиция плюс маска». Работает, но даёт два миллиона операций на проверку вместо двадцати тысяч; вместе с перебором c это уже риск не уложиться. Перенос префикса из индекса в значение — главный трюк задачи.
2. Забыть, что значение может не войти вовсе. При c = 0 блок нулевой длины — законный переход, и без него ответы на маленьких тестах занижаются.
3. Брать копии не самые левые. Любой другой выбор внутри блока только отодвигает конец префикса и ничего не улучшает.
4. Искать максимум по всем c, а не только по наибольшему. Не ошибка по ответу, но лишняя работа: достаточно доказать, что наибольшее c оптимально.
5. Считать, что порядок блоков надо перебирать. Маска ровно для того и нужна, чтобы заменить перебор $8!$ порядков на 256 подмножеств.
6. Ошибка на единицу в конце блока. Конец — это индекс последней взятой копии плюс один: следующий блок начинается со следующей позиции.

Сложность

Время: $O(\log(n/8) \cdot 2^8 \cdot 9 \cdot 8 \cdot \log n)$ — семь проверок, в каждой около двадцати тысяч переходов, в каждом переходе бинарный поиск по списку позиций. Фактически это доли миллисекунды. Память: $O(n + 2^8 \cdot 9)$.

---

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

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

• Codeforces 1102F «Elongated Matrix» (~CF 2000) — строки матрицы можно переставлять; матрица обходится по столбцам сверху вниз, и нужно максимизировать минимальную разность соседних чисел в получившейся последовательности. Подсказка: строк не больше шестнадцати — значит порядок строк это гамильтонов путь, а он ищется динамикой по маске; не забудьте про особый переход между концом одного столбца и началом следующего.
• Codeforces 431D «Random Task» (~CF 2100) — нужно найти наименьшее n, при котором количество чисел от 1 до n с ровно k единицами в двоичной записи равно заданному m. Подсказка: количество монотонно по n, а посчитать его для конкретного n можно, разбирая двоичную запись по разрядам и складывая биномиальные коэффициенты.
• Codeforces 1732C2 «Sheikh (Hard Version)» (~CF 2100) — для каждого запроса нужно найти самый короткий подотрезок, у которого разность суммы и побитового «и» максимальна. Подсказка: «и» на отрезке меняется не больше тридцати раз при движении границы — это и есть та маленькая величина, которая делает перебор реальным.
• Codeforces 1360H «Binary Median» (~CF 2100) — из всех двоичных строк длины m вычеркнули n заданных; нужно вывести медиану оставшихся. Подсказка: строку длины m удобно считать числом, а «сколько оставшихся строк меньше кандидата» — монотонной проверкой, внутри которой достаточно посчитать вычеркнутые.

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

---

Что дальше

Половина «Пика» позади. Обе сегодняшние задачи показали одно и то же: сам бинарный поиск на этом уровне не составляет труда — он всегда одинаковый, — а вся работа уходит в проверку. Если сегодня что-то далось тяжело, скорее всего это был не поиск, а вопрос «как сделать проверку дешёвой»; именно его и стоит тренировать. И полезная привычка на будущее: увидев в ограничениях подозрительно маленькое число — восемь, шестнадцать, двадцать, — сразу прикидывать $2^k$ и проверять, не про маски ли задача.

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