Internet Problem Solving Contest

• Correct output – C1
• Correct output – C2
• C++ program solving both data sets
• Another C++ program solving both data sets

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.