Marbels (Codeshef)

Problem link : MARBLES

In order to solve this problem we need to know basic permutation and combination. We can address this problem with the tag "Selection With Repetition" . If we have n type of object or n objects and we have to choose k objects from these where each object can be choosen multiple times, then number of ways we can do it is  (n+k-1) C (k).

Let's come to our problem. we have K type of objects and we have to choose N objects from them. So, now we can convert the given formula into (K+N-1) C (N). Suppose , we have 30 objects to choose and we have 7 types of objects. This formula will give us (36)C(30) = 1947792. Which is much much greater that the required answer. This happens because we have calculated all the possibilities without filtering those possibilities where we haven't taken at least one from each types (which is a key condition) . Let's assume another example - we have two letters A , B and we have to choose 3 letters each time. We can do this in the following ways ..

AAA   -> All of type A
AAB   -> 2 of type A and 1 of type B
ABB   -> 2 of type B and 1 of type A
BBB   -> All of type B

This will give us 4C3 = 4 ways to choose. But we can not count AAA and BBB because these possibilities don't have at least one of A or B. So,we have to take K of the given types automatically and choose the remaining N-K items out of K items. our final formula takes  the form-

(K+N-K-1) C (N-K)
= (N-1) C (N-K)

Now using the basic combination formula
nCr = n * (n-1)  * (n - 2) ..... (n-r+1)  / (1 *2 * 3 * ...  r) 
or using dp with the idea of binomial coefficient
we can find out the desired value of (N-1) C (N-K) .

My solution link : MARBELS SOLUTION