[ Closed ] Codeforces The World is a Theatre

codeforces
combinatorics
easy
simple
simple-math

#1

Problem Statement : Click here.


I have approached at this formula for this question.

Assume C[n][r] = n!/(n-r)!*(r!)


ans = c[n][4] * c[m][1] * c[n+m-5][t-5];
<-- this is the formula i’ve got.
Please correct me, Where I’ve gone wrong?


#2

I think c[n][4]*c[m][1] is enough.


#3

Your formula will lead to repeated cases. Example there are 4 boys and 3 girls and t = 6 then your answer is c[4][4] * c[3][1] * c[2][1] = 6 but answer is 3 because there are only 4 boys so each group needs to have all the boys plus 2 more girls for which there are C[3][2] ways = 3. What is happening is that once you fix certain girls/boys in the compulsory slot call them X and then you pick another set of boys/girls in the non compulsory slot, call them Y. Now it is possible that in some other group, you have already counted this group by including some of Y in the compulsory slots and some of X in the non compulsory slot.

Since t is small, I would suggest you go by the answer as -
ans = C[n][4] * C[m][t-4] + C[n][5] * C[m][t-5] + … C[n][t-1] * C[m][1]

Depending on n and m, there will be slight modifications in this, but you get the idea.


#4

please read the question carefully and check before answering here .


#5

Thanks! :slight_smile:


#6

No problem !