When to start over
A puzzle solver is a Las Vegas algorithm: if it stopped, the answer is right, but how long it runs depends on the random numbers. It was run n times with independent random numbers, and the number of steps each run took was recorded; runs that had not finished in L steps were cut off.
Now the solver is to be run like this: if a run has not finished in t steps, cut it off and start a new one, until some run finishes. Assuming that the run time is distributed as in the recorded sample, choose t from 1 to L for which the mean total number of steps until an answer is smallest, and print this mean. For the sample it equals
$$\frac{\sum_i \min(T_i,\ t)}{\#\{i : T_i \le t\}},$$where cut-off runs count as longer than L. If no run finished, print −1.
Input
The first line holds n and L (1 ≤ n ≤ 200,000, 1 ≤ L ≤ 109). The second holds n numbers Ti: the number of steps of a run from 1 to L, or −1 if the run was cut off.
Output
The smallest mean number of steps with a relative error of at most 10−6, or −1.
Examples
Example 1
5 100 3 5 -1 4 -1
7.333333
Example 2
4 100 10 10 10 11
10.250000
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 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 formula is given, but t is any number from 1 to L, and L goes up to a billion. How does the fraction behave as t grows between two neighbouring values of the sample?
2Hint 2
Between neighbouring values the denominator, the number of runs that finished no later than t, does not change, while the numerator grows. So the candidates are only the run lengths themselves. How can the numerator be computed quickly for each of them?
3The idea
Why the formula is right is proved in the article: the number of runs until the first success is geometrically distributed, and the mean total time is E[min(T, t)] / P(T ≤ t). On a segment between neighbouring lengths vk ≤ t < vk+1 the denominator is constant, and the numerator grows by the number of runs not yet finished for each step of t. So the minimum is reached at the left end, at t = vk, and values of t below the shortest length are not allowed: the denominator is zero.
Sort the finished runs. For t equal to the k-th smallest length (the last of those equal to it), the numerator is the sum of the first k lengths plus t times the number of all the other runs, including the cut-off ones: a cut-off run also ran for t steps before it was stopped. This is the trap of the problem.
4Walkthrough
A sort, a pass with a prefix sum, the minimum of the fractions. Equal lengths must be handled together: the denominator is the number of all runs of length no more than t.
The fourth test is real runs of the sudoku solver from the article: 300 runs cut off at 20,000 steps. The best cutoff gives 5685 steps per solution on average, close to the measurement in the article, where t = 2000 gave 5635 on another sample of 400 runs.
4+Solution
5Complexity
O(n log n) for the sort, the rest O(n).
6Common mistakes
- Cut-off runs are free. If they are not charged t steps, restarts seem more profitable than they are: on the first example you get 4 instead of 7.333.
- Trying all t from 1 to L. With L = 109 this is too slow.
- Equal lengths one at a time. If for t = v only part of the runs of length v is counted, the denominator is too small and the fraction wrong (the seventh test).
- 32 bits. In the eighth test the numerator is about 2·1014.