PROBLEM LINKS
DIFFICULTY
MEDIUM
PREREQUISITES
Dynamic Programming, Simple Math
PROBLEM
(Although the problem is stated slightly differently, I believe this interpretation of the problem is much easier to discuss. The main insight used here is that the students may be seated in rows, but that is irrelevant, since rows don’t affect the outcome at all.)
You are playing a game of Memory. There are N cards face down on the table. There are an even number of cards. Each card has a unique matched pair.
You play the game step by step.
- Open a card face up. Now you know the rank on the card.
- Open another card face up. Now you know the rank on the card.
- If both the cards have the same rank, they remain face up.
- Otherwise, they both go face down.
You have infinite memory. You also employ an optimal strategy - optimising it as ranks get revealed to you during a move.
What is the expected number of moves in which you will have all the cards face up.
EXPLANATION
The key insight in this problem is deriving the optimal strategy.
Since the cards are shuffled uniformly randomly among all possible permutations, the order in which you will consider cards does not matter. Hence, let us assume that the cards are kept in a horizontal line and you pick them up from left to right.
When we are playing by the optimal strategy, at any point in the game, we will have a total of T cards, out of which K are known. Also, all of the K known cards are unique.
The optimal strategy employed at any state is
- Pick a card from the set of unknown cards.
- If the card matches a known card, always pick the known card as the second card.
- Otherwise, pick another unknown card.
- If the second unknown card matches a known card, in the next move, select that pair of known cards to make them face up.
- Begin with Step 1 again.
Hints to this strategy lie in the Explanation Section of the problem statement, but getting here may not be intuitive (but getting here is in itself about half the work done).
Let us dissect the strategy and see why it would be optimal.
Step 1 is obvious. We would never risk picking a known card first since we will be reducing our odds of completing the game faster.
We can see that Step 3 is also obvious. If we picked a first card whose pair is not known yet, then we will never pick a known card as the second card.
Although Step 4 is not compulsory to guarantee the minimum number of moves, but we know that this known pair has to be eliminated. We can do it later, but there is no harm (that is, we will not be increasing the expected number of moves) in doing it now.
The only step that might not be immediately intuitive is Step 2. Note that if we do not immediately select the matching pair, we will always incur an additional move - the move to eliminate this known pair of cards.
To implement this strategy we can maintain a Dynamic Programming state
D[T,K] = expected number of moves with T cards and K known
// probability that first card matches a known card P1 = K / (T-K) // probability that first card did not match a known card // and the second card matched the first card P2 = (1-P1) / (T-K-1) // probability that first card did not match a known card // and the second card matched a previous known card P3 = (1-P1) * K / (T-K-1) // probability that neither the first, nor the second card // match any known cards P4 = (1-P1) * (1-P2-P3) D[T,K] = P1 * (1 + D[T-2,K-1]) + // we pick the known pair (STEP 2) P2 * (1 + D[T-2,K]) + // we eliminate the first and the second card we pick! P3 * (2 + D[T-2,K]) + // we make another move to eliminate the new pair P4 * (1 + D[T,K+2]) // we only make more knowns, no elimination
Implementing this recursion solves the problem in O(N2) time. The maximum value of N from the problem statement is 2500. Hence, this will solve the problem.
CODE COMMENTARY
Dynamic Programming with recursion requires very careful implementation. All the stopping conditions must be carefully met, otherwise the program would easily go out of index bounds for the DP array.
In the tester’s solution, you can notice that there are guards in place to avoid recursing to undesirable values of T and K.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.