Problem 316342 · hard · Level 03 Linear Management & Searching

The Glitchy Sensor

outliers · robust fitting · least-squares line · residuals · median

A cheap pressure sensor is calibrated against a laboratory gauge. For 200 test runs the log records the gauge value x (between 0 and 100) and the sensor's raw output y. In normal operation the sensor follows a straight line y = a + b·x plus a little noise. But the logger is unreliable, and between 15% and 30% of the rows are glitches of three kinds:

  • the output spikes: y is far above the normal reading;
  • the output drops out: y is exactly 0.0;
  • the row is mixed up: x is recorded as a value far beyond 100, with an ordinary-looking y from another run.

Nothing in a row says whether it is a glitch. Write calibrate(xs, ys) that returns a tuple (a, b): your estimate of the sensor's normal line.

The setup provides sensor_log(seed), which returns the lists (xs, ys) of one calibration; each test calls calibrate(*sensor_log(seed)) with its own seed.

Examples

Input:  xs = [0, 10, 20, 30, 40, 50, 60, 70, 180], ys = [2, 7, 0.0, 17, 22, 90, 32, 37, 20]
Output: for example (2.0, 0.5)
Explanation: the rows at x = 20 (a drop-out), x = 50 (a spike) and x = 180 (a mix-up)
are glitches; the other six lie exactly on y = 2 + 0.5x. The least-squares line through
all nine rows is roughly y = 19.7 + 0.11x, far from the normal line.

How this problem is scored

  • Your line is compared with the sensor's true normal line over the working range: the error is the average of (your line(x) - true line(x))² over x from 0 to 100.
  • Baseline: the least-squares line through all 200 rows. You pass a test when your error is no larger than the baseline's.
  • Best known: the least-squares line through exactly the rows that are not glitches (which only the judge knows).
  • Your score is 100 · log(baseline / yours) / log(baseline / best), between 0 and 100 (100 at or below the best known).

Constraints

  • 200 rows per test; return two finite numbers
  • the result must not depend on the clock; seed any randomness you use
  • each call must finish well within a second (a few tens of thousands of simple steps are fine)

Goals

  • See how a few bad points drag a least-squares line away from the rest of the data
  • Fit a line that follows the majority of the points and ignores the glitches
  • Use residuals to decide which points to trust
Starting Python…