Solution: Soup Servings

Understand how to apply dynamic programming to compute the probability that soup A empties before soup B in a randomized serving process. Explore memoization techniques and recursion to optimize calculations, handling large input values with state normalization. Gain insight into solving probabilistic problems efficiently with coding interview patterns.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

You begin with two types of soup, A and B, each containing n milliliters. During each turn, exactly one of the following four operations is selected uniformly at random (each with probability $0.25$ ), independent of all prior turns:

Serve $100$ mL of soup A and $0$ mL of soup B.
Serve $75$ mL of soup A and $25$ mL of soup B.
Serve $50$ mL of soup A and $50$ mL of soup B.
Serve $25$ mL of soup A and $75$ mL of soup B.

The serving from both soups happens simultaneously in each turn. If an operation requires serving more than the remaining amount of a particular soup, simply serve whatever is left of that soup. The process terminates immediately after any turn in which at least one soup becomes empty.

Compute and return the probability that soup A becomes empty before soup B, plus half the probability that both soups become empty at the same time. Answers within $10^{-5}$ of the true value will be accepted.

Note: There is no operation that serves $0$ mL of soup A and $100$ mL of soup B. ...