Contest Duration: - (local time) (210 minutes) Back to Home
Official

## 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: