## 369 - Combinations

Moderator: Board moderators

IIUC GOLD
New poster
Posts: 19
Joined: Tue Jun 11, 2002 4:27 pm
Contact:
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?!

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
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. "Life is beautiful with algorithm"

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

### Almost there... :(

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:
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:
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:
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
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
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???

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
kp wrote: So, why this

Code: Select all

``````procedure solve;
var
n, m, i: integer;
a: int64;
begin
while true do begin
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
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:
[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) [/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:
[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) [/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
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) 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

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
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.``