yassin_'s blog

By yassin_, history, 7 years ago, In English

I am stuck on this problem

Basically: p1 has N points, p2 has M points. They play N + M - 1 rounds. N, M ≤ 1000. The player who gets zero first loses.

p1 knows the probability of winning each round pi, the loser gets 1 point subtracted.

I can only think of dp in O((N+M)*N*M), but it gets TLE

my code

Any help is appreciated :)

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

If I am not mistaken, your O(N*M) dp update is very inefficient? In fact, I believe only O(N+M) element are actually updated? So maybe you can make that more efficient?