Degree-hours from a gappy sensor
The outdoor sensor of a smart thermostat sends the temperature whenever it can: usually once an hour, but the connection drops, and between readings there may be five minutes or half a day. To estimate how much heat went on heating, degree-hours are needed: the integral over time of how many degrees colder it is outside than a given temperature B. When it is warmer than B, zero goes into the integral, not a negative number.
Between two readings assume the temperature changed evenly, along a straight line. Compute the degree-hours from the first reading to the last.
The second example is a real day in Almaty, 4 April 2025, and among the hidden tests is the whole heating season by the hour (the ERA5-Land reanalysis via Open-Meteo, CC BY 4.0).
Input
The first line holds n and B (1 ≤ n ≤ 200,000, −600 ≤ B ≤ 600). Then n lines t T: the time of the reading in minutes from the start of observations and the temperature in tenths of a degree (0 ≤ t ≤ 2·10⁹, times strictly increasing; −600 ≤ T ≤ 600). B is in tenths of a degree too.
Output
One number: the degree-hours (degrees, not tenths, times hours). The answer is accepted with a relative error of up to 10⁻⁶.
Examples
Example 1
3 180 0 200 60 160 120 160
2.500000
Example 2
8 180 480 99 600 136 660 169 780 203 840 205 1020 187 1080 170 1200 132
21.700000
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The first example: at midnight +20 °C, an hour later +16 °C, another hour later +16 °C, and B = 18 °C. Draw the graph and shade what needs to be added up. Is it two trapezoids?
2Hint 2
On the interval between two readings the shortfall from B is a linear function of time. The positive part of a linear function comes in three kinds: all of it, none of it, or a triangle up to the point where the line crosses zero.
3The idea
This is the integral of a function given by a table, and between points we agreed to treat it as linear, so the trapezoidal rule for the temperature itself is exact. But we integrate not the temperature but max(0, B − T), and this function has a kink where T crosses B. Inside an interval with no crossing it is an ordinary trapezoid. Where there is one, the integral is the area of a triangle: a line from g₀ > 0 to g₁ < 0 crosses zero at a fraction g₀/(g₀ − g₁) of the interval, and the area equals g₀² / (g₀ − g₁) · Δt / 2.
4Walkthrough
For each pair of neighbouring readings compute g₀ = B − Ti and g₁ = B − Ti+1. Both at least zero: add (g₀ + g₁)/2 · Δt. Both at most zero: nothing. Of different signs: a triangle with its apex at the end where the difference is positive. The steps differ, and each trapezoid takes its own width: the trapezoidal rule does not require equal intervals, unlike Simpson. At the end divide by 10 (tenths of a degree) and by 60 (minutes to hours).
Why the readings cannot first be clipped at zero and then summed by trapezoids. In the first example the clipped differences are 0, 2 and 2 degrees, and trapezoids give 1 + 2 = 3 degree-hours. But in the first hour the temperature dropped below 18 °C only in its second half: the real area is a triangle of 0.5 degree-hours, and the answer is 2.5. Clipping “smears” the kink over the whole interval. On winter data, where the temperature is almost always below 18 °C, the error is small, but in spring there are crossings every day, and it grows.
4+Solution
5Complexity
O(n) time, and O(n) memory for reading, although O(1) would do: only two neighbouring readings are needed.
6Common mistakes
- Clipping before summing. max(0, B − T) at the points, then trapezoids: an overestimate at every crossing of B; the first test.
- Assuming the step is an hour. Readings come irregularly; the width of a trapezoid is the difference of times, not the reading number.
- Negative contributions. If trapezoids for B − T are summed without clipping, warm hours are subtracted from cold ones, although they give no heat back to the house.
- One reading gives zero. With n = 1 no time has passed, and the answer is 0.