STANDUP - Editorial

PROBLEM LINKS

Practice
Contest

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

  1. Pick a card from the set of unknown cards.
  2. If the card matches a known card, always pick the known card as the second card.
  3. Otherwise, pick another unknown card.
  4. If the second unknown card matches a known card, in the next move, select that pair of known cards to make them face up.
  5. 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.

4 Likes

P4 should be (1-P1-P2-P3)

1 Like

No. I think the definition of P4 implies it should be (1-P1)*(1-P2-P3).

The given definition of P4 is not correct.
P1 is when First card matches with a previous card. P2 is when First and second card are same (then they obviously don’t match with any previous card). P3 is when only second card matches with a previous card. P4 is when First and Second Cards are different and they don’t match with any previous cards.
P4 is when neither of P1, P2 and P3 occurs.
That is
P1+P2+P3+P4=1

1 Like

I think we have to take two moves for the first case, because we have to pick the know card again.

so , “P1 * (1 + D[T-2,K-1])” should be “P1 * (2 + D[T-2,K-1])”

similarly with step2, step4

P4=(1-P1)*(1-a-b) where a=1/(t-k-1) and b=k/(t-k-1).

1 Like

@siddharth_l
yes i also think p4 should be p4=(1-p1)*(1-a-b) where a=1/(t-k-1) and b=k/(t-k-1).

the given definition of p4 in editorial is wrong

because probability that the second card do not match any known cards

is = (1-a-b)

where a=probab. that second card matches with first card in the move

and b=probab. that second card matches with the k known cards

which is also equal to p4=(1-p1-p2-p3)

as p4 = (1-p1)*(1-a-b)

   = 1-p1 - a*(1-p1) - b*(1-p1)

   = 1-p1 - p2 -p3

   = (1-p1 -p2-p3)
//