131C. The World is a Theatre

Mathematics Combinatorics

There are $n$ boys and $m$ girls attending a theatre club. To set a play “The Big Bang Theory”, they need to choose a group containing exactly $t$ actors containing no less than $4$ boys and no less than one girl. How many ways are there to choose a group? Of course, the variants that only differ in the composition of the troupe are considered different.

Read the question with I/O specifications at codeforces.com.

Hints

Hint 1

The ways of selecting $r$ entities from $n$ entities is given by the formula $\binom{n}{r}$.

Hint 2

Think about the Pascal’s triangle - the triangular array of numbers with 1 at the end of the rows and others the sum of the nearest two numbers in the row above.

Solution

This question turns out to be a basic combinatorial problem. We have to choose a total of $t$ entities from a pool of $n$ elements of one type and $m$ of another.

For the selection of $i$ boys, $4 \leq i \leq n$, there exists $\binom{n}{i}$ ways.

For the selection of $t - i$ girls, $1 \leq t-i \leq m$, there exists $\binom{m}{t - i}$ ways.

Hence, there are $\binom{n}{i} \times \binom{m}{t - i}$ ways of selecting $i$ boys and $t-i$ girls i.e. t actors from a pool of $n$ boys and $m$ girls.

All that’s required is to find the sum of all these values for each possible $i$. This can be calculated by running a loop through all the possible values of $i$ - from $4$ till $t - 1$, considering to leave out cases when $r$ exceed $n$ in $\binom{n}{r}$.

The complexity of the problem now comes down to computing the value of the binomial coefficient. $\binom{n}{r}$, efficiently to fit within the time limit imposed the constraints. The easiest and an efficient approach would be through the Pascal’s triangle approach to computing the binomial coefficient. Read about the Pascal’s triangle at Wikipedia.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...

Each element in the Pascal’s triangle is the sum of the nearest two numbers in the row above, for elements except at the end of the rows. The end of the row positions are occupied by 1.

Code

#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll nr[35][35];

void pascals() {

	nr[0][0] = 1;
	nr[1][0] = 1;
	nr[1][1] = 1;
	for (int i = 2;i < 31;i++) {
		nr[i][0] = 1;
		for (int j = 1;j < i;j++) {
			nr[i][j] = nr[i-1][j-1] + nr[i-1][j];
		}
		nr[i][i] = 1;
	}
}

int main(void) {
	pascals();

  ll n, m, t, k = 0;
  cin >> n >> m >> t;

  for (int i = 4;i <= t-1;i++) {
    if (t-i > m || i > n) continue;
    k += nr[n][i] * nr[m][t-i];
  }
  
  cout << k;
}

Written by Nandakishore