ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1597. Chernobyl’ Eagle on a Roof. Version 2

Math solution but still not enough fast
Posted by Mahilewets 17 Apr 2017 17:34
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
Posted by Mahilewets 17 Apr 2017 17:44
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
Posted by Tolstobrov Anatoliy[Ivanovo SPU] 10 May 2017 20:10
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
Posted by Mahilewets 10 May 2017 22:01
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
Posted by Mahilewets 19 May 2017 14:32
My current WA#4 C code.
http://ideone.com/KwNNiu
Re: Math solution but still not enough fast
Posted by Mahilewets 19 May 2017 14:50
AC Python2.
Re: Math solution but still not enough fast
Posted by Mahilewets 19 May 2017 15:49
Finally AC with C++.  Thanks!