Problem Description

Alice is playing a game similar to "21" (Blackjack). The game works as follows:

• Alice starts with 0 points
• She keeps drawing numbers as long as she has less than k points
• Each draw gives her a random integer between 1 and maxPts (inclusive), with all outcomes being equally likely
• Each draw is independent of previous draws
• Alice stops drawing immediately when she reaches k or more points

Given three parameters:

• n: a target score threshold
• k: the minimum score at which Alice stops drawing
• maxPts: the maximum points that can be gained in a single draw

You need to calculate the probability that Alice's final score is n or less.

For example, if k = 10, maxPts = 5, and n = 15:

• Alice keeps drawing while her score is less than 10
• Each draw adds 1 to 5 points randomly
• Once she reaches 10 or more, she stops
• We want the probability that her final score is at most 15

The answer should be accurate within 10^-5 of the actual probability.

Intuition

The key insight is to think about this problem recursively. We can define dfs(i) as the probability of ending with a score ≤ n when starting from score i.

Starting from any score i < k, Alice must draw another card. The next score will be i + j where j is between 1 and maxPts. Since each outcome is equally likely, we have:

dfs(i) = (1/maxPts) × Σ[j=1 to maxPts] dfs(i+j)

This means the probability from score i is the average of probabilities from all possible next scores.

However, computing this directly for each state would be too slow. The clever optimization comes from recognizing a pattern. If we expand dfs(i) and dfs(i+1):

• dfs(i) = (dfs(i+1) + dfs(i+2) + ... + dfs(i+maxPts)) / maxPts
• dfs(i+1) = (dfs(i+2) + dfs(i+3) + ... + dfs(i+maxPts+1)) / maxPts

Notice that these two sums overlap significantly! The only difference is that dfs(i) includes dfs(i+1) but not dfs(i+maxPts+1), while dfs(i+1) includes dfs(i+maxPts+1) but not dfs(i+1) itself.

By subtracting the second equation from the first, we get: dfs(i) - dfs(i+1) = (dfs(i+1) - dfs(i+maxPts+1)) / maxPts

Rearranging: dfs(i) = dfs(i+1) + (dfs(i+1) - dfs(i+maxPts+1)) / maxPts

This transforms our O(maxPts) calculation per state into O(1)!

The special case is when i = k-1. From this score, Alice draws one more card and immediately stops (since she'll reach k or more). The probability of ending ≤ n is simply the fraction of outcomes that land in the valid range [k, n]. This gives us: dfs(k-1) = min(n-k+1, maxPts) / maxPts

Learn more about Math, Dynamic Programming and Sliding Window patterns.

Solution Approach

The solution uses memoized recursion (dynamic programming with memoization) to efficiently calculate the probability. Here's how the implementation works:

State Definition: We define dfs(i) as the probability that starting from score i, Alice ends with a final score ≤ n.

Base Cases:

1. If i >= k: Alice stops drawing. Return 1 if i <= n (success), otherwise return 0 (failure).
2. If i == k - 1: This is a special case. From score k-1, Alice draws exactly one more card and stops. The probability of success is the fraction of outcomes that result in a score ≤ n:
   • Valid outcomes are scores in range [k, min(n, k + maxPts - 1)]
   • Number of valid outcomes = min(n - k + 1, maxPts)
   • Probability = min(n - k + 1, maxPts) / maxPts

Recursive Case (when i < k - 1): Using the optimization derived earlier: dfs(i) = dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts

This formula allows us to calculate dfs(i) in O(1) time given the values of dfs(i + 1) and dfs(i + maxPts + 1).

Implementation Details:

• The @cache decorator is used for memoization, storing already computed values of dfs(i) to avoid redundant calculations
• The recursion starts from dfs(0) (Alice's initial score)
• The function works backwards from higher scores to lower scores due to the recursive nature

Time Complexity: O(n) where n is the maximum score we need to consider. Each state is computed at most once due to memoization.

Space Complexity: O(n) for the memoization cache storing the computed probabilities.

The key insight that makes this solution efficient is transforming the naive O(k × maxPts) approach into an O(n) solution by recognizing the mathematical relationship between consecutive states and using the sliding window property of the probability calculations.

Example Walkthrough

Let's walk through a small example with n = 6, k = 4, and maxPts = 3.

Alice starts at score 0 and keeps drawing while her score is less than 4. Each draw adds 1, 2, or 3 points with equal probability (1/3 each). She stops when reaching 4 or more points.

Step 1: Identify possible final scores

• From score 0: Drawing 1,2,3 → reach scores 1,2,3 (continue drawing)
• From score 1: Drawing 1,2,3 → reach scores 2,3,4 (continue from 2,3; stop at 4)
• From score 2: Drawing 1,2,3 → reach scores 3,4,5 (continue from 3; stop at 4,5)
• From score 3: Drawing 1,2,3 → reach scores 4,5,6 (stop at all)

Possible final scores: 4, 5, 6

Step 2: Calculate probabilities using our formula

Start with base cases (scores ≥ k):

• dfs(6) = 1 (6 ≤ n = 6, success)
• dfs(5) = 1 (5 ≤ n = 6, success)
• dfs(4) = 1 (4 ≤ n = 6, success)

Special case at k-1 = 3:

• From score 3, Alice draws once more and stops
• Valid outcomes: reaching 4, 5, or 6 (all ≤ n = 6)
• dfs(3) = min(6-4+1, 3) / 3 = 3/3 = 1.0

Working backwards using our optimized formula:

• dfs(2) = dfs(3) + (dfs(3) - dfs(6)) / 3

• dfs(2) = 1.0 + (1.0 - 1.0) / 3 = 1.0

• dfs(1) = dfs(2) + (dfs(2) - dfs(5)) / 3

• dfs(1) = 1.0 + (1.0 - 1.0) / 3 = 1.0

• dfs(0) = dfs(1) + (dfs(1) - dfs(4)) / 3

• dfs(0) = 1.0 + (1.0 - 1.0) / 3 = 1.0

Result: The probability is 1.0, meaning Alice always ends with a score ≤ 6.

This makes sense because the maximum possible score is 6 (reaching score 3, then drawing 3), which equals our target n. Therefore, Alice can never exceed n, giving us probability 1.0.

Solution Implementation

Time and Space Complexity

The time complexity is O(k + maxPts) and the space complexity is O(k + maxPts).

Time Complexity Analysis: The function uses memoization with @cache decorator. Each state i from 0 to at most k + maxPts is computed at most once due to caching. The recursive calls explore states from i = 0 up to potentially i = k + maxPts - 1 (since when we're at state k-1 and draw maxPts, we reach k - 1 + maxPts). Each memoized computation takes O(1) time as it only performs constant operations and makes recursive calls that are either already cached or will be cached. Therefore, the total time complexity is O(k + maxPts).

Space Complexity Analysis: The space complexity comes from two sources:

1. The recursion stack depth, which can go up to O(k + maxPts) in the worst case
2. The cache storage for memoization, which stores results for states from 0 to potentially k + maxPts - 1

Both contribute to a space complexity of O(k + maxPts).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Base Case Handling

A common mistake is not properly handling the boundary between when Alice continues drawing and when she stops. The critical insight is that Alice stops drawing immediately when her score reaches k or more.

Pitfall Example:

# WRONG: This incorrectly continues drawing even at score k
if current_points > k:  # Should be >= k
    return 1.0 if current_points <= n else 0.0

Solution: Always use current_points >= k to check if Alice has stopped drawing.

2. Misunderstanding the k-1 Special Case

When Alice has exactly k-1 points, she will draw exactly one more card and stop. Many implementations fail to optimize this case or calculate it incorrectly.

Pitfall Example:

# WRONG: Incorrectly counting favorable outcomes
if current_points == k - 1:
    # This doesn't account for the upper bound correctly
    favorable_outcomes = n - k + 1  # Missing min() with maxPts
    return favorable_outcomes / maxPts

Solution: The favorable outcomes should be min(n - k + 1, maxPts) because:

• Alice can only draw values from 1 to maxPts
• She needs to land in the range [k, n] to win
• The number of winning draws is limited by both constraints

3. Stack Overflow with Deep Recursion

For large values of n and k, the recursive solution without memoization can cause stack overflow or timeout.

Pitfall Example:

# WRONG: No memoization leads to exponential time complexity
def calculate_probability(current_points):
    if current_points >= k:
        return 1.0 if current_points <= n else 0.0
    # Recursive calls without caching results
    return sum(calculate_probability(current_points + i) 
               for i in range(1, maxPts + 1)) / maxPts

Solution: Always use memoization (@cache decorator or manual dictionary) to store computed results and avoid recalculating the same states.

4. Floating Point Precision Issues

When dealing with probabilities, accumulating small floating-point errors can lead to results outside the required accuracy of 10^-5.

Pitfall Example:

# WRONG: Accumulating errors through repeated additions
total = 0
for i in range(1, maxPts + 1):
    total += calculate_probability(current_points + i)
return total / maxPts  # Small errors can accumulate

Solution: Use the sliding window optimization formula which minimizes the number of floating-point operations:

return next_probability + (next_probability - future_probability) / maxPts

5. Edge Case: When k > n

If k > n, Alice needs more points to stop drawing than the maximum allowed score. In this case, the probability should be 0, but some implementations might not handle this correctly.

Solution: The base case if current_points >= k: return 1.0 if current_points <= n else 0.0 naturally handles this, but it's important to verify this edge case works correctly.