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). CodeChef: Practical coding for everyone
How is this problem different from “algorithm - Maximum subarray sum modulo M - Stack Overflow” 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
arr[-1]=0; Is it legally? 
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
Your solution output 20, but answer is 15, your process empty segments
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