Problem Description
Given n milliliters of two types of soup, A and B, you perform operations that reduce fixed amounts of each soup with equal probability. There are four operations available:
- 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.
If during an operation there is insufficient soup to serve the full amount, you serve as much as possible. The process stops when one or both soups run out. The goal is to compute the probability that soup A becomes empty first plus half the probability that A and B become empty at the same time.
Key Insights
- The problem is inherently probabilistic and can be solved using recursion with memoization (DP).
- Transform the problem by scaling down the soup amounts (dividing n by 25 and rounding up), converting the operations to unit decrements.
- Use a recursive function dp(a, b) to compute the probability starting with a units of soup A and b units of soup B.
- Base cases:
- Both soups empty (a <= 0 and b <= 0): return 0.5.
- Only soup A empty (a <= 0): return 1.
- Only soup B empty (b <= 0): return 0.
- For large n (n > 4800), the answer approaches 1, so return it early for performance reasons.
Space and Time Complexity
Time Complexity: O((n/25)²) in the worst-case because the recursive state space is roughly bounded by the transformed soup amount. Space Complexity: O((n/25)²) due to the memoization cache storing each state.
Solution
The solution employs recursion with memoization to avoid redundant calculations. By scaling down the amount of soup (dividing by 25) the problem works in a smaller state space. The recursive function handles:
- Base conditions where one or both soups are empty.
- A summation of the outcomes from the four possible operations. To improve efficiency for very large soup amounts, an early return is added when n exceeds 4800, as the probability converges to 1.