# BEARSEG - Editorial

Practice

Contest

Author: Kamil Debowski

Tester: Lewin Gan

Editorialist: Misha Chorniy

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.

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

6 Likes

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 ?

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

2 Likes

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

arr[-1]=0; Is it legally?

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 )
3 Likes

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.

1
5 5
5 5 5 5 5

1 Like

just 5 5 0 0 0 0 0? what about p?

Why N log^2 N? For me, it’s N log N

Got it. 1 5 5 5 5 5 5 5 it is.

bin.search in set is log^2, is not it?

No, log(N)

1 Like

Ok, thanks

Can someone please provide a more simple explanation for Subtask 3? I can’t understand anything.

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 )

If you don’t understand, say me!

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

1 Like

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=p-1"
Can you please elaborate what you mean?
I really appreciate the help, buddy

ok, let’s count the sum on prefixs! Then the sum of every subarray is the sum on prefix(0,r)-prefix(0,l-1)!

//