BEARSEG - Editorial

editorial
, , , , ,
21

That’s about subtask 2, I understood it completely.

22

Then let’s go from prefix(0,0) to(0,n-1)! 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 !

23

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 p-1)

24

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)?
25

@glebodin why are u adding p???

26

it’s the habit, it’s not Obligated

27

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???

28

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.

29

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

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:

31

1
3 1000000000
1000000000 1000000000 1000000000
Your solution output 0 5, but must be 0 6. Think about it

32

s += a[x] % p, this line, if p = 1000000000, and array = {999999999, 999999999, …, …}, then value s will overflow

1 Like
33

how should it be for the code to produce AC?

34

at first, use long long or be very neat with modulo p

35

Thank you.

36

refer to this code :-
O(nlogn) solution

37

How to ask questions!?

3 Likes
38

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 ?

39

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

40

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

}