369 - Combinations

[IIUC GOLD]

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]

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]

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]

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]

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]

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

[stcheung]

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]

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

[little joey]

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

[kp]

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]

[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]

[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]

[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]

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]

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.