Internet Problem Solving Contest

IPSC 1999

Solution to Problem G – Rain

Suppose we have the predictions of the meteoronome pre-computed in the array a[1], a[2], ..., a[N]. We can rephrase the problem as follows: "find the smallest K, such that there is a subsequence a[i], a[i+1], ..., a[j] of length K+1 with sum greater than M". We will maintain the indices i,j and sum s in a way, that preserves these properties:

First, we initialize both i and j to 0. Then, we increase j until the sum s is greater than M (or j reaches the end of the sequence). Next, we increase i until the sum s is less or equal to M. At this point, all three stated properties hold. The sequence a[i], ..., a[j] is a candidate for the desired shortest subsequence. If it is shorter than any subsequence found so far, we have a new shortest subsequence. This way we keep increasing j and i until j reaches the end of the sequence N.

Realize, that it is not necesary to store values a[1], a[2],..., a[N] in an array - indices i and j are always increased by one and we need to know only values a[i] and a[j], which can be calculated form the previous values.