BEARSEG - Editorial

Practice

Contest

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.

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

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

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

@glebodin why are u adding p???

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.

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. :slight_smile:

refer to this code :-
O(nlogn) solution

How to ask questions!?

3 Likes

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 ?

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

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<n;i++)
		{
			arr[i]=sc.nextInt();
			sum+=i;
		}
		sum+=n;
		int a[]=new int[sum];
		int z=0,k=1,s=0;
		while(k<=n)
		{
			for(int i=0;i<=n-k;i++)
			{
			    s=0;
				for(int j=0;j<k;j++)
				{
				    
					s=s+arr[i+j];
				}
				a[z]=s%p;
				z++;
			}
			k++;
		}
		int max=a[0];
		for(int i=0;i<sum;i++)
		{
			if(max<a[i])
				max=a[i];
		}
		int count=0;
		for(int i=0;i<sum;i++)
		{
			if(max==a[i])
				count++;
		}
		System.out.println(max+" "+count);
	}
}

}

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.

2 Likes

can you explain with some example

can you tell me where my code is going wrong??

My O(n \log^2(n)) solution got accepted after some slight optimizations (in 1.94 s). https://www.codechef.com/viewsolution/13411903

How is this problem different from “http://stackoverflow.com/questions/31113993/maximum-subarray-sum-modulo-m” problem?

1 Like

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.

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