TSECJ105 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest

Author: TSEC CodeCell

DIFFICULTY:

Medium

PROBLEM:

Find the number of ways a group can be split into a combination or pairs and solo units mod 10^9 +7.

EXPLANATION:

We must find ways N distinct people can form pairs out of which some can remain alone.

So the Nth person can stay alone (1 way to do that), or pair with someone from 1 to N-1.
Thus f(N)= 1* f(N-1) + N-1 * f(N-2)

The solution can be optimized by caching all the results in an array.
The precomputation of all results take O(N) time and O(1) for answering each test query.

AUTHOR’S SOLUTIONS:

Author’s solution can be found here.

1 Like
2

Can someone explain the f(N) function in better way? Specially this underbrace part f(N)=1\cdot f(N-1)+\underbrace{(N-1)\cdot f(N-1)} ?

3

@bansal1232

The recursive function

f(n) = f(n-1) + (n-1) \cdot f(n-2)

The first term of the RHS is simple. The person who has just been added, let us call him A, be alone while we can pair all the other people in f(n-1) ways. For the second term in the RHS, we can pair A with any of the n-1 people, then we have n-2 people left, so we can also arrange them in f(n-2) ways. Thus, the number of ways of forming pairs is (n-1) \cdot f(n-2).

1 Like