### SureYeaah's blog

By SureYeaah, history, 4 years ago,

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

 » 4 years ago, # |   +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??
•  » » 4 years ago, # ^ |   0 Ah Okay, so it's an approximate solution. Can we also find the exact solution?
•  » » » 4 years ago, # ^ |   +5 On further googling ,I found out editorial describes an approximation solution. Editorial
 » 4 years ago, # | ← 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_ruinYou can also solve a more general version of this problem, on Markov chains (they are actually called absorbing Markov chains).
•  » » 4 years ago, # ^ |   0 Thanks.