Индекс из прямых
Каталог землетрясений хранит моменты толчков по возрастанию, в наносекундах от начала 1970 года. Чтобы находить в нём момент быстрее двоичного поиска, кривую «момент → место» заменяют кусками прямых, как в выученных индексах баз данных. Прямая куска угадывает место ключа с ошибкой не больше ε, и ключ остаётся найти среди 2ε + 1 мест вокруг догадки. Индекс хранит только начала кусков и наклоны их прямых: чем меньше кусков, тем он меньше.
Ключи k0 < k1 < … < kn−1 стоят на местах 0, 1, …, n − 1. Куски строятся жадно, слева направо. Кусок начинается с первого ключа, который ещё не вошёл ни в один кусок, — пусть это ks. Его прямая проходит через точку (ks, s), то есть первый ключ угадывает точно, а наклон σ можно подбирать. Кусок берёт следующие ключи по одному, пока есть такое σ, что для каждого ключа kp куска
|s + σ · (kp − ks) − p| ≤ ε.
Ключ, с которым такого σ уже нет, начинает новый кусок. Для каждого из m значений ε выведите, сколько получится кусков.
Три теста — настоящие данные: моменты всех землетрясений магнитудой от 5 за 2015–2025 годы (каталог USGS ComCat), а также население и широты городов мира от 10 000 жителей (GeoNames).
В первом примере при ε = 1 первый кусок берёт ключи 0, 10, 20, 31 и 40: подходит, например, σ = 0,1. Ключу 100 на месте 5 нужно σ от 0,04 до 0,06, а ключ 40 требует σ ≥ 3/40 = 0,075 — ключ 100 начинает второй кусок. При ε = 0 куски получаются такие: 0, 10, 20 — затем 31, 40 — затем 100.
Во втором примере три первых ключа лежат на прямой с наклоном 1/333 333 333 333 333 333, а наклон до последнего ключа — 3/1018. Эти числа различаются в восемнадцатом знаке, и при ε = 0 последний ключ начинает новый кусок.
Вход
В первой строке n и m (1 ≤ n ≤ 150 000, 1 ≤ m ≤ 5). Во второй — n различных целых ключей по возрастанию, |k| ≤ 2·1018. В третьей — m целых ε (0 ≤ ε ≤ 109).
Выход
m чисел через пробел: сколько кусков получится при каждом ε.
Примеры
Пример 1
6 2 0 10 20 31 40 100 0 1
3 2
Пример 2
4 1 0 333333333333333333 666666666666666666 1000000000000000000 0
2
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 13 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Прямая проходит через первую точку куска, поэтому от неё остаётся один параметр — наклон σ. Какие σ разрешает один ключ kp? Запишите условие |s + σ·(kp − ks) − p| ≤ ε как ограничение на σ.
2Подсказка 2
Каждый ключ разрешает отрезок наклонов, а весь кусок — их пересечение. Пересечение отрезков — снова отрезок, и хранить нужно только его концы. Как сравнивать концы, чтобы не ошибиться на ключах до 2·1018?
3Идея
Обозначим Δ = kp − ks > 0 и d = p − s. Условие ключа равносильно (d − ε)/Δ ≤ σ ≤ (d + ε)/Δ. Кусок держит отрезок допустимых наклонов [lo, hi]: очередной ключ сужает его до пересечения со своим отрезком. Если пересечение пусто, ни одна прямая через первую точку не годится сразу для всех ключей — ключ начинает новый кусок, и отрезок снова становится всей прямой. Это и есть «сужающийся конус»: прямые через первую точку с наклонами от lo до hi заметают угол, и каждый ключ его сужает.
4Разбор
Концы отрезка — дроби a/b с положительным знаменателем Δ, и сравнивать их нужно точно: a/b ≤ c/d ровно тогда, когда a·d ≤ c·b. Числители не больше n + ε, знаменатели — до 4·1018, и произведения доходят до 1027. Целые Python это выдерживают сами. В Go нужно 128-битное произведение: bits.Mul64 перемножает модули, а знак числителя учитывается отдельно.
Вот что получается на настоящих данных. Моменты 19 тысяч землетрясений при ε = 64 укладываются в 16 кусков: толчки идут почти равномерно, и кривая «момент → место» почти прямая. Население городов — в 18 кусков, хотя целиком эта кривая для интерполяции хуже некуда. Закладок через каждые 2ε + 1 = 129 ключей при той же ошибке понадобилось бы 148 и 238.
4+Решение
5Сложность
O(n·m) времени: каждый ключ при каждом ε сравнивается с концами отрезка за O(1). Памяти — O(n) на сами ключи.
6Типичные ошибки
- Наклоны в числах с плавающей точкой. Две разные дроби с огромными знаменателями округляются в одно и то же число: во втором примере 1/333 333 333 333 333 333 и 3/1018 для
floatравны. Этоwrong.py. - Произведения в int64. 109 · 4·1018 не помещается в 64 бита, и сравнение молча ошибается. Это
wrong.go. - Проверять только сам ключ. Можно принимать ключ, лишь если его собственный наклон d/Δ лежит внутри конуса, — так устроено разбиение в одной из статей о выученных индексах. Но условие задачи требует другого: ключ можно угадать с ошибкой до ε, а не точно. Такое правило режет куски чаще — у населения городов при ε = 16 выходит 77 кусков вместо 45.
- Забыть сбросить отрезок. Новый кусок начинается с чистого листа: старые ограничения относились к прямой через другую точку.