BEARSEG - Editorial

editorial
, , , , ,
2

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 ?

3

Why am I getting wrong answer during final submission?

Here is my solution: lcMMYw - Online C++ Compiler & Debugging Tool - Ideone.com

On Codechef: CodeChef: Practical coding for everyone

2 Likes
4

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: Y8l5mm - Online C++0x Compiler & Debugging Tool - Ideone.com )
3 Likes
5

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

6

@glebodin why are u adding p???

7

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.

8

Can someone please tell me why I am getting a wrong answer? I really can’t tell.
Link for code: HYU7dB - Online C++0x Compiler & Debugging Tool - Ideone.com

Any and all improvements are welcome. :slight_smile:

9

refer to this code :-
O(nlogn) solution

10

How to ask questions!?

3 Likes
11

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 ?

12

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

13

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);
	}
}

}

14

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
15

can you explain with some example

16

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

17

My O(n \log^2(n)) solution got accepted after some slight optimizations (in 1.94 s). CodeChef: Practical coding for everyone

18

How is this problem different from “algorithm - Maximum subarray sum modulo M - Stack Overflow” problem?

1 Like
19

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.

20

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

21

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