Author: Kamil Debowski Difficulty:EasyMedium PreRequisites:None Problem StatementGiven a sequence $A$ and a number $P$. Define score for nonempty consecutive subsequence as a sum of all elements in it by modulo $P$. You need to find nonempty 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:
Complexity of this algorithm is $O(N^3)$ per test case. Subtask 2For 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[i1]
for left = 1..N:
for right = left..N:
sum = (S[right]  S[left1]) % P //S[right]=A[1]+....+A[right]
//S[left1]=A[1]+....+A[left1]
//S[right]S[left1]=A[left]+...+A[right]
if sum > maxSum:
maxSum = sum
countMaxSum = 0
if sum == maxSum:
countMaxSum += 1
print maxSum, countMaxSum
Subtask 3Let'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[left1]) % 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..right1 S[right]%P==(maxSum+S[i])%P, i = 0..right1 (S[right]maxSum)%P==S[i]%P, i = 0..right1 We need to quickly calculate how many values $S[i]%P$ on prefix $0..right1$ 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..right1$, 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 P1.
This table responds for every y(first row) value of (xy)%P, we need to find maximal (xy)%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..right1. 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 = 30=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 70=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. (47)%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[i1]) % 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 Please feel free to post comments if anything is not clear to you.
This question is marked "community wiki".
asked 29 Apr '17, 15:21

Ok, but i think your solution is too hard for novice, so let's do this 1) let's go from i=0 to n and add a[i] to sum 2) then we need the first number >=(sum+1+p)%p because (sum(sum+1)+p)%p=p1; so let's make bin.search to the set for number>=(sum+1+p)%p so it's work Nlog(N) (link: https://ideone.com/Y8l5mm ) answered 29 Apr '17, 23:56
Why N log^2 N? For me, it's N log N
(30 Apr '17, 00:02)
bin.search in set is log^2, is not it?
(30 Apr '17, 00:09)
1
No, log(N)
(30 Apr '17, 00:11)
Ok, thanks
(30 Apr '17, 00:12)
1
@glebodin: It is $\mathcal{O}(log N)$. Underlying structure in set is balanced binary search trees (BBSTs). In BBST, the following property is held for each node. For each node $x$, the value at its left child is $\leq$ the value at $x$, and the value at the right child will be $\geq$ value at $x$. So, you can find first element greater than or equal to some value by making a comparison at each node starting from root and deciding which child to go, to the left or to the right. The max number of comparisons will equal to the height of the tree, which is $\mathcal{O}(log N)$ for BBST.
(30 Apr '17, 15:13)

Answer is hidden as author is suspended. Click here to view.
answered 30 Apr '17, 10:35

Why am I getting wrong answer during final submission? Here is my solution: http://ideone.com/lcMMYw On Codechef: https://www.codechef.com/viewsolution/13413428 answered 29 Apr '17, 23:47
arr[1]=0; Is it legally? :)
(29 Apr '17, 23:53)
I thought that too. But it's working everywhere (GCC, Codechef Ide, Ideone), doesn't it? But during submission on Codechef, it throws WA. I'm looking for alternative of that but as of now, please let me know if I've done something wrong there.
(29 Apr '17, 23:57)
1
1 5 5 5 5 5 5 5 Your solution output 20, but answer is 15, your process empty segments
(29 Apr '17, 23:58)
just 5 5 0 0 0 0 0? what about p?
(30 Apr '17, 00:01)
Got it. 1 5 5 5 5 5 5 5 it is.
(30 Apr '17, 00:08)

These editorials are so hard to understand. 8 out of 10 times I am not able to understand what the editorial is trying to say and end up wasting a lot of time. Please make editorials more beginner friendly and explain the intuition behind the concepts well before diving into the solution. answered 30 Apr '17, 13:39

How is this problem different from "http://stackoverflow.com/questions/31113993/maximumsubarraysummodulom" problem? answered 30 Apr '17, 18:49

Can someone please provide a more simple explanation for Subtask 3? I can't understand anything. answered 30 Apr '17, 00:14
Ok, but i think your solution is too hard for novice, so let's do this 1) let's go from i=0 to n and add a[i] to sum 2) then we need the first number >=(sum+1+p)%p because (sum(sum+1)+p)%p=p1; so let's make bin.search to the set for number>=(sum+1+p)%p so it's work Nlog(N) (link: https://ideone.com/Y8l5mm )
(30 Apr '17, 00:16)
If you don't understand, say me!
(30 Apr '17, 00:16)
I don't know anything about sets/maps/pairs. I can't quite understand your code. " we need the first number >=(sum+1+p)%p because (sum(sum+1)+p)%p=p1" Can you please elaborate what you mean? I really appreciate the help, buddy :)
(30 Apr '17, 00:23)
ok, let's count the sum on prefixs! Then the sum of every subarray is the sum on prefix(0,r)prefix(0,l1)!
(30 Apr '17, 00:35)
That's about subtask 2, I understood it completely.
(30 Apr '17, 00:38)
Then let's go from prefix(0,0) to(0,n1)! Let's firstly find the most optimal prefix,that give the closest to p number and then add new prefix to our list of prefixes !
(30 Apr '17, 00:38)
ok, what is the most optimal prefix? It's the prefix, which gives sum on prefix(0,x)+1 or more! ( because sum on prefix(0,x)(sum on prefix(0,x)+1) gives 1, which is equal to p1)
(30 Apr '17, 00:40)
then how to save all prefixes 1) vector, but it's n^2 2) we can save the amount of every prefix in array,but it's give p memory and pn time; 3) then you can do set! what is your language(c++,java, pascal)?
(30 Apr '17, 00:45)
showing 5 of 8
show all

@glebodin why are u adding p??? answered 30 Apr '17, 01:09
it's the habit, it's not Obligated
(30 Apr '17, 01:11)
and why we are adding 1? what does this line means (sum(sum+1)+p)%p=p1?? tell me the meaning /significance of this line???
(30 Apr '17, 01:16)
Look, what's the max amount of sum(l,r)%p? It's p1! So we have that sum on prefix (0,r)=x, than sum on prefix(0,r)  sum on prefix(0,l1)=p1 =>  sum on prefix(0,l1)=p1  sum on prefix(0,r) => sum on prefix(0,l1)=1 + sum on prefix(0,r)  p =>sum on prefix(0,l1)=1 + sum on prefix(0,r)
(30 Apr '17, 01:22)

I wrote a brute force solution but it gives WA. I know it would give TLE but I just wanna know whats wrong in this code.link Please help. answered 30 Apr '17, 01:16
1
s += a[x] % p, this line, if p = 1000000000, and array = {999999999, 999999999, ..., ...}, then value s will overflow
(30 Apr '17, 01:41)
how should it be for the code to produce AC?
(30 Apr '17, 01:55)
at first, use long long or be very neat with modulo p
(30 Apr '17, 02:08)
Thank you.
(30 Apr '17, 02:17)

Can someone please tell me why I am getting a wrong answer? I really can't tell. Link for code: http://ideone.com/HYU7dB Any and all improvements are welcome. :) answered 30 Apr '17, 01:27
1 3 1000000000 1000000000 1000000000 1000000000 Your solution output 0 5, but must be 0 6. Think about it
(30 Apr '17, 01:34)

Answer is hidden as author is suspended. Click here to view.
answered 30 Apr '17, 09:19

How we will justify this :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 maxSummaxSum ? answered 30 Apr '17, 10:50

@glebodin, you gave a wonderful solution, but if you don't mind, can you please explain your solution again in detail, specially this part: "2) then we need the first number >=(sum+1+p)%p because (sum(sum+1)+p)%p=p1; so let's make bin.search to the set for number>=(sum+1+p)%p". Thanks in advance. answered 30 Apr '17, 12:23

why my code is giving wrong answer
} answered 30 Apr '17, 13:15

can you tell me where my code is going wrong?? http://ideone.com/3P9PGB answered 30 Apr '17, 18:22
1 3 1000000000 1000000000 1000000000 1000000000 Your solution output 0 5, but must be 0 6. Think about it(overflows sum[n]>2^32)
(30 Apr '17, 19:10)

My $O(n \log^2(n))$ solution got accepted after some slight optimizations (in 1.94 s). https://www.codechef.com/viewsolution/13411903 answered 30 Apr '17, 18:28

What's the significance of writing "P(not necessarily prime)" in the question? one implication I thought that instead of taking log(n) steps[map operation to find], one can iteratively search for the value from "left" because the numbers are not spaced that much as compared to situation where P is prime. answered 01 May '17, 00:47

Really happy to see editorialist actively helping users. Really appreciate it @mgch :)