## 530 - Binomial Showdown

Moderator: Board moderators

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
Thanks Claudio,

Of course you're first remark is correct! Silly mistake.

As to the 2nd remark, I thought "... just in case!, maybe the
input isn't n, k but k, n". But as you said, that wouldn't cause
this error.

As a third measure I corrected the newline.

And no, I don't have the judge's input data, but a fast
GCD algorithm from Steven Halim's site.

The trouble is, that other programs show the same behaviour. And they
should run at least one or two tenth of a second.

Ok, I just submitted the new version and still have a WA but this time
the program ran 0.002 seconds. So the program's not correct but at least
the main function seems to work. I guess it was the "n 0" input that
caused that response.

Thanks again

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova
WR wrote:Ok, I just submitted the new version and still have a WA but this time
the program ran 0.002 seconds. So the program's not correct but at least
the main function seems to work. I guess it was the "n 0" input that
caused that response.
I just checked the stats for problem 530 and I see that there are far too many 0.000 accepted solutions, so probably the input data set is small.
Maybe you should check the behaviour of your prog with input near or equal to MAXINT...

Ciao!!!

Claudio

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

### 530

Hi,

why does this program give a WA?

I wouldn't be too surprised if the message were TLE but it's WA.

The elements of the denominator array (karr) are 1 when leaving the function binom, so what remains to be done is the multiplication of
the elements of narr but that can't be helped.

The program certainly gives a wrong answer if the (intermediate)
results of that multiplication don't fit into an integer but as there is
nothing to divide by anymore I think I can ignore that for this problem.

The function GGT is from S. Halim's website and computes the greatest common denominator (GCD).

Code: Select all

``````#include <stdio.h>                     /* printf */

/*****************************
* ACM Contest - Problem 530 *
*****************************/

long GGT(long a1, long b1)
{
long a, b;
a = a1;
b = b1;
while (b > 0){
a %= b;
a += b;
b = a-b;
a -= b;
}
return a;
}

long Minimum(long a, long b)
{
if (a < b)
return a;
else
return b;
}

double binom(long m, long n)
{
long i, j, k, l, t;
static long narr, karr;
long na, ka;
short end;
double b;
if (m == n)
return 1;
else{
if (n < 2)
return m;
else{
k = Minimum(n,m-n);
l = m - k;
for (i=0;i<k;i++){
karr[i] = i+1;
narr[i] = karr[i]+l;
}
for (i=k-1;i>=0;i--){
j = k-1;
end = 0;
do{
do{
na = narr[i];
ka = karr[j];
if ((na < 2) && (ka < 2))
end = 1;
else{
t = GGT(na,ka);
if (t > 1){
narr[i] /= t;
karr[j] /= t;
}
}
}while ((t > 1) && (end != 1));
j--;
}while ((j >= 0) && (end != 1));
}
b = 1;
for (i=0;i<k;i++)
b *= narr[i]/karr[i];
}
return b;
}
}

int main(void)
{
long k, n;
double p;
while (scanf("%ld %ld",&k,&n) == 2){
if ((k > 0) || (n > 0)){
p = k;
if (n == 0)
p = 1;
else
if (p > 1) p = binom(k,n);
printf("%.0lf\n",p);
}
}
return 0;
}
``````

Gigi's Baby
New poster
Posts: 19
Joined: Thu May 02, 2002 5:47 am
Location: Zhongshan (Sun Yat-sen) University
You can compute it directly.
C(n,k)=(n-k+1)/k * (n-k+2)/(k-1) * (n-k+3)/(k-2) ...

dpitts
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm
Thozz: Recursive factorial, for shame.

You end up with 100 factorials on the stack. Try using an iterative approach instead:

[cpp]long double Factorial(int n)
{
double value = 1;
for (int i = 2; i < n; i++)
value *= i;
return value;
}[/cpp]

Anyway, I think using double is sort of cheating, isn't it? Kind of defeats the purpose of this problem Well, if it gets AC, then it works okay I guess.

dpitts
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

### 530 Special cases.

I think I found a special case that is giving me WA, and I thought I'd share it.
Specifically, when k = 0, the output should = 1.

The way I had it set up, the program exited on k=0 Ohwell, its fixed now an I got AC.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
int is enough for this problem, if you do it cleverly enough. It's too bad that long double works =P

Examiner
New poster
Posts: 28
Joined: Thu Feb 19, 2004 1:19 pm
I didn't use double but got accepted. The magic line was
[cpp]r = max(r, n - r);[/cpp]

Pavl0
New poster
Posts: 16
Joined: Sun Apr 18, 2004 2:57 pm
the fastest way j know is using dynamic programing end formula:

nCr(n,r) = nCr(n-1,r-1) + nCr(n-1,r);

but j cant go AC :| but this way j hot AC in 369 - it's very symilar but easest

sory 4 me englisz Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am
Hello!

nCk = n! / k!(n-k)!

for example,
7C4 = 7! / (4! * 3!)
= 7 * 6 * 5 * 4 * 3 * 2 * 1
----------------------------
(4 * 3 * 2 * 1) * (3 * 2 * 1)

= 7 * 6 * 5
----------
3 * 2 * 1

= 7C3

100 C 99 = 100 C 1
1000 C 9998 = 1000 C 2
.
.
.

Try to do a loop for multiplying the numerator and the denominator;
whereby, we can reduce the numerator and the denominator to their lowest terms by dividing them with their greatest common divisor.

Frostina
New poster
Posts: 23
Joined: Mon Dec 15, 2003 5:21 am
i try to use recursion to solve this problem..
but it was "runtime error?!"
could anyone please tell me why ?

here's my code ..

[c]#include <stdio.h>
int c(int n, int r) {
if (n==r) return 1;
if ((r==1)||(!r)) return n;
return (c(n-1,r-1)+c(n-1,r));
}
int main(void) {
int n, r;
while (scanf("%d %d", &n, &r)==2) {
if (!n&&!r) break;
printf("%d\n", c(n, r));
}
return 0;
}[/c]
Thanks for your help ! Frostina
New poster
Posts: 23
Joined: Mon Dec 15, 2003 5:21 am
i try to use recursion to solve this problem..
but it was "runtime error?!"
could anyone please tell me why ?

here's my code ..

[c] Q_Q i was wrong.. [/c]
Last edited by Frostina on Sun Jul 04, 2004 6:57 am, edited 1 time in total.
Thanks for your help ! Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
your program crashes for input 10000 9999..
i guess you will still get TLE since the method is too slow

nCr = (n/r)* n-1 C r-1

one more correction if(!r) return 1( not n)
if u can think of it .. u can do it in software.

Frostina
New poster
Posts: 23
Joined: Mon Dec 15, 2003 5:21 am
Thanks a lot ! ^_^
I got AC.
Thanks for your help ! habibiamin
New poster
Posts: 8
Joined: Tue Oct 12, 2004 1:54 pm
Location: Iran-Tehran
Contact:

### 530 Why TLE (Help Please)

This is my solution for 530. But I don't know why its TLE Thanks
[cpp]
#include<stdio.h>
long long int gcd(long long int p,long long int q)
{
long long int temp;
while(q)
{
temp=p;
p=q;
q=temp%q;
}
return p;
}
int main()
{
long long int n,k;
long long int t,a,b;
while(scanf("%lld %lld",&n,&k),n!=0||k!=0)
{
a=1;b=1;
for(int i=1;i<=k;i++)
{
a*=n-k+i;
b*=i;
t=gcd(a,b);
a/=t;
b/=t;
}
printf("%lld\n",a);
}
return 0;
}
[/cpp]