530 - Binomial Showdown

[10153EN]

From your code:

for(i=n;i>n-k;i--)
data=1;

where n and k are the inputs. However your size of array data is 141 only (I donno why is this number )
And actually n and k can be larger, as the problem description said n >= 1 but does not has upper limit. For example n and k can be equal to 2147483647.

[hank]

Thanks!!

[naushad]

can anyone tell me why my 530 is giving runtime error
regards,
naushad:-(

[naushad]

can anyone tell me why 520 is giving me run time error......
regards,
naushad:-(

[shahriar_manzoor]

With the given info I can only say that run time error occurs when you access outside your array boundary or divide by zero.

[Artine]

Can anyone offer any tips for solving problem 530? I first tried the factorial method for binomial coefficients, but that obviously was impossible because the numbers were way too large to store even in a 64 bit long long. Then I tried computing Pascal's Triangle, but that didn't work because the inputs were too big to create the array. Any suggestions?

[turuthok]

Hello ... I have a simple idea (eventhough I'm sure it still needs to be improved) ...

Let's put one example to make things clear a little bit ... consider:

-> 100 C 30 = ????

so you would have to calculate 100! / (30! x 70!)

You can definitely cross out 70! (I pick the larger number) since we know we can write it as:

100 x 99 x 98 x .... 71 x 70!
---------------------------------
30! x 70!

You'll end up with:

100 x 99 x 98 x ... 71
-------------------------
30 x 29 x 28 x ... x 1

For this, you can have one integer array that contains: {100, 99, .. 71 } and another array contains {30, 29, 28, ... 1} ... Previously we pick larger number (70 instead of 30) to handle less elements in both arrays.

Now the goal is to iterate in such a way that your second array will contain all ones. { 1, 1, 1 ... } ...

I think we stop here so you'll still have some fun writing your solution

Oh yes, BTW, you can also try solve similar problems 10338 - Mischievous Children.

-turuthok-

[turuthok]

Recent public-contest has this similar problem but definitely above methods won't stand a chance ...

Given some constraints, we'll still be able to improve the running time quite a bit. Watch for the new problems posted in Volume CIII.

-turuthok-

[haaaz]

My suggestion:

1. Use double.
2. Multiplies and divides at the same time to reduce run time.
3. nCr(n,r) == nCr(n,n-r)
So make r as large as possible to reduce iteration.

Easy problem, right?

[Artine]

Yes, you'd think it would be easy, but it times out. It handles cases where num1 == num2 and where num2 == 1 to save time. It multiplies and divides simultaneously. It reduces the denominator to make that faster. What other tricks are there to speed this up? TIA.

[mido]

This gives TLE...any tips:
[cpp]
#include <iostream.h>

long num,k,i;
double result;

void main()
{
while (!cin.eof() && cin>>num>>k && num>=1 && k>=0)
{
result=1;
for (i=1;i<=k;i++)
{
result*=num;
result/=i;
num--;
}
cout<<long(result)<<endl;
cout.flush();
}
}
[/cpp]

[Red Scorpion]

Hi, Mido

Consider How if the input is
2147483648 2147483648,

You do the iteration from 1 to 2147483648, it is very consuming time.
Try to change your algo.

GOOD LUCK.
RED SCORPION

[mido]

I got AC by changing the value of k so as to decrease the number of iterations..just a little combination trick (a friend of mine did it for me, actually)...thanks (btw,from TLE to zero seconds..whoof)

[lendlice]

[cpp]//530
#include<stdio.h>
main()
{
double n=0,m=0,i=0,c=0;
while(scanf("%lf%lf",&n,&m)==2)
{
if(n==0&&m==0)
break;
c=n;
m=n-m;
if(n!=m)
{
for(i=1;i<m;i++)
c=c*(n-i)/(i+1);
}
printf("%.lf\n",c);
}
}[/cpp]
i got tle
anyone can help me

[Hisoka]

I don't know there are input like this or not.

Code: Select all

10000 1
100000 1
1000000 1

If there are input like this your program will produce TLE.

I just think this about your TLE.