Author: Kamil Debowski
Tester: Lewin Gan
Editorialist: Misha Chorniy
Difficulty:
Easy-Medium
Pre-Requisites:
None
Problem Statement
Given a sequence A and a number P. Define score for non-empty consecutive subsequence as a sum of all elements in it by modulo P. You need to find non-empty consecutive subsegment with the maximal score, and calculate how many subsegments with this score are.
Subtask 1
N is not more than 100. Next solution should pass, iterate over left bound of segment and right bound of segment and calculate sum of elements between left bound and right bound by modulo P. Let’s create two auxillary variable maxSum and countMaxSum. After calculating sum, we should update values of maxSum and countMaxSum. Following code helps to understand:
countMaxSum = maxSum = 0
for left = 1..N: //iterating over left bound
for right = left..N: //iterating over right bound
sum = 0
for i = left..right: //calculating sum on segment
sum = (sum + A[i]) % P
if sum > maxSum:
maxSum = sum
countMaxSum = 0
if sum == maxSum:
countMaxSum += 1
print maxSum, countMaxSum
Complexity of this algorithm is O(N^3) per test case.
Subtask 2
For this subtask O(N^3) algorithm works too long. We need to invent something smarter, as a variation, we can calculate sum on segment in O(1) with O(N) preprocessing, this technique called partial sum or prefix sum. This trick allows decrease runtime from O(N^3) to O(N^2).
S[0] = 0
for i = 1..N: //preprocessing
S[i] = A[i] + S[i-1]
for left = 1..N:
for right = left..N:
sum = (S[right] - S[left-1]) % P //S[right]=A[1]+....+A[right]
//S[left-1]=A[1]+....+A[left-1]
//S[right]-S[left-1]=A+...+A[right]
if sum > maxSum:
maxSum = sum
countMaxSum = 0
if sum == maxSum:
countMaxSum += 1
print maxSum, countMaxSum
Subtask 3
Let’s iterate over right bound of segment, and try to quickly find left bounds with maximal score. Consider more attentively this line of code (S[right] - S[left-1]) % P, in our new algorithm we want to fix variable right and find out maximal score, when segment is ended in right and also calculate the number of left bounds where it is carried out. Assume that maxSum is the maximal score over all segments which is ended in right, how to calculate number of segments which are ended in right and has the same score?
(S[right]-S[i]) % P == maxSum, i = 0…right-1
S[right]%P==(maxSum+S[i])%P, i = 0…right-1
(S[right]-maxSum)%P==S[i]%P, i = 0…right-1
We need to quickly calculate how many values S[i]%P on prefix 0..right-1 are equal (S[right]-maxSum)%P, for this subproblem. Because of the fact that P can be up to 10^9 we cannot use array of size P, where number x will store frequency of element x on prefix. We need to use some data structure, likely modern programming languages has data structures for such subproblem, map in C++, TreeMap in Java and etc. With these DS, we can find frequency on prefix in O(log N) time. But how to find maxSum? Assume that x = S[right]%P, and we know about all the values S[i]%P on prefix 0..right-1, let they be in some set Z. Z = {S[0] P, S[1] P, S[2] P, ..., S[right - 1] P]}.
maxSum can’t exceed P, maximal value of maxSum can be P-1.
0 1 2 3 4 ...... x-1 x x+1 x+2 ... P-1 P x x-1 x-2 x-3 x-4 ..... 1 0 P-1 P-2 .. P-1-x P-x
This table responds for every y(first row) value of (x-y)%P, we need to find maximal (x-y)%P, when we know x=S[right]%P, and y can be any value from the set Z.
For example, let we have set Z = {0, 4, 7} and x = 3, P = 9, then maximal sum is (3 - 4) 9 = 8. For $x = 7$, maximal sum is (7 - 0) 9 = 7
We need to find smallest number which is more than x and less than P and lies in Z, if there are no such numbers, we need to find smallest number in Z. Difference between x and that element modulo P is the maxSum.
Consider next example:
N = 4, P = 8
A = {3, 4, 5, 6}
At first, calculate partial sums:
S = {0, 3, (3 + 4) 8, (3 + 4 + 5) 8, (3 + 4 + 5 + 6) % 8}
S = {0, 3, 7, 4, 2}
Let’s iterate right bound from 1 to N, and maintain a set Z where for each element we will maintain frequency on prefixe 0…right-1. Initially Z = {(0, 1)}, we have only one element S[0] = 0.
First step, x=S[1]%8=3, do we have in Z x+1=4? No. Do we have in Z x+2=5? No. 6? No. 7? No. We have 0, therefore current maxSum = 3-0=3, countMaxSum = 1.
Add x into the Z, Z = {(0, 1), (3, 1)}
Second step x=S[2]%8=7, Do we have 0? Yes. Update maxSum with value 7-0=7(for the segment A[1…2]), countMaxSum = 1. Z = {(0, 1), (3, 1), (7, 1)} now.
Third step x=S[3]%P=4. Do we have 5? No. 6? No. 7. Yes. (4-7)%8=5, it’s less than maxSum. Z = {(0, 1), (3, 1), (4, 1), (7, 1)} now.
Fourth step x=S[4]%P=2. Do we have 3? Yes. Update countMaxSum = 2. Segment A[2…4], gives 7=(S[4]-S[1])%P
Hence, maxSum is 7 and countMaxSum = 2.
S[0] = 0
for i = 1..N:
S[i] = (A[i] + S[i-1]) % P
Z = {}
Z[0] += 1
for right = 1..N:
x = S[right] % P, y = 0
if Z.upper(x) != empty
y = Z.upper(x)
else
y = Z.minElement()
sum = (x + P - y) % P
if sum > maxSum:
maxSum = sum
countMaxSum = 0
if sum == maxSum:
countMaxSum += Z[y] //Z[y] - frequency of element y
Z[x] += 1 //adding element S[right]%P in Z
print maxSum, countMaxSum
Complexity of the algorithm above is O(N log N). Don’t forget about 64bit type for the number of segments with maximal score.
Solution:
Setter’s solution can be found here
Tester’s solution can be found here
Please feel free to post comments if anything is not clear to you.
