Approach #1: Dynamic Programming [Accepted]

Intuition

It is clear that the probability that Alice wins the game is only related to how many points x she starts the next draw with, so we can try to formulate an answer in terms of x.

Algorithm

Let f(x) be the answer when we already have x points. When she has between K and N points, then she stops drawing and wins. If she has more than N points, then she loses.

The key recursion is This is because there is a probability of to draw each card from to .

With this recursion, we could do a naive dynamic programming solution as follows:

#psuedocode
dp[k] = 1.0 when K <= k <= N, else 0.0
# dp[x] = the answer when Alice has x points
for k from K-1 to 0:
    dp[k] = (dp[k+1] + ... + dp[k+W]) / W
return dp[0]

This leads to a solution with time complexity, which isn't efficient enough. Every calculation of dp[k] does work, but the work is quite similar.

Actually, the difference is . This allows us to calculate subsequent 's in time, by maintaining the numerator .

As we calculate each dp[k] = S / W, we maintain the correct value of this numerator .

Complexity Analysis

  • Time and Space Complexity: .
    Note that we can reduce the time complexity to and the space complexity to by only keeping track of the last values of dp, but it isn't required.

Analysis written by: @awice.