Math solution but still not enough fast

So the task is to determine whether the sum C[n][1]+C[n][2]+...+C[n][k] is greater than X and do it FAST.

I can't do it fast.

#include <stdio.h>

typedef unsigned long long huge;

huge calc(int n, int k){

huge Up=k, Dn=0;

while(Up-Dn>1){

huge Md=(Up+Dn)/2;

huge cnt=0;

long double aux=1;

for(int i=1; cnt<k && i<=n; ++i){

aux*=(long double)Md+1-i;

aux/=i;

cnt+=aux;

}

if(cnt<k)

Dn=Md;

else

Up=Md;

}

return Dn+1;

}

int main(){

huge n,k, ans[1000];

int tot=0;

scanf("%llu %llu",&n,&k);

while(n>0 && k>0){

ans[tot++]=calc(n,k);

scanf("%llu %llu",&n,&k);

}

for(int i=0; i<tot; ++i)

printf("%llu\n",ans[i]);

return 0;

}

Re: Math solution but still not enough fast

With that code you can solve version 1 in 0.031 sec and even in 0.001 sec if precomputed table of binomials is used.

But in V2 it runs in 0.51 sec on testcase 2!

Re: Math solution but still not enough fast

Try

Update from:

huge calc(int n, int k){

To:

huge calc(huge n, huge k){

And one more trick:

ans[tot++]=calc(n,k);

replace by ans[tot++]=calc(min(60,n),k);

Re: Math solution but still not enough fast

Thanks

See you AC

I am applied your suggestions to my program

But something went wrong again

Then I replaced magic constant 60 with 30000 and got 0.4999 sec running time but WA#2

Re: Math solution but still not enough fast

Re: Math solution but still not enough fast

AC Python2.

Re: Math solution but still not enough fast

Finally AC with C++. Thanks!