CR193 - Editorial

Problem Link:

Contest
Practice

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.

1 Like

Please explain the use of ifact[].

ifact array is used to store the modular multiplicative inverse. We need that in order to calculate the nCr. Suppose you want to calculate ((x/y) % mod), where mod is some prime number. We can not divide x by y and then take mod, this would be wrong. We multiply x with the modular multiplicative inverse of y and then take mod.
You can read more about it at Modular Inverse - Algorithms for Competitive Programming