Problem Link:
Author: Vaibhav Srivastava
Tester: Shivam Garg and Vaibhav Srivastava
Editorialist: Saurabh Kumar
Difficulty:
Easy
Prerequisites:
Permutation, mod-inverse
Problem:
We are given number of people in 3 different groups (let’s say A, B and D). We have to output how many different ways are there to form a team among the groups in a way such that:-
i. There is at least 1 member from each group in a team.
ii. Number of member from group A has to be one more than the number of members from group B.
Quick Explanation:
The number of ways can be calculated by the formula:-
\sum_{2}^{A}(_{i}^{A}\textrm{C}*\sum_{1}^{min(B,i-1)}(_{j}^{B}\textrm{C})*(2^{D} - 1))
where, _{i}^{A}\textrm{C} = \frac{A!}{(i)!(A-i)!}.
Explanation:
The number of ways of selecting i people from a group of A people is _{i}^{A}\textrm{C} which equals \frac{A!}{(i)!(A-i)!}. Now as given in the question if we select i people from group A then we can select 1 to (i-1) number of people from group B which becomes \sum_{1}^{i-1}(_{j}^{B}\textrm{C}). B can also be less than i-1 therefore the summation changes to \sum_{1}^{min(i-1, B)}(_{j}^{B}\textrm{C}). And the number of ways of selecting 1 or more people from a group of D peoples is (2^{D} - 1).
Combining all these 3 equations we get the formula:-
\sum_{2}^{A}(_{i}^{A}\textrm{C}*\sum_{1}^{min(i-1, B)}(_{j}^{B}\textrm{C})*(2^{D} - 1))
So, we use two nested loops i and j. i from 2 to A and j from 1 to minimum of (i-1, B) and we can count the ways using the formula and keep adding to the final answer. One thing to note is that we can pre-compute the nCr values before the test cases and this would help in reducing the time complexity and getting accepted.
Time Complexity becomes O(A*B) which equals O(10^6).
Author’s solution can be found here.