Marbles - Codechef Solution

Problem:

Rohit dreams he is in a shop with an infinite amount of marbles. He is allowed to select n marbles. There are marbles of k different colors. From each color there are also infinitely many marbles. Rohit wants to have at least one marble of each color, but still there are a lot of possibilities for his selection. In his effort to make a decision he wakes up. Now he asks you how many possibilities for his selection he would have had. Assume that marbles of equal color can't be distinguished, and the order of the marbles is irrelevant.

Problem Abstract :The mathematical crux of the problem isSelection With Repetition.If there are 'n' objects and 'r'objects have to be selected from it such that repetition is allowed,then number of ways in which this can be achieved is given by(n + r -1) Cr

Lets take a concrete example : A Candy shop have 3 types of candies say A B & C. We have to purchase 4 candies . How may ways can this purchase be done ? Following shows some of the cases :

A A A A--> All candies of type A
A A B B--> 2 of type A and 2 of Type B
A B C A--> 2 of type A and rest B C each one

Here N = 3 , R = 4
So number of ways in which this can be done is(3+4-1) C 4= > 15 Ways in total .

Returning to our problem , its given there are K types of marbles , N of them have to be selected. Given that there should be at least 1 from each type. This means we already selected one each from each of K types. Now we have to select remaining N-K items from K types of marbles . Which according to above problem is

r =N - K

n = K

solutionis(n + r -1)Cr

The crux is implementing the Combinatorial FunctionnCr .While implementing this we have to have a look at the limits ofN ,K in the problem statement. In MARBLES its quite large. 1 <=N <=K<=1000000

Implementation Issues :

The formula for nCr isn!/((n-r)! * r!)
(NOTE: in the problemr= N - K , as explained above)

Look at the denominator there , r!!!! . Its already given thatN,K <= 10000000, clearlyN-K <= 1000000 , which means we have to find thesay factorial of 10000000 !!!This cannot be done because its factorials have more than 100000 digits and cannot be represented using any datatypes. So we have to surmount this issue .

To do that we look at the alternate definition ofnCr.

nCr = n * (n-1)* (n - 2) ..... (n-r+1)/ (1 *2 * 3 * ...r)

==>n/1*(n-1)/2*(n-2)/3 ......................

This way of computation will make sure that the partial value of nCr computed will never become too large that cannot be represented using any datatype.

Also there is one more simplifying stuff :nCr==>nC(n-r) . So if we find that

r > n/2 , we taker = n-rWhich simplifies the calculation.

Following is the implementation :

long long int C (long long int n, long long int r) {
long long int res = 1,i;
if(r > n/2)
r = n-r;
for(i = 0; i < r; i++) {
res *=n;
res /= i+1;
n--;
}
return res;
}

NOTE: The use oflong long int , should be obvious to you , the intermediate results if becomes bigger should be accommodated. Also the limits ofK ,N are 100000000 which requires a lager storage , ( long int will also do ) .

References : Readers interested in Permutations and Combinations are directed to the Master Work ofRalph . P . Grimaldi" Discrete Mathematical Structures "