Задачник Базовый курс EN

Толчки рядом во времени

оценка сортировка два указателя наука и физика геоданные

Сейсмологи ищут толчки, которые случились близко друг к другу во времени: так находят афтершоки и рои землетрясений. Дано n моментов времени в секундах и число T. Сколько пар событий отстоят друг от друга не больше чем на T секунд? Пары неупорядоченные: пара событий считается один раз.

Второй и третий тесты — все 19 073 землетрясения силой от пяти баллов за 2015–2025 годы из каталога USGS, время в секундах от начала 2015 года, окно — час и сутки.

Прежде чем писать код, оцените: сколько шагов сделает перебор всех пар при n = 2·10⁵ и сколько это секунд.

Вход

В первой строке n и T (1 ≤ n ≤ 2·10⁵, 0 ≤ T ≤ 10⁹). Во второй — n целых чисел t₁, …, t_n (0 ≤ t_i ≤ 10⁹) в произвольном порядке; моменты могут совпадать.

Выход

Одно число — количество пар i < j, для которых |t_i − t_j| ≤ T.

Примеры

Пример 1

Вход

6 3600
7200 0 3600 100000 3601 7200

Выход

Ограничения

Время · Python: 3000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 8 тестов

Разбор

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

1Подсказка 1

Пар при n = 2·10⁵ около 2·10¹⁰. Даже если проверка одной пары стоит наносекунду, это двадцать секунд. Значит, пары нужно считать, не перебирая их. Что изменится, если моменты упорядочить?

2Идея

Отсортируем моменты. Для события i все более поздние события, которые отстоят от него не больше чем на T, идут подряд сразу за ним — до первого, которое уже дальше. Если знать конец этого блока j, то событие i даёт j − i − 1 пар. А когда i сдвигается вправо, конец блока может только сдвинуться вправо: два указателя.

3Разбор

Сортировка — O(n log n), около 3,5·10⁶ сравнений. Указатель j за весь проход сдвигается не больше n раз, поэтому второй этап линейный. Вместо второго указателя можно для каждого i искать конец блока двоичным поиском — тоже O(n log n).

Ответ бывает большим: если все события в одном окне, пар n(n − 1)/2 ≈ 2·10¹⁰, а в 32-битное целое помещается только 2,1·10⁹. В Go int 64-битный, в Python целые не переполняются, но в других языках здесь легко ошибиться.

Интересно посмотреть на перебор всех пар. На настоящем каталоге это 1,8·10⁸ проверок: Go справляется за доли секунды, а Python тратит секунды и не укладывается в лимит. На 2·10⁵ событий перебор не проходит нигде: Go нужно несколько секунд, Python — минуты. Именно такую оценку стоит сделать до того, как писать код.

3+Решение

4Сложность

O(n log n) на сортировку и O(n) на подсчёт.

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

Перебор всех пар. Верно, но 2·10¹⁰ проверок не помещаются ни в какой лимит.
Забыть отсортировать. В настоящем каталоге события уже идут по времени, а в остальных тестах — нет.
Совпадающие моменты. Пары с t_i = t_j тоже считаются. В седьмом тесте окно нулевое, и других пар там нет.
32-битный счётчик. В шестом тесте ответ почти 5·10⁹.

Алгоритмы задачи

TEC Приём Сколько операций в секунду Шаги алгоритма, делённые на скорость языка, — и вы знаете, уложится ли программа, ещё до того, как её написали. оценка — секунды в уме 1 задача TEC Приём Два указателя Два индекса движутся только вперёд и заменяют перебор пар или отрезков одним проходом за O(n). O(n) 2 задачи SRT Алгоритм Двоичный поиск Находит границу «нет → да» в упорядоченных данных за log₂ n проверок. O(log n) 2 задачи