Internet Problem Solving Contest

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 sk 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 sj - si-1. (The numbers sk are called prefix sums.)

In other words, the sum of this subsequence is 47 if and only if sj = si-1 + 47.

Thus the answer is the count of pairs [i,j] such that i<j and sj = si-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 [sj,j]. From the sorted array the answer can be computed in linear time.