We are given two soups, A and B, each starting with n mL. On each turn, the program randomly picks one of the following four serving operations, each with equal probability (0.25):

1. Serve 100 mL from A, 0 mL from B
2. Serve 75 mL from A, 25 mL from B
3. Serve 50 mL from A, 50 mL from B
4. Serve 25 mL from A, 75 mL from B

The process stops when either A or B becomes empty. If an operation asks to serve more soup than is available, it only serves what remains. The goal is to calculate the probability that soup A is emptied before B, plus half the probability that both become empty in the same step.

Intuition

Each turn reduces both A and B. The outcome depends on which soup finishes first or whether they both finish at the same time. The four operations form a probabilistic branching structure, and the problem can be seen as calculating the expected result from a probability tree.

We can use memoization to store the results of overlapping subproblems. Importantly, when n becomes large (specifically, above 4500), the result converges very close to 1.0. So we can short-circuit the calculation in such cases.

To simplify calculations, we convert n into units of 25 mL. This helps limit the total number of states we need to compute.

Approach

We define a recursive function p(a, b) that returns the probability that soup A is emptied before B (plus half if they empty at the same time), starting from a units of A and b units of B. We reduce the soup volume in units of 25 mL.

We use a 2D array size[a][b] to memoize results to avoid recalculating the same state.

C++ Code

class Solution {
public:
    double p(int a, int b)
    {
        if (a <= 0 && b <= 0)
            return 0.5;

        if (a <= 0)
            return 1;

        if (b <= 0)
            return 0;

        auto& res = size[a][b];
        if (res == 0)
            res = 0.25 * (p(a - 4, b) + p(a - 3, b - 1) + p(a - 2, b - 2) + p(a - 1, b - 3));

        return res;
    }

    double soupServings(int n) {
        if (n > 4500) return 1;

        int m = ceil(n / 25.0);
        return p(m, m);
    }

    double size[300][300];
};

JavaScript Version

var soupServings = function(n) {
    if (n > 4500) return 1;

    const memo = new Map();

    const dp = (a, b) => {
        if (a <= 0 && b <= 0) return 0.5;
        if (a <= 0) return 1;
        if (b <= 0) return 0;

        const key = `${a},${b}`;
        if (memo.has(key)) return memo.get(key);

        const result = 0.25 * (
            dp(a - 4, b) +
            dp(a - 3, b - 1) +
            dp(a - 2, b - 2) +
            dp(a - 1, b - 3)
        );

        memo.set(key, result);
        return result;
    };

    const m = Math.ceil(n / 25);
    return dp(m, m);
};

Python Version

import math
from functools import lru_cache

class Solution:
    def soupServings(self, n: int) -> float:
        if n > 4500:
            return 1.0

        m = math.ceil(n / 25)

        @lru_cache(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)

Time and Space Complexity

Time Complexity:

• The number of unique states we compute is proportional to O(n^2) where n is the number of 25 mL units (i.e., ceil(n / 25)).
• So worst-case is O(300 * 300) = 90,000 states when n = 4500.

Space Complexity:

• We use a 2D array or memoization table of size O(n^2) to cache results.

Final Thoughts

This problem blends probability and recursion. The key insight is to limit the state space by grouping soup quantities in multiples of 25. For large n, the probability of A being finished first becomes so close to 1.0 that we can safely return 1 as an approximation. Memoization helps to efficiently handle overlapping subproblems without recomputing.