Soup Servings
Understanding the Problem
We have two soups, each starting at n ml, and on every turn we pick one of four serving operations uniformly at random. Each operation takes more soup A than soup B on average. 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).
This asymmetry is what makes the problem tractable. Because A depletes faster, as n grows the probability converges to 1.0, and the convergence is fast. For large enough n we can return 1.0 without computing anything. The work splits into two parts: pick a threshold above which the answer is within tolerance of 1.0, and compute the answer exactly for smaller n.
Since all serving amounts are multiples of 25, we can divide everything by 25 to shrink 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 very large, so any solution that scales with n directly is ruled out. We need either a mathematical shortcut or a cap on the computation. Since A depletes faster than B on average, the probability approaches 1.0 as n increases. For n at or above 4800 (192 units of 25ml), the answer is within 10^-5 of 1.0, so the DP state space we compute is bounded by a constant.
Approach 1: Recursive with Memoization (Top-Down DP)
Intuition
The problem has a recursive structure. We are in state (a, b) representing the remaining units of soup A and B. At each step we pick one of four operations uniformly at random and move to the corresponding new state. The probability we want is the sum over all paths, weighted by their likelihood.
The base cases:
- 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), in units of 25ml.
With n up to 10^9 the state space looks huge, but the bias in the operations bounds the work. Each turn removes 2.5 units from A on average ((4+3+2+1)/4) but only 1.5 from B ((0+1+2+3)/4). That gap drives the probability toward 1.0 as n grows. For n >= 4800 (192 units), the answer is already within 10^-5 of 1.0, so we return 1.0 directly for large n and run the DP only for small n.
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 version carries a call stack proportional to the recursion depth. The next approach fills the same table iteratively and avoids that.
Approach 2: Bottom-Up Dynamic Programming
Intuition
Instead of computing probabilities top-down with recursion, we fill a 2D table iteratively. The state dp[a][b] holds 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 match the recursive version: 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). We then fill the table for increasing a and b.
Both versions have the same time complexity. The iterative one removes the recursion, which keeps the call stack flat and the access pattern more cache-friendly.
Computing dp[a][b] references states like dp[a-4][b] and dp[a-3][b-1], and those indices can drop to zero or below. Those correspond to the base cases, so a helper function returns the right base-case value for any non-positive index.
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.