D - Shopping Editorial by rng58_admin


Let’s consider the game as follows. Initially, each player is given \(K\) cards, numbered \(1\) through \(K\). In each turn, the player chooses one of the cards in his hand at random, and if the card is not a joker (described later), he wins the game, and leaves the game. At this point, if the card numbered \(x\) is just played, all other cards numbered \(x\) (in other players’ hands) will be changed to jokers. The game ends when \(K\) players leave.

What happens after each player takes exactly one turn? For each player, one of the following happens:

  • Wins and leaves the game.
  • There are \(K - 1\) cards in his hand. Exactly \(J - 1\) of them are jokers, where \(J\) is the number of people who have already left the game. (Since he didn’t win the game in the first round, the card he played must be a joker).

A key observation is that, after each remaining player takes the same number of turns (call it \(t\)), all remaining player has the same number of jokers in hands (that is, \(J - t\), where \(J\) is the number of people who have already left the game.)

Thus, we can define the following DP state:

\(dp[n][a][b][i]\): \(N\) people are remaining, each player has \(a\) cards, \(b\) of them are jokers. What is the probability that the \(i\)-th player wins?

To get a recurrence formula to compute \(dp[n][a][b][i]\), iterate over two parameters \(l, r\) - the number of people who leave the game in the next turn to the left / right of the \(i\)-th player. We get an \(O(N^6)\) solution with a very small constant.

posted:
last update: