Блог пользователя SureYeaah

Автор SureYeaah, история, 6 лет назад, По-английски

Hey everyone,

I was trying to solve this problem from Topcoder. Correct solutions to the problem had used dp but aren't there infinite states when PointsToWinBy > 1?

Thanks.

  • Проголосовать: нравится
  • -16
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Since the constraints are small I think probability of winner being declared after 106 games is very small. Hence.we can simulate if for 106 games and take it to be answer.

Does this seem correct??

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

The exact solution:

Brute-force the first 2n - k steps, counting the probability of exiting along the way. We do this because, after that, we will be guaranteed that the winner (by difference) will have enough points to count.

Now, imagine a path with 2k + 1 vertices, that represent the difference between the two players [ - k...k]. States  - k and k are absorbing (you cannot get out of them), and there are transitions from a state to its neighbours of probability s and 1 - s respectively.

This is a classical problem, called Gambler's Ruin (unfair coin version), and it has a closed form solution: https://en.wikipedia.org/wiki/Gambler%27s_ruin

You can also solve a more general version of this problem, on Markov chains (they are actually called absorbing Markov chains).