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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Code: Select all

nC0 = 1
I think you are missing this case. You are printing 0.
Ami ekhono shopno dekhi...
HomePage

TripShock
New poster
Posts: 14
Joined: Tue Jun 20, 2006 9:33 am

WA

Post by TripShock »

can someone please tell me what is wrong with this C code...

Code: Select all

#include <stdio.h>

int main()
{
    int n = 0;
    int r = 0;
    unsigned int Result = 1;
    double Temp = 1.0;
    int i = 0;

    while (1)
    {
        scanf("%d %d", &n, &r);
            
        if (n == 0 && r == 0)
            break;
            
        r = n - r < r ? n - r : r;
            
        for (i = r, Temp = 1.0; i >= 1; i--)
            Temp = Temp * ((double)(n--) / i);

        Result = (int)Temp;

        printf("%d\n", Result);
    }

    return 0;
}

Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

Post by Spykaj »

Code: Select all

110 6
My answer:

Code: Select all

2141851635
Your:

Code: Select all

2141851634
: )

john_locke
New poster
Posts: 13
Joined: Sat Oct 07, 2006 6:42 pm
Contact:

why WA

Post by john_locke »

I think my code gives the right answers but why WA please give some critical input

Code: Select all


/*problem for solving nCk
Author :-Vivek Sharma  */
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int main()
{
	long double n,k;//binomial coefficient
	while(cin>>n>>k)
	{
		if(n==0&&k==0)
			return 0;
		long double num=1,den=1;
		if(n-k<k)
			k=n-k;
		for(int i=k;i>0;i--)
		{
			num=(n+i-k)*num;
			den=(k-i+1)*den;
		//cout<<num<<" "<<den<<endl;
			if(fmod(num,den)==0)
			{
				num=num/den;
				den=1;
			}
		}
	printf("%.0lf\n",num);
	}
	return 0;
}

thanx in advance

RED-C0DE
New poster
Posts: 16
Joined: Mon Mar 26, 2007 6:47 pm

Post by RED-C0DE »

hello everybody , i got RE and i cant understand why?!...

can i do better with my algo ?...
tnx...

Code: Select all

 
//530 C0DED by RED-C0DE ~ 07-11-06 11:09 pm
#include <cstdio>
#include <iostream>
using namespace std;

__int64 f2(int n,int m)
{
	static __int64 cache[1000][1000]={0};

	if(n<1000 && m<1000 && cache[n][m])
		return cache[n][m];
	if(m==n || m==0)
		return 1;
	return  n<1000 && m<1000 ? (cache[n][m] = f2(n-1,m) + f2(n-1,m-1)) : f2(n-1,m) + f2(n-1,m-1) ;
}

int main()
{
	int n ,m;
	while(cin >> n >> m && n )
		printf("%ld\n" , f2(n,m));

	return 0;
}
:::::J.u.s.t.C.0.D.E.i.T:::::

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Read the description again.
Warning: Don't underestimate the problem. The result will fit into an integer - but if all intermediate results arising during the computation will also fit into an integer depends on your algorithm. The test cases will go to the limit.
20000 20000 is a valid case. And your will return nothing but RTE.
Ami ekhono shopno dekhi...
HomePage

scott1991
New poster
Posts: 28
Joined: Fri Dec 07, 2007 11:41 pm

Post by scott1991 »

my code doesn't work but i have no idea why. can anyone help please?

Code: Select all

i have done the following code to solve this problem but it wont run properly, and breaks. I am totally confused as to why this is. Can anyone help please? i take the system("pause") out before submitting. 

// Binomial Showdown - 530.cpp : Defines the entry point for the console application. 
#include <iostream> 
#include <math.h> 
using namespace std; 

int factorial(int input){ 
int answer = 0, current = 1; 
while (current < input) { 
answer *= current; 
current++; 
} 
return answer; 
} 

int main(int argc, char* argv[]) 
{ 
a: 
int n=1,k=1; 
int o,q,w,answer; 
scanf("%d%d",&n,&k); 
if (n!=0 && k !=0) 
{ 
q=factorial(n); 
w=factorial(k); 
o = q /( w * ( q - w ) ); 
cout<<o<<endl; 
system("PAUSE"); 
goto a; 

} 
else 
{ 
return 0; 
} 
}
Thanks

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 »

You should not solve the problem by finding factorial separately. U may get RTE.
Because if n=20 then ? On the other hand using string causes RTE or invalid output.
U may use this algo:

--->Do n!/(r!*(n-r)!)
--->Like, 5C2 = 5! / (2!*(5-2)!) = 5! / (2!*3!) = 5*4*3*2*1/2*1*3*2*1 = 5*2
--->And then multiply the simplest form of nCr (5*2) = 10
--->Get the output.

Hope it will work.

ligregni
New poster
Posts: 11
Joined: Thu Nov 29, 2007 12:41 am
Location: Queretaro, M
Contact:

Post by ligregni »

Thozz wrote:Hi there!. This is my code:

Code: Select all

#include <stdio.h>

long double Factorial(int f, int s) {
    if (f < s) return 1;
    else return f*Factorial(f-1, s);    
}

main() {
    long double n, k;
    while ((scanf("%Lf %Lf\n", &n, &k)>0)&&(n>0))
        if (k > 0)
            printf("%.0Lf\n", Factorial(n, n-k+1)/Factorial(k, 1));
        else printf("0\n");
}
While running at home I get a right output, but the judge always answers: Runtime Error (SIGSEGV). Does anyone know what happend?.
main () should return a value too

Code: Select all

main ()
{
...

return 0;
}
C: multum in parvo

"a lot since quite few"

http://acmicpc-live-archive.uva.es/nuev ... user=12539

ligregni
New poster
Posts: 11
Joined: Thu Nov 29, 2007 12:41 am
Location: Queretaro, M
Contact:

Post by ligregni »

scott1991 wrote:my code doesn't work but i have no idea why. can anyone help please?

Code: Select all

i have done the following code to solve this problem but it wont run properly, and breaks. I am totally confused as to why this is. Can anyone help please? i take the system("pause") out before submitting. 

// Binomial Showdown - 530.cpp : Defines the entry point for the console application. 
#include <iostream> 
#include <math.h> 
using namespace std; 

int factorial(int input){ 
int answer = 0, current = 1; 
while (current < input) { 
answer *= current; 
current++; 
} 
return answer; 
} 

int main(int argc, char* argv[]) 
{ 
a: 
int n=1,k=1; 
int o,q,w,answer; 
scanf("%d%d",&n,&k); 
if (n!=0 && k !=0) 
{ 
q=factorial(n); 
w=factorial(k); 
o = q /( w * ( q - w ) ); 
cout<<o<<endl; 
system("PAUSE"); 
goto a; 

} 
else 
{ 
return 0; 
} 
}
Thanks
YOU SHOULD initialize answer=1;

because the line

Code: Select all

answer *= current; 
you are always multiplying 0 * n = 0 EVERYTIME!!!

I think it helps!!!

Sergio Ligregni, MEX
C: multum in parvo

"a lot since quite few"

http://acmicpc-live-archive.uva.es/nuev ... user=12539

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

530

Post by Obaida »

Could any one help me please. Is there any shortcut way to calculate the value. please help me to find the equation.
:o

Code: Select all

#include<stdio.h>
int main()
{
	long int sum=1,sum1=1,sum2=1,i,m,n,num;
	while(scanf("%ld %d",&m,&n)==2)
	{
		for(i=1;i<=m;i++)
		{
			sum=sum*i;
		}
		for(i=1;i<=n;i++)
		{
			sum1=sum1*i;
		}
		for(i=1;i<=(m-n);i++)
		{
			sum2=sum2*i;
		}
		num=sum/(sum1*sum2);
		printf("%d\n",num);
	}
	return 0;
}
try_try_try_try_&&&_try@try.com
This may be the address of success.

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

Post by mpi »

Your algorithm is correct, but it can be made faster. To compute the binomial coefficient of n and k is not necessary to compute n! + k! + (n-k)!. Write it down on a piece of paper and you will realize that some terms can be omitted, so that you can cut down drastically the number of operations.

Just two notes on the code above:

1. The last input pair is n=0, k=0 and shouldn't be processed.
2. If you compute the factorials first and then divide, some of the results can overflow the int type (even long long int). The thing of the problem is to think how to deal with this...

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Whats the problem 530

Post by Obaida »

Code Removed After Acc..
Last edited by Obaida on Wed May 07, 2008 8:44 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Oh.... No....

Post by Obaida »

:evil:
Over comed pervious problem but still got TLE....
please help..... I sort so many calculation. What can I do...?
try_try_try_try_&&&_try@try.com
This may be the address of success.

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

Post by mpi »

The problem is here:

Code: Select all

           else
           {
               r=n+1;
               for(i=r;i<=m;i++)
               {
                        sum=sum*i;
               }
               for(i=1;i<=n;i++)
               {
                    sum2=sum2*i;
               }
               num=sum/sum2; 
In the second for, i goes from 1 to m-n (or 2 to m-n)

Post Reply

Return to “Volume 5 (500-599)”