530 - Binomial Showdown

[WR]

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]

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]

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[10000], karr[10000];
  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]

You can compute it directly.
C(n,k)=(n-k+1)/k * (n-k+2)/(k-1) * (n-k+3)/(k-2) ...

[dpitts]

Thozz: Recursive factorial, for shame.

This about this, your stack has enough room for maybe 50 depth, but what happens if you take Factorial(100)?
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]

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]

int is enough for this problem, if you do it cleverly enough. It's too bad that long double works =P

[Examiner]

I didn't use double but got accepted. The magic line was
[cpp]r = max(r, n - r);[/cpp]

[Pavl0]

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

[Zyaad Jaunnoo]

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]

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]

[Frostina]

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]

[jagadish]

your program crashes for input 10000 9999..
i guess you will still get TLE since the method is too slow

this recurrence maybe helpful

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

one more correction if(!r) return 1( not n)

[Frostina]

Thanks a lot ! ^_^
I got AC.

[habibiamin]

This is my solution for 530. But I don't know why its TLE
Please help me !
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]