Soup Servings
Last Updated: April 2, 2026
Understanding the Problem
At first glance, this looks like a straightforward probability simulation. We have two soups, each starting at n ml, and on every turn we randomly pick one of four serving operations. Each operation takes more soup A than soup B on average. Specifically, across the four operations, A loses 100+75+50+25 = 250 ml total while B loses 0+25+50+75 = 150 ml total. So A depletes faster than B in expectation.
We need to find: P(A empties first) + 0.5 * P(A and B empty simultaneously).
The key insight that makes this problem tractable is that because A depletes faster, as n grows large, the probability converges to 1.0 very quickly. For sufficiently large n, we can just return 1.0 without computing anything. The interesting part is figuring out the exact threshold where the answer is close enough to 1.0, and computing the answer precisely for smaller values of n.
Since all serving amounts are multiples of 25, we can divide everything by 25 to simplify the state space. Instead of tracking ml directly, we track units of 25ml. The four operations become: serve (4,0), (3,1), (2,2), (1,3) units from A and B respectively.
Key Constraints:
0 <= n <= 10^9— The input can be enormous, so any solution that scales with n directly is out of the question. We need either a mathematical shortcut or a way to cap the computation. Since A depletes faster than B on average, the probability approaches 1.0 as n increases. For n above roughly 4800 (or 192 units of 25ml), the answer is within 10^-5 of 1.0. So the actual DP state space is bounded by a constant.
Approach 1: Recursive with Memoization (Top-Down DP)
Intuition
The most natural way to think about this problem is recursively. We are in state (a, b) representing the remaining amounts of soup A and B. At each step, we pick one of four operations uniformly at random and transition to the corresponding new state. The probability we want is the sum of probabilities over all paths, weighted by their likelihood.
The base cases are straightforward:
- If a <= 0 and b > 0, soup A ran out first. Return 1.0.
- If a <= 0 and b <= 0, both ran out simultaneously. Return 0.5.
- If a > 0 and b <= 0, soup B ran out first. Return 0.0.
For the recursive case, the answer for state (a, b) is the average of the answers for the four next states: (a-4, b), (a-3, b-1), (a-2, b-2), (a-1, b-3), where we are working in units of 25ml.
But there is a catch. With n up to 10^9, the state space could be huge. This is where the probabilistic nature of the problem saves us. Because A drains faster on average (losing 2.5 units per turn vs B losing 1.5 units), the probability converges to 1.0 rapidly as n increases. Empirically, for n >= 4800 (or about 192 units), the answer is already within 10^-5 of 1.0. So we can return 1.0 directly for large n and only run the DP for small n.
The critical insight is that the four operations are biased toward consuming more of soup A. On average, each turn removes 2.5 units from A but only 1.5 units from B (in units of 25ml). This asymmetry means that as n grows, soup A almost certainly empties first. Mathematically, the probability converges to 1.0 exponentially fast. By the time n reaches 4800, the difference from 1.0 is less than 10^-5, which is within the problem's accepted tolerance.
For small n, we compute the exact probability using dynamic programming. Each state (a, b) is visited at most once thanks to memoization, and from each state we do O(1) work (look up four children). The total number of unique states is at most k^2 where k = ceil(n/25).
Algorithm
- If n >= 4800, return 1.0 (the answer is within the accepted tolerance of 1.0).
- Convert n to units by computing
m = ceil(n / 25). - Define a recursive function
dp(a, b)with memoization: - If a <= 0 and b <= 0, return 0.5.
- If a <= 0, return 1.0.
- If b <= 0, return 0.0.
- Otherwise, 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).
Example Walkthrough
Code
- Time Complexity: O(k^2) where k = ceil(n/25). For n >= 4800, returns in O(1). Since k <= 192, the DP visits at most ~37,000 states, making this effectively constant time.
- Space Complexity: O(k^2) for the memoization table. With k <= 192, this is bounded by a constant.
The recursive approach works well, but uses a call stack proportional to the depth of recursion and hash map lookups for memoization. Can we eliminate both overheads by filling the table iteratively?
Approach 2: Bottom-Up Dynamic Programming
Intuition
Instead of computing probabilities top-down with recursion, we can fill a 2D table iteratively. The state dp[a][b] represents the probability that soup A empties first (plus half the probability both empty simultaneously) given a units of A and b units of B remaining.
The base cases are the same: dp[0][b] = 1.0 for b > 0 (A empty first), dp[a][0] = 0.0 for a > 0 (B empty first), and dp[0][0] = 0.5 (both empty). Then we fill the table for increasing values of a and b.
The benefit over the top-down approach is eliminating recursion overhead. In practice, both approaches have identical time complexity, but the iterative version avoids potential stack overflow for deeper recursion and is slightly more cache-friendly.
Notice that when computing dp[a][b], we reference states like dp[a-4][b] and dp[a-3][b-1]. Some of these indices can be negative or zero, which correspond to base cases. We handle this with a helper function that returns the appropriate base case value for out-of-bounds indices.
Algorithm
- If n >= 4800, return 1.0.
- Convert n to units:
m = ceil(n / 25). - Create a 2D array dp of size (m+1) x (m+1).
- Set base cases: dp[0][0] = 0.5, dp[0][b] = 1.0 for b > 0.
- For a from 1 to m, for b from 1 to m:
- dp[a][b] = 0.25 * (val(a-4, b) + val(a-3, b-1) + val(a-2, b-2) + val(a-1, b-3))
- where val(i, j) returns the correct value handling negative indices as base cases.
- Return dp[m][m].
Example Walkthrough
Code
- Time Complexity: O(k^2) where k = ceil(n/25). For n >= 4800, returns in O(1). The double loop iterates over at most 192 * 192 = 36,864 cells, so effectively constant time.
- Space Complexity: O(k^2) for the 2D DP table. At most 192 * 192 entries, bounded by a constant.