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

Задача

Тренд по любому окну

регрессия префиксные суммы двоичный поиск аналитика

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

Исследователи задают вопросы вида «каков тренд с года A по год B?». Ответ — наклон прямой, проведённой методом наименьших квадратов через все измерения, у которых A ≤ xi ≤ B. Температура — в десятых долях градуса, время — в годах, так что наклон получается в десятых градуса за год, то есть ровно в градусах за десять лет. Если в окно попало меньше двух измерений, прямую провести нельзя.

Вопросов много, и отвечать нужно быстро. Один из тестов — настоящие среднегодовые температуры Алматы с 1941 по 2025 год (реанализ ERA5) и все окна длиной от десяти лет.

Вход

В первой строке число n (1 ≤ n ≤ 50 000). В каждой из следующих n строк два целых числа xi и yi (|xi| ≤ 50 000, |yi| ≤ 1000), годы строго возрастают. Дальше число вопросов q (1 ≤ q ≤ 100 000) и q строк с целыми A и B (−50 000 ≤ A ≤ B ≤ 50 000).

Выход

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

Примеры

Пример 1

Вход
7
2001 84
2002 91
2004 88
2005 95
2008 97
2009 93
2010 104
7
2001 2010
2001 2005
2003 2006
2005 2005
2006 2007
1990 2002
2008 2030
Выход
1.538759690
1.900000000
7.000000000
-
-
7.000000000
3.500000000

Ограничения

Время · Python
6000 мс
Время · Go
1500 мс
Память
256 МБ
Проверка
7 тестов

Разбор

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

1Подсказка 1

Для одного окна всё понятно: найти его измерения и провести прямую по формуле из статьи. Но окон до ста тысяч, и каждое может накрывать почти весь ряд. Что из ряда на самом деле нужно формуле? Не сами точки, а несколько чисел о них — каких?

2Подсказка 2

Раскройте скобки в формуле наклона: Σ(x − x̄)(y − ȳ) = Σxy − Σx·Σy/m, и так же для Σ(x − x̄)². Остаются четыре суммы и число точек. А сумму по отрезку ряда умеют считать за O(1).

3Подсказка 3

Окно задано годами, а не номерами измерений. Годы отсортированы — как быстро найти первое измерение не раньше A и последнее не позже B?

4Идея

Наклон прямой наименьших квадратов зависит только от пяти чисел: m, Σx, Σy, Σxy, Σx². Умножив числитель и знаменатель формулы на m², получаем

$$b = \frac{m\sum xy - \sum x \sum y}{m\sum x^2 - \bigl(\sum x\bigr)^2}.$$

Все четыре суммы складываются, поэтому их хранят префиксными суммами: сумма по измерениям с номерами от lo до hi − 1 — это разность двух префиксов. Границы окна по годам находит двоичный поиск. Это та же мысль, что в статье: регрессии нужны не строки, а их суммы, и суммы окна собираются из готовых кусков.

5Разбор

Один раз проходим по ряду и строим четыре массива префиксов. На вопрос (A, B) двоичным поиском находим lo — первое измерение с x ≥ A — и hi — первое с x > B; в окне m = hi − lo измерений. Если m < 2, печатаем прочерк. Иначе берём разности префиксов и делим по формуле.

Знаменатель при m ≥ 2 строго положителен: он равен m²·(разброс годов), а годы различны. Числитель и знаменатель — целые числа. В Python они точные сами собой. В Go оценим их размер: |Σx| ≤ 5·10⁴ · 5·10⁴ = 2,5·10⁹, его квадрат — 6,25·10¹⁸; m·Σx² ≤ 5·10⁴ · 1,25·10¹⁴ — столько же. Это меньше предела int64, 9,2·10¹⁸, так что считаем числитель и знаменатель точно и делим один раз. Пятый тест собран как раз у этой границы.

На настоящих данных Алматы ответы совпадают с таблицей из статьи: окно 1941–2025 даёт 0,122, окно 1976–2025 — 0,494 (это градусы за десять лет). За 1941–1975 здесь −0,714, а не −0,72, как в статье: в задаче средние годы округлены до десятых долей градуса.

5+Решение
6Сложность

O(n) на префиксы и O(log n) на вопрос: O(n + q log n) всего. Решение в лоб — O(n·q), до 5·10⁹ шагов.

7Типичные ошибки
  • Каждый вопрос — заново по окну. Верно, но четвёртый тест с сотней тысяч широких окон не уложится во время ни на каком языке.
  • Префиксы в числах с плавающей точкой и формула через разность. Здесь это обычно сходит с рук, но привычка опасная: mΣx² и (Σx)² — два больших близких числа, и при годах, далёких от нуля, их разность в float64 теряет верные знаки. Пока данные целые, считайте в целых.
  • Переполнение в 32-битных целых. Уже Σx² по пятидесяти тысячам лет — до 10¹⁴.
  • Окно из одного года. Одна точка не задаёт прямую: знаменатель равен нулю. Прочерк, а не деление на ноль.
  • Границы двоичного поиска. Год B входит в окно: нужна правая граница «первый год больше B», а не «не меньше».

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

ML Алгоритм Линейная регрессия Подбирает коэффициенты модели так, чтобы сумма квадратов промахов по данным была наименьшей. O(n·d² + d³) 2 задачи TEC Приём Префиксные суммы Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки. O(n) на построение, O(1) на запрос 2 задачи
Каталог алгоритмов