MARBLES codechef explaination...

In our problem we are having N marbles we have to pick K colors. And it is necessary that at least one marble of each color.

So now we left with N-K marbles which can be of K colors. Now this problem turns into a problem of counting in how many

ways we can distribute N-K marbles into K distinguishable colors, with no constraints.

This is a problem of "combinations with repetitions", also known as the "stars and bars problem".

Lets journalize this whole situation for a while …

We can also have an r- combination of n items with repetition. And these two conditions must be fulfilled:-

For example: We can choose 6 marbles where only 3 colors are available. Colors are Blue(B), Red(R) , Yellow(Y).

How many different selections can we make?

Since order doesn’t matter we ‘ll list all of our selections in same order for example:
R R R B Y B is the same as R R R B B Y.
Analogically we can separate our combinations with dividers such as

- - - | - - | -

- | - - - - | -

- - - - | - - |

| | - - - - - -

we need to shift these dividers to get our combinations like:

R R R | B B | Y

R | B B B B B |

Now the answer becomes obvious: we have 8 slots there and just have to decide where to put the two dividers.
There are C(8,2) ways to do that, so C(8,2) = 28 possible selections.
… or equivalently, there are C(8,6) =28 ways to place the marble selections.

By observation we can state that there are (n-1) dividers. And there are r + (n−1) positions, and we want to choose r of them.

If we are selecting an r -combination from n elements with repetition, there are C(r+n-1 , n-1) or C(r+n-1 , r) ways to do so.

So for this problem r = N-K and n = K

We get C(N-1 , N-K).

Now the problem is the 1≤k,n≤1000000. If N =1000000 ,then we have no data type to store the value of 1000000!

What we can do here is, since we know that n C r = n*(n-1)*(n-2)……(n-r+1)/1*2*3*4*5….*r. We

can compute the value of (n/1)*(n-1/2) *(n-2/3) ... making sure that the partial value at any

step never becomes too large.

Code 1:

Output:

One more optimization we can do is n C r = n C n-r ,so if r>n/2 we can simply make r = n-r.

Code 2:

Output:

annoying_code