AlgoInsight

DSA problem

Soup Servings

MediumProbability DPPattern: Probability DPtop300GoogleAmazonMicrosoftBloombergApple

There are two soups, A and B, each initially containing n mL. On every turn one of four operations is chosen uniformly at random, each with probability 1/4: serve 100 mL of A and 0 mL of B; serve 75 mL of A and 25 mL of B; serve 50 mL of A and 50 mL of B; or serve 25 mL of A and 75 mL of B. If at any operation a soup does not have enough left, we just serve all that remains of it. We keep serving until at least one of the soups is empty. Return the probability that A becomes empty first, plus half the probability that A and B become empty at the same time.

The crucial observation is that every serving size is a multiple of 25 mL. We therefore rescale the problem by working in units of 25 mL: replace n by ceil(n / 25) and the four operations by (4, 0), (3, 1), (2, 2), (1, 3). After scaling, the state space (a, b) is at most a few thousand cells wide for small n, which makes memoisation tractable.

Define p(a, b) as the answer when there are a units of A and b units of B left. There are three boundary cases that drop out of the rules: a <= 0 and b <= 0 simultaneously means both finished on the same operation, contributing probability 0.5; a <= 0 only means A finished first, contributing 1; b <= 0 only means B finished first, contributing 0. Note the order in which these are checked matters — the simultaneous case must be tested before either single-empty case.

For larger n something subtle happens: the four operations all bias toward draining A faster than B (on average 2.5 units of A vs 1.5 of B per turn), so as n grows the probability of "A empties first or simultaneously" rapidly approaches 1. Once n exceeds roughly 4800 mL, the true answer is within 1e-5 of 1, so we may safely short-circuit and return 1.0. Without this guard a naive DP for very large n would explode in time and memory.

Examples

Example 1
Input: n = 50
Output: 0.625
Explanation: After scaling, n = 2 units. Enumerating the four operations one level deep gives a probability of 5/8 = 0.625 that A empties first or both empty simultaneously.
Example 2
Input: n = 100
Output: 0.71875
Explanation: Scaled n = 4 units. Recursion over the four operations with the boundary rules yields 23/32 = 0.71875.
Example 3
Input: n = 10000
Output: 1.0
Explanation: Past roughly 4800 mL the bias toward draining A dominates so strongly that the answer is within 1e-5 of 1; we short-circuit and return 1.0.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

dynamic-programmingprobabilitymemoizationmath

Browse all DSA problems