PROBLEM LINK
DIFFICULTY
HARD
PREREQUISITES
PROBLEM
You are given an array of N positive integers. There are N+1C2 sub-arrays of this array. Find the number of unique sums possible among all the possible sub-arrays.
QUICK EXPLANATION
Although the problem statement isn’t as direct as the problem description used above, it is very easy to come to the conclusion that this is indeed what the problem to be solved is.
The limits to the problem were given rather innovatively as
1 ≤ N * S ≤ 4 * 1010
Where S is the sum of all the numbers.
Considering all the numbers are positive, the real limit on N is hence
1 ≤ N ≤ 200,000
We note that S can vary greatly as N varies and hence we cannot solve this problem for all values of N under the same algorithm. We break our solution into 3 different methods meant to solve the problem for different values of N.
EXPLANATION
1 ≤ N ≤ 2,000
For this limit of N
- The number of sub-arrays to be considered are at most 2,001,000
- The value of the sums can be at most 40,000,000,000 (for N = 1)
We can generate all the sums and eliminate the duplicates. We cannot eliminate them using a lookup table because of the possibly large value for the sums.
The complexity of this procedure would be O(N2 log N). The complexity is driven by the procedure to sort before we eliminate the duplicates.
sums = []
for i = 1 to N
value = 0
for j = i to N
value += A[j]
sums.push(value)
sort(sums)
eliminate-duplicates(sums)
2,000 < N ≤ 20,000
For this limit of N
- The number of sub-arrays to be considered are at most 200,010,000
- The value of the sums can be at most 20,000,000 (for N = 2000)
We can still generate all the sums and eliminate the duplicates. Note that sorting to eliminate the duplicates can be quite expensive since we are potentially considering over hundred million values. Fortunately, the value of sums has come down within the range to maintain a lookup table!
sums[] = { 0 }
for i = 1 to N
value = 0
for j = i to N
value += A[j]
sums[value] = 1
answer = 0
for i = 1 to MAX_SUM
answer += sums[i]
The lookup table helped us avoid the cost of the sorting step to eliminate duplicates. We still relied upon our ability to iterate over every possible sub-array’s sum. The complexity of this procedure is O(N2 + S).
20,000 < N ≤ 200,000
For this value of N
- The number of sub-arrays to be considered are at most 20,000,100,000
- The value of the sums can be at most 2,000,000 (for N = 20000)
We can no longer iterate over each sub-array because there could be too many of them. But we note that the value of the maximum possible sum is now very manageable. We can use this to our advantage by trying to base our approach completely over the possible values for sums.
Let us consider an array of sums of prefixes
S[i] = sum( A[x] : 1 ≤ x ≤ i )
We wish to find all the possible values generated by
S[j] - S[i]
for each 1 ≤ j ≤ N AND 1 ≤ i < j. This convolution can be generated by the product of the following two polynomials
X = x0 + xS[1] + xS[2] + ... xS[N] Y = x0 + x-S[1] + x-S[2] + ... x-S[N]
The number of terms in the product of X and Y, which have non-zero coefficient and positive power, is the answer we are looking for. To only deal with positive powers in our problem, we can multiply Y with xS[N] and check the coefficients of all the terms xS[N]+1 and above in th resultant polynomial.
The fastest way to multiply two polynomials is using FFT. We can multiply the two polynomials as follows.
fX = FFT(X) fY = FFT(Y) fT = fX . fY (dot product) T = iFFT(fT)
Thus, we can solve this case in O(N + S log S) time.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.
(and once I got the AC there was no incentive to look for more efficient solutions) but I thought that this point was worth mentioning. I am wondering if anyone has other solutions with a guaranteed theoretical time complexity which is good enough to fit the time limit.
I will sneak in some test data for practice section though!