## IPSC 2006

## Solution to Problem C – Counting Subsequences

The easy problem was pretty simple – all the numbers in the input
were positive, and thus a simple linear search was possible.

For a program that solves both inputs we had to be a bit more clever.
Let **s**_{k} be the sum of the first **k** numbers
of the given sequence. Then the sum of a subsequence
that starts with the **i**-th and ends with the **j**-th term
of the given sequence is equal to **s**_{j} - s_{i-1}.
(The numbers **s**_{k} are called *prefix sums*.)

In other words, the sum of this subsequence is 47 if and only if
**s**_{j} = s_{i-1} + 47.

Thus the answer is the count of pairs **[i,j]** such that **i<j**
and **s**_{j} = s_{i-1} + 47.

One possibility how to compute this value is to process the elements of the
sequence one by one, keep the current prefix sum and use an efficient set
or map data structure to compute the number of interesting subsequences
that end at the current position. (E.g., if the current prefix sum is 49,
we are interested in how many previous prefix sums were equal to 49-47=2.)

Another possible solution is to sort the pairs **[s**_{j},j].
From the sorted array the answer can be computed in linear time.