Problem Description
A group of Facebook employees just had a very successful product launch. To celebrate, they have decided to go wine tasting. At the vineyard, they decide to play a game. One person is given some glasses of wine, each containing a different wine. Every glass of wine is labelled to indicate the kind of wine the glass contains. After tasting each of the wines, the labelled glasses are removed and the same person is given glasses containing the same wines, but unlabelled. The person then needs to determine which of the unlabelled glasses contains which wine. Sadly, nobody in the group can tell wines apart, so they just guess randomly. They will always guess a different type of wine for each glass. If they get enough right, they win the game. You must find the number of ways that the person can win, modulo 1051962371.
Input
The first line of the input is the number of test cases, N. The next N lines each contain a test case, which consists of two integers, G and C, separated by a single space. G is the total number of glasses of wine and C is the minimum number that the person must correctly identify to win.
Constraints
- N = 20
- 1 ≤ G ≤ 100
- 1 ≤ C ≤ G
Output
For each test case, output a line containing a single integer, the number of ways that the person can win the game modulo 1051962371.
Example input
5 1 1 4 2 5 5 13 10 14 1
Example output
1 7 1 651 405146859
Dynamic Programming Approach
During the contest, I chose to tackle this using a dynamic programming (DP) approach which will be described in this entry. As usual, the DP approach will need us to formulate the recurrence relation for this problem. The recurrence I used was based on the following:
Let f(n, pc, t) be the number of ways to guess arrangement of n glasses with pc of them still have a chance to be named correctly (pc stands for potentially correct), and at least t glasses will be named correctly. When looking at the state (n, pc, t), let our focus be on the very first glass position which can be named correctly. On that position, there’s a possibility to put the correct glass on it, or a wrong glass. Let’s explore the function:
def f(n, pc, t): if n == 0: return 1 if t == 0 else 0 ways = 0 if pc > 0: ways += f(n-1, pc-1, max([0, t-1])) if pc > 1: ways += (pc-1) * f(n-1, pc-2, t) ways += (n-pc) * f(n-1, max([0, pc-1]), t) return ways
Line 2 contains the terminal condition of this recurrence, … it is clear that if there’s no glass left to worry, … we only have one success possibility if there is no target to achieve, t is zero.
Then comes the accumulation of number of ways based on possibilities of actions in this state, … remember the step always focuses in putting a glass (either correct or incorrect) into a position which can still have a proper glass for it.
Line 4 is also straightforward, one of the possibility is to put the correct glass into its position (there’s only one glass here) … the next state after putting this glass is obviously (n-1, pc-1, max(0, t-1)).
Line 5 is basically a possibility of putting wrong glass into the position, but this wrong glass actually has its own proper position somewhere. This means we’re actually wasting 2 glasses and their positions without gaining any correct target. Note that we can choose one out of pc-1 glasses for this possibility, thus the multiplication with pc-1.
Line 6 is basically a possibility of putting wrong glass into the position, and this wrong glass never has a chance to be properly placed (i.e.: its proper position has been occupied by another glass). We can choose out of (n-pc) glasses for this, thus the multiplication by (n-pc). The next state is: (n-1, max(0, pc-1), t).
That’s it, … finally, to tackle an input of (G, C) … call the above function f(G, G, C) …
The above logic doesn’t take care of the modulo for clarity, … the following C++ code has the proper solution for this puzzle.
