×

# BEARSEG - Editorial

Author: Kamil Debowski
Tester: Lewin Gan
Editorialist: Misha Chorniy

Easy-Medium

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.

$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.

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[left]+...+A[right] if sum > maxSum: maxSum = sum countMaxSum = 0 if sum == maxSum: countMaxSum += 1 print maxSum, countMaxSum 

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.

This question is marked "community wiki".

6★mgch
4451436
accept rate: 20%

1

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

(30 Apr '17, 00:19)

 3 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=p-1; 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 4★glebodin 111●4 accept rate: 0% Why N log^2 N? For me, it's N log N (30 Apr '17, 00:02) mgch6★ bin.search in set is log^2, is not it? (30 Apr '17, 00:09) glebodin4★ 1 No, log(N) (30 Apr '17, 00:11) mgch6★ Ok, thanks (30 Apr '17, 00:12) glebodin4★ 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)
 2 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 63●5 accept rate: 0% arr[-1]=0; Is it legally? :) (29 Apr '17, 23:53) mgch6★ 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) mgch6★ 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)
 2 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 21●1 accept rate: 0% Read my solution, I think it's better for novice! (02 May '17, 13:25) glebodin4★
 1 How is this problem different from "http://stackoverflow.com/questions/31113993/maximum-subarray-sum-modulo-m" problem? answered 30 Apr '17, 18:49 4★raja379 89●2 accept rate: 0% Aren't the problems for Lunchtime supposed to be new? (01 May '17, 16:26) raja3794★
 0 Can someone give mathematical proof for 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. Why it will give the maximal sum ? answered 29 Apr '17, 23:47 497●1●8 accept rate: 15% If we fix x, then maximal possible sum modulo P can be P-1, if y=x+1, if x+1 not in Z, we need to check x+2 for P-2, x+3 ... P-1, after that, if didn't find any number, let's try 0, 1, 2, .., x (29 Apr '17, 23:51) mgch6★
 0 @glebodin why are u adding p??? answered 30 Apr '17, 01:09 164●9 accept rate: 4% it's the habit, it's not Obligated (30 Apr '17, 01:11) glebodin4★ and why we are adding 1? what does this line means (sum-(sum+1)+p)%p=p-1?? 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 p-1! So we have that sum on prefix (0,r)=x, than sum on prefix(0,r) - sum on prefix(0,l-1)=p-1 => - sum on prefix(0,l-1)=p-1 - sum on prefix(0,r) => sum on prefix(0,l-1)=1 + sum on prefix(0,r) - p =>sum on prefix(0,l-1)=1 + sum on prefix(0,r) (30 Apr '17, 01:22) glebodin4★
 0 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 4★ayush933 97●5 accept rate: 0% 1 s += a[x] % p, this line, if p = 1000000000, and array = {999999999, 999999999, ..., ...}, then value s will overflow (30 Apr '17, 01:41) mgch6★ how should it be for the code to produce AC? (30 Apr '17, 01:55) ayush9334★ at first, use long long or be very neat with modulo p (30 Apr '17, 02:08) mgch6★ Thank you. (30 Apr '17, 02:17) ayush9334★
 0 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 accept rate: 0% 1 3 1000000000 1000000000 1000000000 1000000000 Your solution output 0 5, but must be 0 6. Think about it (30 Apr '17, 01:34) mgch6★
 0 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 61●1 accept rate: 0%
 0 @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=p-1; so let's make bin.search to the set for number>=(sum+1+p)%p". Thanks in advance. answered 30 Apr '17, 12:23 1 accept rate: 0%
 0 why my code is giving wrong answer import java.util.Scanner;class codechef1 { public static void main(String args[]) { Scanner sc=new Scanner(System.in); int t=sc.nextInt(); while(t-->0) { int n=sc.nextInt(); int p=sc.nextInt(); int sum=0; int arr[]=new int[n]; for(int i=0;i
 0 can you explain with some example answered 30 Apr '17, 14:26 12●2 accept rate: 0%
 0 can you tell me where my code is going wrong?? http://ideone.com/3P9PGB answered 30 Apr '17, 18:22 1 accept rate: 0% 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) mgch6★
 0 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 1 accept rate: 0%
 0 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 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,722
×83
×82
×74
×21

question asked: 29 Apr '17, 15:21

question was seen: 2,709 times

last updated: 02 May '17, 13:25