530 - Binomial Showdown

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Post by 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
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa »

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

Post by 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
New poster
Posts: 19
Joined: Thu May 02, 2002 5:47 am
Location: Zhongshan (Sun Yat-sen) University

Post by 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
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

Post by 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
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

530 Special cases.

Post by 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
:oops:

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:

Post by Larry »

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

Post by Examiner »

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

Post by 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
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Post by 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
New poster
Posts: 23
Joined: Mon Dec 15, 2003 5:21 am

Post by 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]
Thanks for your help ! ;)

Frostina
New poster
Posts: 23
Joined: Mon Dec 15, 2003 5:21 am

Post by 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]
Last edited by Frostina on Sun Jul 04, 2004 6:57 am, edited 1 time in total.
Thanks for your help ! ;)

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by 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)
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

Post by Frostina »

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)

Post by habibiamin »

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

Post Reply

Return to “Volume 5 (500-599)”