Soup Servings

The problem requires us to compute the probability of finishing soup A before or at the same time as soup B, taking into account the four types of operations.

In this problem, each serving operation reduces the quantity by multiples of 25ml. So, we can divide n by 25 to simplify the problem. If n is not a multiple of 25, we add 1 to n (equivalent to rounding up to the nearest multiple of 25) to account for the case where there’s still some soup A or B remaining, but not enough to serve.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def soupServings(self, n: int) -> float:
        if n > 4800:
            return 1.0

        n = (n + 24) // 25
        memo = {}

        def dp(x, y):
            if (x, y) in memo: return memo[x, y]
            if x <= 0 and y <= 0: return 0.5
            if x <= 0: return 1.0
            if y <= 0: return 0.0

            memo[x, y] = 0.25 * (dp(x-4, y) + dp(x-3, y-1) + dp(x-2, y-2) + dp(x-1, y-3))
            return memo[x, y]

        return dp(n, n)

This code is using memoization to reduce the computational overhead of the recursion. The dp function calculates the probability, and the results are stored in memo to avoid recalculating for the same values of x and y. This greatly improves the efficiency of the code, especially for larger inputs.

The base cases are when x <= 0 and y <= 0. If x (soup A) is finished and y (soup B) is still remaining, we return 1.0, indicating a 100% probability of soup A finishing first. If both are finished (x <= 0 and y <= 0), we return 0.5, indicating a 50% chance of either soup finishing first. If only soup B is finished, we return 0.0, indicating a 0% chance of soup A finishing first.

The recursive step involves calling the dp function for the 4 possible serving operations and taking the average. This value is then stored in memo[x, y] for future reference.