Problem 360305 · hard · Level 03 Linear Management & Searching

When Did the Glacier Move Fastest?

least-squares line · R squared · sliding window · running sums

A stake drilled into a glacier is surveyed again and again. Each survey gives the time t (hours since the start, a whole number; several surveys may share the same hour) and how far the stake has moved, d (millimetres, a whole number). The lists t and d are in survey order, and t never decreases.

For every window of k consecutive surveys, fit the least-squares line d = a + b·t to the surveys in the window. Write glacier_windows(t, d, k) that returns a tuple (fast, speed, clean, r2):

  • fast is the start index of the window whose slope b has the largest absolute value (the fastest movement, forwards or backwards), and speed is that slope;
  • clean is the start index of the window whose line fits best, that is whose R² is the largest, and r2 is that R².

Windows in which all t are equal have no slope and are skipped for both; windows in which all d are equal are also skipped for R². If no window qualifies, the corresponding pair is (None, None). Values that are equal within 1e-9 count as equal, and the smallest start index wins.

For a window, with Sxx the sum of (t - mean t)², Syy the sum of (d - mean d)² and Sxy the sum of (t - mean t)(d - mean d): b = Sxy / Sxx and R² = Sxy² / (Sxx · Syy).

The setup provides stake_survey(n, seed), which returns random lists (t, d) of n surveys of a stake that speeds up and slows down with the seasons.

Examples

Input:  t = [0, 1, 2, 3, 4, 5], d = [0, 2, 4, 5, 9, 10], k = 3
Output: (2, 2.5, 0, 1.0)
Explanation: the four windows start at 0, 1, 2, 3. Their slopes are 2, 1.5, 2.5 and 2.5,
so the window starting at 2 is the first of the fastest. The window starting at 0
lies exactly on a line (R² = 1).

Input:  t = [4, 4, 4], d = [1, 2, 3], k = 2
Output: (None, None, None, None)

Constraints

  • 2 <= k <= len(t) == len(d) <= 10**5
  • 0 <= t[i] <= 10**6, -10**6 <= d[i] <= 10**6, all integers
  • floats are compared with a tolerance of 1e-6
  • the largest tests need an O(n) solution

Goals

  • Express the least-squares slope and R² through a handful of sums
  • Update those sums in O(1) as a window slides along the data
  • Keep integer sums exact and compare windows with a clear tie rule
Starting Python…