Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The future probability depends only on the amounts of soup remaining. Each serving choice has probability one quarter, so a state's answer is the average of its four successor answers. Soup A is consumed faster on average; for sufficiently large equal starting amounts, the answer is close enough to one to use the problem's permitted approximation.

Approach

Follow the reference cutoff: return 1 when n > 5000. This is an approximation, not a claim that A must empty first.
For smaller inputs, memoize the answer for remaining amounts (a, b). Return 0.5 when both are depleted, 1 when only A is depleted, and 0 when only B is depleted. Check the simultaneous case first, including the initial input zero.
Otherwise, average the states after subtracting (100, 0), (75, 25), (50, 50), and (25, 75). Nonpositive amounts are handled by the terminal cases.
Evaluate the state (n, n), reusing repeated amount pairs through memoization.

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

        @cache
        def dp(a, b):
            if a <= 0 and b <= 0:
                return 0.5
            if a <= 0:
                return 1
            if b <= 0:
                return 0

            res = 0
            res += 0.25 * dp(a - 100, b)
            res += 0.25 * dp(a - 75, b - 25)
            res += 0.25 * dp(a - 50, b - 50)
            res += 0.25 * dp(a - 25, b - 75)
            return res

        return dp(n, n)

Complexity analysis

For n ≤ 5000, let k = ceil(n / 25). Memoization computes at most O(k²) soup-pair states with four transitions each, using O(k²) time and space plus O(k) recursion depth. For n > 5000, the cutoff returns in O(1) time and space.