### 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(N ^{2}) 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.