Soup Servings: Probability with Memoized Recursion

You have two types of soup, A and B, each starting with n ml. Every turn you pick one of four operations at random, each serving different amounts from each soup. Your job is to find the probability that soup A runs out first, plus half the probability that both soups run out at the same time. This is LeetCode 808: Soup Servings, and it combines probability, memoized recursion, and a neat convergence trick into one compact problem.

The problem

You start with n ml of soup A and n ml of soup B. Each turn, you choose one of the following four operations with equal probability (0.25 each):

1. Serve 100ml of soup A and 0ml of soup B
2. Serve 75ml of soup A and 25ml of soup B
3. Serve 50ml of soup A and 50ml of soup B
4. Serve 25ml of soup A and 75ml of soup B

If the remaining soup is not enough, you serve as much as possible. When soup A runs out, you stop. Return the probability that soup A empties first, plus half the probability that A and B empty at the same time.

The approach

Notice that all serving amounts are multiples of 25. That means we can divide n by 25 (rounding up) and work in units instead of milliliters. The four operations become: serve (4, 0), (3, 1), (2, 2), or (1, 3) units from (A, B).

From there, define dp(a, b) as the probability that soup A empties first (plus half the tie probability) given a units of A and b units of B remaining. The recursion averages the results of the four operations. We memoize with @lru_cache to avoid recomputing states.

The key insight: soup A loses more on average per turn. A loses (4+3+2+1)/4 = 2.5 units per turn, while B loses (0+1+2+3)/4 = 1.5 units per turn. For large n, the probability that A empties first approaches 1.0. In fact, for n >= 4800, the answer is within 10^-5 of 1.0, so we can return 1.0 immediately.

from functools import lru_cache

def soupServings(n: int) -> float:
    if n >= 4800:
        return 1.0

    m = (n + 24) // 25

    @lru_cache(maxsize=None)
    def dp(a, b):
        if a <= 0 and b <= 0:
            return 0.5
        if a <= 0:
            return 1.0
        if b <= 0:
            return 0.0
        return 0.25 * (
            dp(a - 4, b)
            + dp(a - 3, b - 1)
            + dp(a - 2, b - 2)
            + dp(a - 1, b - 3)
        )

    return dp(m, m)

The early return for large n is not just an optimization. Without it, the state space grows quadratically and the recursion becomes impractical. With it, the function runs in O(1) for any input above 4800.

Step-by-step walkthrough

Here is how the algorithm builds the answer from its pieces.

The normalization step keeps the state space manageable. The recursive formula averages four sub-problems, and the base cases handle the three possible outcomes: A empties first, both empty together, or B empties first. For large inputs, the convergence property lets us skip the computation entirely.

Complexity analysis

After normalizing, the state is a pair (a, b) where both values range from 0 to ceil(n/25). That gives at most m^2 states where m = ceil(n/25). Each state does O(1) work. But since we cap n at 4800, m is at most 192, making the maximum number of states around 37,000. In practice, the function returns in constant time for any large input.

The building blocks

Memoized recursion for probability

The core pattern here is the same one you see in Knight Probability in Chessboard. Each state contributes a probability by combining results from sub-states. Instead of summing counts or minimizing costs, you average probabilities. The recursion structure is identical to any other memoized DP problem. Define your state, write the recurrence, handle base cases, and cache results.

Convergence and early termination

This is what makes Soup Servings unique. On average, soup A loses 62.5ml per turn and soup B loses 37.5ml per turn. That asymmetry means A will almost certainly empty before B when n is large enough. The expected number of turns to empty A is roughly n / 62.5, while for B it is n / 37.5. As n grows, the probability of A finishing first converges to 1.0 so quickly that for n >= 4800 the answer rounds to 1.0 within the required precision of 10^-5.

This kind of early termination based on mathematical convergence shows up occasionally in competitive programming. Recognizing when a problem has this property saves you from implementing a solution that would time out on large inputs.

Edge cases

• n = 0: Both soups are already empty, so return 0.5 (the "both empty at the same time" case, weighted by half).
• Large n (n >= 4800): The probability converges to 1.0 within the required precision. Return 1.0 directly.
• Small n: Need the actual memoized recursion. For example, n = 50 gives 2 units each, and the recursion explores a small number of states.

From understanding to recall

Reading through this solution, the convergence trick and the recursion probably make sense. But will you remember the threshold of 4800, the normalization step, and the exact base cases under pressure? Understanding is the first step, but recall under time constraints is a separate skill. Spaced repetition bridges that gap. You revisit this problem at increasing intervals, write the solution from scratch each time, and after a few reps the pattern sticks. Probability DP with convergence is a rare but memorable building block, and drilling it a few times makes it automatic.

Related posts

• Coin Change - Memoized recursion over remaining amounts
• Knight Probability in Chessboard - Probability with DP
• Champagne Tower - Flow simulation with probability-like distribution