Soup Servings
Problem
n ml. Each turn one
of four servings is picked with probability 1/4: (A 100, B 0), (A 75, B 25), (A 50, B 50) or
(A 25, B 75) ml. If a soup has less than requested, serve what is left. Stop as soon as
either soup is empty. Return P(A empties first) + ½ · P(both empty
together).n = 50Output0.62500n = 100Output0.718750 ≤ n ≤ 109 · answers within 10-5 are accepted
Try it yourself
class Solution {
public double soupServings(int n) {
}
}
m = ⌈n/25⌉). On average A loses 2.5 units and B 1.5 per turn, so A
is heavily favoured: once n > 4800 the answer is within 10-5 of 1
and we can return 1 directly.Instinct Asked for a probability or expected value after random moves? Run DP over (step, state) and split each state's mass across every outcome.
Memory hack Pour the probability like water - split it across the moves, let what spills off the board drain away, and the puddle that's left is your answer.
Open the Probability DP guide →Approaches
Brute ForcePlain Recursion over All Serving Sequences
O(4n/100)Space O(n/100)f(a, b) returns 0.5 if both are empty, 1 if only A is empty, 0 if
only B is empty, else the average of the four next states. Every turn removes 100 ml
in total, so the depth is about 2n/100 and each level branches 4 ways.
public double soupServings(int n) { return serve(n, n); } private double serve(int a, int b) { if (a <= 0 && b <= 0) return 0.5; if (a <= 0) return 1.0; if (b <= 0) return 0.0; return 0.25 * (serve(a - 100, b) + serve(a - 75, b - 25) + serve(a - 50, b - 50) + serve(a - 25, b - 75)); }
Faithful to the rules but exponential — only works for a few hundred ml.
BetterMemoisation in 25 ml Units
O(m2)Space O(m2)Divide by 25 (rounding up, since a partial serving still empties the soup) to
get m units; servings become (4,0), (3,1), (2,2), (1,3). Only
(m+1)2 states (a, b) exist, so cache them.
private double[][] memo; public double soupServings(int n) { int m = (n + 24) / 25; // units of 25 ml, rounded up memo = new double[m + 1][m + 1]; for (double[] row : memo) Arrays.fill(row, -1); return f(m, m); } private double f(int a, int b) { if (a <= 0 && b <= 0) return 0.5; if (a <= 0) return 1.0; if (b <= 0) return 0.0; if (memo[a][b] >= 0) return memo[a][b]; double p = 0.25 * (f(a - 4, b) + f(a - 3, b - 1) + f(a - 2, b - 2) + f(a - 1, b - 3)); return memo[a][b] = p; }
Exact and fast for small n, but n = 109 needs a 4×107-squared table.
OptimalMemoisation + Convergence Cut-off
O(1)Space O(1)The answer increases towards 1 as n grows; at
n = 4800 (192 units) it is already 0.999995. So for larger
n return 1, and otherwise run the memo, whose table never exceeds
193×193 — a constant bound.
private double[][] memo; public double soupServings(int n) { if (n > 4800) return 1.0; // answer is within 1e-5 of 1 from here on int m = (n + 24) / 25; memo = new double[m + 1][m + 1]; for (double[] row : memo) Arrays.fill(row, -1); return f(m, m); } private double f(int a, int b) { if (a <= 0 && b <= 0) return 0.5; if (a <= 0) return 1.0; if (b <= 0) return 0.0; if (memo[a][b] >= 0) return memo[a][b]; double p = 0.25 * (f(a - 4, b) + f(a - 3, b - 1) + f(a - 2, b - 2) + f(a - 1, b - 3)); return memo[a][b] = p; }
Handles n up to 109 instantly; the cut-off is the whole trick.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Plain Recursion over All Serving Sequences | O(4n/100) | O(n/100) |
| Better | Memoisation in 25 ml Units | O(m2) | O(m2) |
| Optimal | Memoisation + Convergence Cut-off | O(1) | O(1) |
- Using
n / 25instead of rounding up — 1 ml of soup still counts as a unit. - Returning 1 for “both empty” instead of 0.5.
- Allocating an m×m table for n = 109 without the cut-off (memory error).
- Spot the gcd of all servings (25) early — it shrinks the state space 625×.
- Explain the asymmetry: expected A per turn is 62.5 ml vs 37.5 ml for B.
- Justify the cut-off with the 10-5 tolerance stated in the problem.