805. The Best Long Average
A sensor logged n readings a[0] ... a[n-1], which may be negative. Among all contiguous
runs of at least k readings, print the largest average, to exactly 6 digits after the decimal
point.
readings 1 12 -5 -6 50, k = 2 -> 22.000000
readings 1 -1 1 -1 1 -1 1, k = 2 -> 0.333333
readings 4 1 1 1 4, k = 4 -> 2.200000
In the first log the run -6 50 averages 22, which beats 1 12 at 6.5 and the whole log at 10.4.
## Why the run is not simply the best one of length exactly k
It is tempting to believe that the best average is always achieved by a shortest run, since a longer run can only dilute it. That is false, and the third example shows it: the best run of length exactly 4 averages 1.75, while the whole log of length 5 averages 2.2. A single large value at each end is worth carrying the middle for.
So every length from k to n is in play, and there are O(n^2) runs to consider. At
n = 10^5 that is 10^10.
## The trick: search the ANSWER, not the run
Fix a candidate average x and subtract it from every reading. A run of length L and sum S
has average at least x exactly when
S / L >= x <=> S - x * L >= 0 <=> sum of (a[i] - x) over the run >= 0
The division is gone. The question is now whether SOME run of length at least k has a
non-negative sum in the shifted readings, and that is a prefix-sum sweep:
pre[0] = 0, pre[j] = pre[j-1] + (a[j-1] - x)
for j from k to n:
keep the smallest pre[i] seen for i <= j - k
if pre[j] - that smallest >= 0, some run qualifies
One pass, O(n).
## Why the predicate is monotone
Let g(x) be the largest value of S - x * L over the eligible runs. Each term S - x * L is a
straight line in x with slope -L, which is strictly negative because L >= k >= 1. A maximum
of strictly decreasing functions is strictly decreasing, so g falls as x rises, and
g(x) >= 0 is true up to a point and false after it. That point is the answer.
## The bounds
lo = min(a) and hi = max(a). Every average lies between the smallest and the largest reading,
and lo itself always qualifies, so the search never returns something that is not an achievable
average.
## The boundary that breaks a careless implementation
The running minimum must lag by exactly k. At index j the smallest prefix considered must be
over i <= j - k, not i <= j; taking the minimum over everything allows runs shorter than
k and reports averages that are too high. The log 1 -1 1 -1 1 -1 1 with k = 2 answers
0.333333, but a sweep that forgets the lag answers 1, taking a single element.
The second is negative readings. Starting lo at 0 rather than at min(a) breaks every log whose
readings are all negative.
## Related problems
Problem 807 uses the identical subtract-the-candidate trick on a ratio of two sums, and problem 806 searches a real threshold with a counting check instead.
## Cost
Time O(100 * n). Space O(n).
Constraints - `1 ≤ k ≤ n ≤ 100000` - `-10^4 ≤ a[i] ≤ 10^4` - every answer is at least `10^-9` away from a halfway rounding point at 6 digits
Input
The first line contains two integers n and k.
The second line contains n integers a[0] ... a[n-1], the readings in order.
Output
Print the largest average over contiguous runs of at least k readings, with exactly 6 digits after the decimal point, in plain fixed notation and never in exponent form, alone on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.