369 - Combinations

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

Moderator: Board moderators

IIUC GOLD
New poster
Posts: 19
Joined: Tue Jun 11, 2002 4:27 pm
Location: Bangladesh
Contact:

Post by IIUC GOLD » Thu Apr 07, 2005 8:43 am

My AC solution is as follows:

c = 1;
for (i=N,j=1;j<=R;i--,j++)
c=(c*i)/j;

Here, R is the minimum of M or N-M.
And the type of c is double or long long. All other variables are int.

It can also be solved by using c as an int. In that case, first divide c and j by gcd(c,j). Suppose the new value of c and j is c' and j'. Now divide i and j' by gcd(i, j'). Let the new value of i and j' is i' and j''. Then the answer will be c' * i'. [You need not do this in all iteration. It only requires at the last iteration (i.e when j=R).]

xintactox
New poster
Posts: 14
Joined: Thu Dec 01, 2005 3:17 pm
Location: Brazil

369 (combinations) - how to?!

Post by xintactox » Thu Dec 01, 2005 8:42 pm

Hi everyone!
I'm trying to solve the problem #369, but I don't know how to do it... I have a library with functions to manipulate big integers and I was trying to do the factorials in the ordinary way, i.e, multiplying... I don't know if i'm having some overflow problem or not, but my problem is into an infinity loop I guess...
Is there any easier way to solve this problem? Just a clue, please!
:)
Thanks!

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo » Fri Dec 02, 2005 2:56 am

You don't need big integer to solve this problem.

The problem says that :
"You may assume that the final value of C will fit in a 32-bit Pascal LongInt or a C long."

so a simple technique will pass this problem.

input :
100 6

Code: Select all

       100!
= ------------
   (100-6)!*6!
   
      100!
= ------------
    94! * 6!
    
     94! * 95 * 96 * 97 * 98 * 100
= ----------------------------------
         94! * 6!
         
(eliminate 94!)

    95*96*97*98*99*100
=  -------------------- 
        2*3*4*5*6
        
(divide 96 with 2*6 = 8)
(divide 99 with 3 = 33)
(divide 100 with 4*5 = 5)

= 95 * 8 * 97 * 98 * 33 * 5

= 1192052400
I hope you can get AC.
:D


"Life is beautiful with algorithm"

xintactox
New poster
Posts: 14
Joined: Thu Dec 01, 2005 3:17 pm
Location: Brazil

Almost there... :(

Post by xintactox » Mon Dec 05, 2005 8:00 pm

This thing is driving me mad... This should be a simple task, but I don't know how....
Well, the problem is: How to choose the right numbers to use (and how to keep track of them) to simplify the fraction?
My code works for the test cases given in the problem, but i'm getting WA anyway. I think the numbers aren't fitting into long long int. I need to find the right order to simplify the fraction!

My code follows.... Take a look please!!

Code: Select all

#include <iostream>

using namespace std;

void simplify(unsigned long long int *n, unsigned long long int *m)
{
	for(int i = 100; i >= 2; i--)
	{
		if(*n%i == 0 && *m%i == 0)
		{
			*n = *n/i;
			*m = *m/i;
		}
	}
}

int main()
{
	unsigned long long int num, den, C;
	unsigned long long int n, m, i, j;
	while(true)
	{
		cin>>n>>m;
		if(n == 0 && m == 0) break;
		num = n-m+1;
		den = m;
		i = num+1;
		j = den-1;
		while(i <= n && j > 1)
		{
			unsigned long long int aux1 = i;
			unsigned long long int aux2 = j;
			simplify(&aux1, &aux2);
			num *= aux1;
			den *= aux2;
			i++;
			j--;
		}
		while(i <= n)
		{
			num *= i;
			i++;
		}
		while(j > 1)
		{
			den *= j;
			j--;
		}
		if(num != 0 && den != 0)
			C = num/den;
		else C = 0;
		cout<<n<<" things taken "<<m<<" at a time is "<<C<<" exactly."<<endl;
	}
	return 0;
}

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Dec 05, 2005 8:29 pm

Is there any easier way to solve this problem?
You can just use the identity: C(n,m) = C(n,m-1)*(n-m+1)/m
Starting from C(n,0)=1, repeatedly apply the formula until you reach C(n,m).
With this formula, in the worst case you'll need to work with numbers of order 100*2^31, which fit well in 'long long'.

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

Post by shihabrc » Tue Jan 03, 2006 8:26 pm

U can try long double data type.But __int64/long long is sufficient. Try to evaluate C(n,m) as product of
(n-i)/(i+1) for i=0 to n-1;

-Shihab
Shihab
CSE,BUET

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by stcheung » Sat Jan 14, 2006 9:11 am

unsigned long is enough to store the result. There were some sample test data in this thread like C(100,50) but turns out the judge won't use those data, because my program got AC without returning the same output on these cases.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » Tue Jan 17, 2006 1:16 pm

mf wrote:
Is there any easier way to solve this problem?
You can just use the identity: C(n,m) = C(n,m-1)*(n-m+1)/m
Starting from C(n,0)=1, repeatedly apply the formula until you reach C(n,m).
With this formula, in the worst case you'll need to work with numbers of order 100*2^31, which fit well in 'long long'.

So, why this

Code: Select all

procedure solve;
 var
   n, m, i: integer;
   a: int64;
begin
  while true do begin
    readln(n,m);
    if (n=0) and (m=0) then break;

    a:= n;
    for i:=2 to m do
      a:= (a*int64(n-i+1)) div i;

    writeln(n,' things taken ',m,' at a time is ',a,' exactly.');
  end;
end;
gives WA???

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Jan 17, 2006 1:43 pm

kp wrote: So, why this

Code: Select all

procedure solve;
 var
   n, m, i: integer;
   a: int64;
begin
  while true do begin
    readln(n,m);
    if (n=0) and (m=0) then break;

    a:= n;
    for i:=2 to m do
      a:= (a*int64(n-i+1)) div i;

    writeln(n,' things taken ',m,' at a time is ',a,' exactly.');
  end;
end;
gives WA???
If you calculate say C(100,94), which is 1192052400 and fits into a standard integer, you pass the 'monster' C(100,50), which is about 10^29 and doesn't fit into even an int64.
Use a well known identity and approach such problems 'from the other side'.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » Wed Jan 18, 2006 10:47 am

little joey wrote:
If you calculate say C(100,94), which is 1192052400 and fits into a standard integer, you pass the 'monster' C(100,50), which is about 10^29 and doesn't fit into even an int64.
Use a well known identity and approach such problems 'from the other side'.
Thanks,
I really should think twice before posting such silly questions.

joebin
New poster
Posts: 12
Joined: Fri Dec 29, 2006 7:18 am
Location: Taiwan
Contact:

Post by joebin » Tue Feb 13, 2007 5:58 am

[CORRECT!!]

(intput)
100 90
100 50
99 40
100 6
20 5
18 6
0 0

(output)
1591253560
445776180
445776180
1192052400
15504
18564


(THE TEST DATA WHICH SOMEBODY TOLD ME IS CORRECT) 8)[/quote]
I have a problem !
I used calculator to count c(100,90) and c(100,50).
I found that c(100,90) < c(100,50) , but your output
1591253560 > 445776180.
Though I got AC , my ans are c(100,90)=1591253560 and
c(100,50)=-938977944.
why mine is different from yours??

joebin
New poster
Posts: 12
Joined: Fri Dec 29, 2006 7:18 am
Location: Taiwan
Contact:

Post by joebin » Tue Feb 13, 2007 5:59 am

[CORRECT!!]

(intput)
100 90
100 50
99 40
100 6
20 5
18 6
0 0

(output)
1591253560
445776180
445776180
1192052400
15504
18564


(THE TEST DATA WHICH SOMEBODY TOLD ME IS CORRECT) 8)[/quote]
I have a problem !
I used calculator to count c(100,90) and c(100,50).
I found that c(100,90) < c(100,50) , but your output
1591253560 > 445776180.
Though I got AC , my outputs were c(100,90)=1591253560 and
c(100,50)=-938977944.
why mine is different from yours??

kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

Post by kn » Fri Apr 27, 2007 7:22 pm

joebin wrote:[CORRECT!!]

(intput)
100 90
100 50
99 40
100 6
20 5
18 6
0 0

(output)
1591253560
445776180
445776180
1192052400
15504
18564


(THE TEST DATA WHICH SOMEBODY TOLD ME IS CORRECT) 8)
Well, it's just because the online judge does not use large test cases..
In fact, C(100, 50) = 8247740487481686900760421832
(You can try it using the windows calculator)
which can not be correctly held using a LONG LONG UNSIGNED

↓It seems contradictory to the original question...
Computing the exact number of ways that N things can be taken M at a time can be a great challenge when N and/or M become very large.

NaIx
New poster
Posts: 4
Joined: Sat Jun 02, 2007 5:49 pm
Location: indonesia

WA... need help

Post by NaIx » Sat Jun 02, 2007 5:57 pm

I don't know wjy my program WA... i'm really confuse..... somebody help plzzz...........

#include<cstdio>
#include<cstdlib>

int main()
{
long int N, M, C, i, j;
while(scanf("%ld %ld",&N,&M)==2)
{
if(N==0&&M==0) break;
else
{
if(N-M < M) M=N-M;
C=1;
for(i=N,j=1;j<=M;i--,j++)
{
C=(C*i)/j;
}
printf("%ld things taken %ld at a time is %ld exactly.\n",N,M,C);
}
}
return 0;
}

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Sat Jun 02, 2007 6:07 pm

Try this case..

Code: Select all

34 14
0 0
My output is..

Code: Select all

34 things taken 14 at a time is 1391975640 exactly.

Post Reply

Return to “Volume 3 (300-399)”