Best Sums

admin, can you please provide one more test case for this problem because it seems that the answer is always k.

plz clear the problem...what is mean of smallest partial sum modulo P that is at least K.

minimize the value of sum such that sum % p is atleast k

Can some one please tell me why my program is throwing a compilation error. I am using Bloodshed Dev - CPP to compile the code on my machine and it compiles just fine.

Please check the FAQ and http://www.codechef.com/wiki

Is it an ad hoc sequence or are the terms related to each other in some way.

In the example it seems like the terms are just arbitrary....

No, they are not related in any way.

What if the sum of ALL numbers are smaller than K? Do we not print anything?

That won't happen.

My output matches with the obvious brute force solution's for more than 1000 cases. Since nobody has managed to submit a correct solution, are you guys sure there's nothing wrong with the control mechanism?

My output matches with the obvious bruteforce solution for 100K cases now!!! Here is the brute force code:

#include <iostream>
#include <cstdlib>

int main() {
unsigned long N,K,P; scanf("%lu %lu %lu",&N, &K, &P);
unsigned long sums[N+1], sum, num, prev=0;

if(K>=P || N==0) exit(1);

sums[0] = 0;
for(unsigned long i=1; i<=N; i++) {
scanf("%lu", &num);
num = num %P;
if(num > (P-prev)) {
// overflow
sum = prev -(P -num);
} else
sum = prev + num;
prev = sum;
sums[i] = sum;
}
unsigned long tmp;
unsigned long resultSum=P, resultI=0, resultJ=0;

for(unsigned long j=1; j<=N; j++) {
for(unsigned long i=1; i<=j; i++) {
unsigned long add = P -sums[i-1];

if(add > (P-sums[j])) {
// overflow
tmp = sums[j] -(P -add);
} else
tmp = add +sums[j];

if(tmp>=K && (tmp < resultSum)) {
resultSum = tmp;
resultI = i;
resultJ = j;
}
#if 0
printf("%lu: (%ld, %ld) => ", tmp, i, j);
printf("%lu: (%ld, %ld)n", resultSum, resultI, resultJ);
#endif
if(resultSum == K) break;
}
if(resultSum == K) break;
}
if(resultSum != P) printf("%lu: (%ld, %ld)n", resultSum, resultI, resultJ);

return 0;
}

i have submittted solution in ,NET. And i am getting "Time limit exceeded" error.

I am sure it is not somehing .NET causing slowness. But still want to confirm.

Can someone from Admin confirm this.

Thanks.

Can you explain this again:

Here N = 7. Suppose K = 2 and P = 17. Then, the answer is 2 because 11+16+26 = 53 and 53 mod 17 is 2. On the other hand, if K = 0 the answer is 0 since 15 + 11 + 16 + 26 = 68 and 68 mod 17 is 0.

Please let me know why the answer is 2 and 0 respectively.

Which part of that exactly don't you understand?

Here is another example. Suppose K=1, but the rest of the example is the same. No matter which partial sum you take, you'll find it is impossible to get a sum of 1 mod 17. It is possible to get 2 however in the same way as above (11+16+26 == 2 mod 17). So the answer is 2 again.

If a sum of 2 mod 17 wasn't possible, then you would need to see if 3 mod 17 was possible, and so on. Until you've found the smallest number >= K for which there is a partial sum adding to that, mod 17.

Thanks a lot Stephen; its clear now. One final question. Should the numbers we take be sequential wrt the input?

In the example, the sequence is " 12 13 15 11 16 26 11 "; Can we take a set as 12,15? Also how many numbers can form a set?

You are told that in the first line of the problem. (It should say 1 <= i <= j <= N, of course).

Are you %100 positive that there is nothing wrong with the judge? No successful submissions yet and i am sure my code works fine!

hey admin.. i've submitted the code 8 times, different optimisations done at every attemt, they work fine at my place.. but all of'em show runtime error.. and of type- others.. even the help section is not of much help.. i am coding in c and the upper limit of n is 1,00,000 so i can't use an integer.. i am assuming that the server is not able to allocate that much size to an array.. so i reduced it.. but still , the same error every time.. please help me out.. coz its really very frustrating

Is it possible for you guys to give us the test case that fails our code? You are possibly testing against a very interesting corner case. Unfortunately, I have no idea what that corner case is. I am testing against the exhaustive solution with random input files of the largest possible size, and I always get an agreement between the two solutions. Now that algol has a succesful submission, I have faith in your testing procedure. However, looking for what is wrong in our code without the test case that fails the code is like looking for a needle in a hay stack. You guys should return the failing test case at least in the case of practice problems. You have a great website, and this way you can make it more useful. Thanx in advance.

I tried optimizing a lot but doesnt work. I get TLE.

There are n²/2 sums. Shouldn't we check all of them (of course stopping inbetween if we are already at least possible answer = K)? That leads to an O(n²) algorithm and I guess thats slow for this problem.

Is there any way to get rid of using the modulo operator in this problem? That might be slowing things down.

A correct algorithm does not need to check all n^2/2 sums.

Hi

Just one question..

Suppose sequence is 12 13 15 11 16 26 11 19

K = 2 and P = 17 Then also result will be 2 and Partial sum will be 19

Am I thinking Correct?

I submitted a solution in python and got this error

:( internal error occurred in the system

The solution works fine on my system. Is there smthing that I am missing while submitting codes in Python

Can You Tell Error in this....it gives correct results logically and to all your test cases....

#include<stdio.h>

int main()

{int n,k,i,j,p,a[10000],sum,ans;

scanf("%i %i %i",&n,&k,&p);

for(i=0;i<n;i++)

{scanf("%i",&a[i]);}

for(i=0;i<n;i++)

{sum=a[i];

for(j=i+1;j<n;j++)

{sum=sum+a[j];

if( (sum%p) < ans && (sum%p) >= k)

{ans=sum%p;}

}

}

printf("%i",ans);

}