Две книги на сертификат
Вам подарили сертификат книжного магазина на S тенге. Правила строгие: взять можно ровно две разные книги, и их цены в сумме должны дать ровно S — сдачи не дают, доплатить нельзя. Сколько есть способов выбрать такую пару из каталога?
Книги с одинаковой ценой — всё равно разные книги, и пара из них считается. Одну книгу дважды взять нельзя. Порядок не важен: «первая и вторая» и «вторая и первая» — одна пара.
Вход
В первой строке числа n и S (1 ≤ n ≤ 200 000, 2 ≤ S ≤ 2·10⁹). Во второй — n цен книг a₁, …, an (1 ≤ ai ≤ 10⁹).
Выход
Одно число — количество пар i < j, у которых ai + aj = S. Обратите внимание: ответ может не поместиться в 32 бита.
Примеры
Пример 1
6 1000 200 800 500 500 300 700
3
Пример 2
4 1000 500 500 500 100
3
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Перебрать все пары — это n(n − 1)/2, при n = 200 000 почти двадцать миллиардов. Слишком много. Посмотрите на одну книгу: сколько у неё вариантов цены для партнёра?
2Подсказка 2
Вариант ровно один: S − a. Значит, для каждой книги нужно лишь узнать, сколько книг стоят S − a. Как отвечать на такой вопрос за O(1)?
3Подсказка 3
Чтобы не посчитать пару дважды и не взять книгу в пару к самой себе, сравнивайте каждую книгу только с теми, что встретились раньше неё.
4Идея
Идём по каталогу слева направо и держим хеш-таблицу «цена → сколько книг с такой ценой уже пройдено». Для очередной книги с ценой a каждая уже пройденная книга с ценой S − a даёт ровно одну новую пару; прибавляем их число к ответу и только потом записываем саму книгу в таблицу. Каждая пара i < j посчитана один раз — в момент, когда дошли до j.
5Разбор
Две строки в цикле: pairs += seen.get(s - a, 0), затем seen[a] += 1. Порядок важен. Если сначала записать книгу, а потом спросить про S − a, то при 2a = S книга найдёт сама себя.
Ровно эта ошибка сидит в «очевидном» решении в два прохода: сначала посчитать все цены, потом для каждой книги прибавить count[S − a] и разделить сумму пополам. Деление на два честно убирает двойной счёт пар из разных цен, но книга с ценой S/2 при этом спарилась с собой. Во втором примере три книги по 500 дают 3 · 3 = 9, после деления — 4, а пар на самом деле три. Чинить можно и так, вычитая самопары, но однопроходное решение просто не даёт им появиться.
Другой путь — отсортировать цены и идти двумя указателями с концов. Он работает за O(n log n) и без хеш-таблицы, но одинаковые цены требуют аккуратности: блоки равных значений надо перемножать, а при a = S/2 брать сочетания из блока по два.
5+Решение
6Сложность
Один проход, на каждую книгу — два обращения к хеш-таблице: O(n) в среднем. Память — O(n) на таблицу разных цен.
7Типичные ошибки
- Книга в паре с собой. Записать книгу в таблицу до того, как спросить про партнёра, или посчитать все цены заранее. Ловится уже первым примером.
- Множество вместо счётчиков. Пары из книг с одинаковой ценой пропадают: множество помнит, что цена была, но не сколько раз.
- Переполнение. Двадцать миллиардов пар не помещаются в 32 бита. В Go нужен
int64(илиintна 64-битной машине), в Python об этом думать не надо. - Двойной цикл. Верно, но на 200 000 книгах займёт минуты.