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.

# | User | Rating |
---|---|---|

1 | tourist | 3822 |

2 | Benq | 3745 |

3 | ksun48 | 3560 |

4 | Radewoosh | 3538 |

5 | peehs_moorhsum | 3532 |

6 | Um_nik | 3489 |

7 | maroonrk | 3424 |

8 | Petr | 3380 |

9 | sunset | 3338 |

10 | ecnerwala | 3336 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 206 |

2 | Errichto | 181 |

2 | awoo | 181 |

4 | Um_nik | 180 |

5 | -is-this-fft- | 175 |

6 | maroonrk | 174 |

7 | Radewoosh | 172 |

7 | tourist | 172 |

9 | SecondThread | 170 |

10 | rng_58 | 166 |

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.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/31/2021 03:34:34 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Since the constraints are small I think probability of winner being declared after 10

^{6}games is very small. Hence.we can simulate if for 10^{6}games and take it to be answer.Does this seem correct??

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

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

Editorial

The exact solution:

Brute-force the first 2

n-ksteps, 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 2

k+ 1 vertices, that represent the difference between the two players [ -k...k]. States -kandkare absorbing (you cannot get out of them), and there are transitions from a state to its neighbours of probabilitysand 1 -srespectively.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).

Thanks.