SureYeaah's blog

How is this solvable using dp?
By SureYeaah, history, 6 years ago, In English

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.

  • Vote: I like it
  • -16
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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??

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ah Okay, so it's an approximate solution. Can we also find the exact solution?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      On further googling ,I found out editorial describes an approximation solution.
      Editorial

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

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).

→ Reply