Тренировочная сессия 8: сортировка с бинарным поиском и хэш-таблица — мост к плато СЕССИЯ

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

Это восьмая, финальная сессия «Разогрева» — короткий итог перед тем, как мы поднимем планку. Сегодня в фокусе два инструмента, которые по отдельности уже встречались в цикле, но сегодня доводятся до автоматизма: бинарный поиск по отсортированному массиву как способ отвечать на запросы «сколько элементов не больше X» и хэш-таблица как способ мгновенно проверять и запоминать, что уже видели. По отдельности это классика, но именно связка «отсортировал → бинарным поиском отвечаю на запросы» и «завёл словарь → O(1) на проверку» — то, с чем в «Плато» вы столкнётесь внутри куда более комплексных задач: DP с бинарным поиском по ответу, графы с хэш-множествами посещённых вершин и так далее. Разогрев был про то, чтобы вернуть беглость в руках; сегодняшняя сессия — контрольная точка: если обе задачи ниже решаются уверенно и быстро, форма восстановлена полностью.

---

Теория

Бинарный поиск по отсортированному массиву — контрольное закрепление. Тот же приём, что в сессии 4: данные сортируются один раз, а каждый запрос «сколько элементов не больше X» отвечается за $O(\log n)$ вместо перебора за $O(n)$.

Что закрепляем сегодня — выбор между двумя функциями:

• upper_bound/bisect_right — для нестрогого «$\le X$»;
• lower_bound/bisect_left — для строгого «$< X$».

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

Хэш-таблица для проверки «видели ли мы это раньше» за O(1). Нужно быстро проверять, встречалось ли значение раньше, и/или считать, сколько раз оно встретилось — без перебора уже накопленных данных.

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

• в условии — «определить, встречалось ли значение ранее», «посчитать количество повторов»;
• запросов много, и линейный поиск по уже увиденным элементам дал бы $O(n)$ на каждый, итого $O(n^2)$.

Как решать:

1. Заводим словарь «ключ → счётчик или факт присутствия» (dict в Python, unordered_map в C++).
2. Идём по данным один раз, обновляя словарь на каждом шаге.
3. Каждая проверка и обновление занимают $O(1)$ в среднем.

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

Где ошибаются: используют хэш-таблицу там, где хватило бы простого массива по маленькому диапазону (работает, но не оптимально), либо, наоборот, ищут линейно по списку там, где нужен словарь с O(1)-доступом.

---

Задача 1 — CF ~1300 — «Queries about less or equal elements»

Что дано

Даны два массива целых чисел: a из n элементов и b из m элементов. Для каждого элемента b_j массива b нужно найти, сколько элементов массива a не превышают b_j (то есть меньше либо равны).

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

• Строка 1: два целых числа n, m ($1 \le n, m \le 2 \cdot 10^5$) — размеры массивов a и b.
• Строка 2: n целых чисел — элементы массива a ($-10^9 \le a_i \le 10^9$).
• Строка 3: m целых чисел — элементы массива b ($-10^9 \le b_j \le 10^9$).

Формат вывода: m целых чисел через пробел — j-е число равно количеству элементов a, не превышающих b_j.

Пример 1:

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

Вывод:
3 2 1 4

Пример 2:

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

Вывод:
4 2 4 2 5

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

Возьмём пример 1: a = [1, 3, 5, 7, 9], запросы b = [6, 4, 2, 8].

Массив a уже отсортирован — это удобно. Для запроса b_1 = 6: сколько элементов a не больше 6? Смотрим по порядку: 1 ≤ 6 (да), 3 ≤ 6 (да), 5 ≤ 6 (да), 7 ≤ 6 (нет) — дальше можно не смотреть, массив отсортирован, все следующие элементы тоже больше 6. Ответ — 3.

Если считать так для каждого запроса линейным проходом — это O(n) на запрос, а запросов m до $2 \cdot 10^5$ и элементов n тоже до $2 \cdot 10^5$ — итого до $4 \cdot 10^{10}$ операций. Слишком медленно для 1 секунды на тест.

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

Идея решения

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

Почему это работает. После сортировки массив a монотонен: если a[i] ≤ b_j, то и все a[k] при k < i тоже ≤ b_j (по отсортированности). Значит множество индексов, где a[i] ≤ b_j, — это ровно префикс массива, и его длина ищется бинарным поиском по инварианту «пока середина ≤ b_j — ответ минимум середина+1, сдвигаем левую границу вправо». В Python это bisect_right, в C++ — upper_bound: обе функции по определению возвращают именно первую позицию, где элемент строго больше искомого значения, — а значит и количество элементов ≤ b_j в отсортированном массиве.

Порядок исходных элементов a для ответа не важен — важно только само множество значений. Порядок запросов b тоже не важен — каждый обрабатывается независимо.

Псевдокод

прочитать n, m
прочитать массив a (n чисел)
прочитать массив b (m чисел)

отсортировать a по возрастанию

для каждого b_j из b:
    pos = первая позиция в отсортированном a, где элемент > b_j
    ответ_j = pos   // это и есть количество элементов a <= b_j

вывести все ответы через пробел

Код решения

Комментарии по реализации. Python — bisect_right(a, bj) без обёрток, чтение через sys.stdin.buffer.read().split() вместо input() — при $m \le 2 \cdot 10^5$ построчный input() в цикле заметно медленнее. C++ — upper_bound возвращает итератор, вычитание a.begin() даёт индекс-count; ios::sync_with_stdio(false) обязателен, иначе cin может не уложиться в лимит времени на таком объёме ввода.

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

Пример 1: a = [1,3,5,7,9] (уже отсортирован), запросы [6,4,2,8].

Наш вывод: 3 2 1 4 — совпадает с ожидаемым.

Пример 2: a = [1,2,1,2,5], отсортированный: [1,1,2,2,5], запросы [3,1,4,1,5].

Наш вывод: 4 2 4 2 5 — совпадает с ожидаемым.

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

• Все b_j меньше минимума a. Ответ для такого запроса — 0. bisect_right/upper_bound корректно вернут позицию 0.
• Все b_j не меньше максимума a. Ответ — n, вся длина массива.
• Повторяющиеся значения в a. Например a = [2,2,2], запрос b_j = 2 — ответ должен быть 3 (все элементы равны, все «не больше»). Именно поэтому нужен upper_bound/bisect_right, а не lower_bound/bisect_left — второй вариант считает «строго меньше», что не совпадает с условием «не больше».
• Отрицательные значения и значения на границах $-10^9$/$10^9$ — обычные int в C++ выдержат (используется long long с запасом, переполнения нет, но и не помешает).
• n = 1 или m = 1 — вырожденные размеры, алгоритм не делает предположений о минимальном размере массива, работает одинаково.

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

1. Перепутать lower_bound/bisect_left с upper_bound/bisect_right. Условие — «не больше» (≤), это upper_bound. Если случайно взять lower_bound, дубликаты, равные b_j, не посчитаются.
2. Забыть отсортировать a перед поиском. Бинарный поиск работает только по отсортированному массиву — без сортировки результат случаен.
3. Читать ввод через input()/cin без ускорения на построчной основе. При $n, m$ до $2 \cdot 10^5$ это может привести к превышению лимита времени просто на чтении, ещё до основной логики.
4. Пересчитывать позицию линейным проходом на каждый запрос — корректно, но O(n) на запрос даёт O(n·m) в худшем случае — слишком медленно.

Сложность

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

---

Задача 2 — CF ~1300 — «Registration System»

Что дано

Разрабатывается прототип системы регистрации имён пользователей. Правила:

• Если запрошенное имя ещё не встречалось — оно добавляется в базу, пользователь получает ответ OK.
• Если имя уже встречалось — система предлагает новое имя: к исходному имени дописывается наименьшее целое число i (начиная с 1), такое что имя + i ещё не встречалось. Это новое имя тоже считается занесённым в базу.

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

• Строка 1: целое число n ($1 \le n \le 10^5$) — количество запросов.
• Следующие n строк: по одному запросу на строку — непустая строка не более 32 строчных латинских букв.

Формат вывода: n строк — ответ системы на каждый запрос: OK либо предложенное имя.

Пример 1:

Ввод:
4
abacaba
acaba
abacaba
acab

Вывод:
OK
OK
abacaba1
OK

Пример 2:

Ввод:
6
first
first
second
second
third
third

Вывод:
OK
first1
OK
second1
OK
third1

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

Возьмём пример 2: запросы first, first, second, second, third, third.

• first встречается впервые → OK, запоминаем, что first встречался 1 раз.
• first снова → уже встречался, наименьшее свободное число — 1 (first1 ещё не встречался) → выводим first1, запоминаем, что счётчик для first теперь 2.
• second впервые → OK.
• second снова → выводим second1.
• Аналогично third → OK, затем third1.

Здесь ключевое наблюдение: не нужно хранить каждое сгенерированное имя (first1, second1, …) отдельно и искать среди них — если считать, сколько раз конкретное исходное имя уже запрашивалось, то следующий свободный суффикс — это ровно этот счётчик. Первый повтор first даёт суффикс 1, второй повтор дал бы суффикс 2, и так далее — числа выдаются строго по порядку, без пропусков.

Идея решения

Алгоритм в одну фразу: хранить в хэш-таблице счётчик встреч каждого исходного имени; если имя новое — OK и счётчик 1; если уже было — вывести имя + счётчик, увеличить счётчик на 1.

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

Хэш-таблица (dict в Python, unordered_map в C++) даёt проверку «встречалось ли имя» и обновление счётчика за O(1) в среднем — без неё пришлось бы искать имя среди уже увиденных за O(n), что на $n = 10^5$ даёт O(n^2) в худшем случае.

Псевдокод

прочитать n
создать пустую хэш-таблицу counter  // имя -> количество прошлых встреч

для каждого запроса name (всего n раз):
    если counter не содержит name (или counter[name] == 0):
        вывести "OK"
        counter[name] = 1
    иначе:
        i = counter[name]
        вывести name + i
        counter[name] = i + 1

Код решения

Комментарии по реализации. Python — читаем весь ввод разом через sys.stdin.buffer.read().split(), имена остаются как bytes, конвертируем в строку только при выводе (name.decode()) — это быстрее построчного input() на $n = 10^5$ запросов. C++ — unordered_map<string,int> с reserve заранее под примерный объём, чтобы избежать частых рехэшей; вывод через "\n", не endl, чтобы не сбрасывать буфер на каждой строке.

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

Пример 1: abacaba, acaba, abacaba, acab.

Наш вывод: OK / OK / abacaba1 / OK — совпадает с ожидаемым.

Пример 2: first, first, second, second, third, third.

Наш вывод: OK / first1 / OK / second1 / OK / third1 — совпадает с ожидаемым.

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

• n = 1. Единственный запрос — всегда OK, счётчика не с чем сравнивать.
• Одно и то же имя повторяется много раз подряд (например, 100 000 раз) — суффиксы должны идти строго по порядку 1, 2, 3, ..., 99999, счётчик обязан расти на каждой встрече, а не оставаться 1.
• Имя длиной ровно 32 символа — граничный случай длины, никакой отдельной обработки не требует, если строки читаются как обычные токены.
• Разные имена, ни одно не повторяется — все ответы OK, счётчики остаются равными 1, но никогда не запрашиваются повторно.
• Известная особенность задачи. Формально возможна ситуация, когда сгенерированное имя (name1) само по себе придёт как отдельный запрос до или после автогенерации — тогда наивный счётчик по name перестаёт быть строго корректным. Официальные тесты этот случай не проверяют, и решение с одним счётчиком на исходное имя — общепринятое и проходит все тесты. Знать про эту особенность полезно на будущее — не все структуры данных в задачах покрывают 100% формальных крайних случаев условия, только те, что реально протестированы.

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

1. Хранить имена в списке/массиве и искать линейным перебором — при $n = 10^5$ и длине имени до 32 символов это O(n) на проверку, итого O(n^2) в худшем случае — не укладывается в лимит времени. Нужна хэш-таблица.
2. Забыть увеличить счётчик после генерации имени. Если не увеличивать, третий повтор того же имени снова предложит name1, хотя оно уже занято.
3. Начинать счётчик с 0 и не различать «имя не встречалось» и «встречалось 0 раз». Проще всего трактовать отсутствие ключа в хэш-таблице как счётчик 0 (Python: dict.get(name, 0); C++: find() == end()).
4. Медленный ввод/вывод в C++ — без ios::sync_with_stdio(false) и с endl вместо "\n" при $n = 10^5$ строк можно не уложиться по времени.

Сложность

Время: $O(n)$ в среднем (хэш-таблица даёт амортизированную O(1) вставку и поиск на запрос). Память: $O(n)$ — по одной записи на уникальное исходное имя.

---

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

• Codeforces 189A «Cut Ribbon» (~CF 1300) — дана лента длины n и три допустимых длины куска a, b, c; нужно разрезать ленту на куски этих длин так, чтобы кусков получилось максимально много.
• Codeforces 25A «IQ test» (~CF 1300) — дана последовательность чисел, ровно одно из которых отличается от всех остальных чётностью; нужно найти позицию этого числа.
• Codeforces 152B «Steps» (~CF 1300) — на прямоугольном поле дана начальная клетка и список векторов сдвига; по каждому вектору нужно сделать максимально возможное число шагов, не выходя за границы поля, и посчитать суммарное число шагов.
• Codeforces 222B «Cosmic Tables» (~CF 1300) — дана таблица чисел и запросы трёх типов: поменять местами две строки, поменять местами два столбца, узнать значение в клетке.

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

---

Что дальше

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

Переходим на плато: Тренировочная сессия 9: жадное построение числа по цифрам.