Problem statement

https://leetcode.com/problems/soup-servings/

Solution

We can look at this problem as dp problem with state a, b: ml of soup of both types. Then if both qualities are zero, we return 0.5, if soup A is empty, we return 1 and if soup B is empty, we return 0. Then we check 4 possibilities we have and return average of them. Also we can notice, that if N is big enough, then probability is very close to 1.

Complexity

Time complexity is O(n^2), where n = N/25 is possible range of our volumes of soup, space complexity as well. Note, that if n > 500, we return 1.

Code

class Solution:
    def soupServings(self, N):
        @lru_cache(None)
        def dfs(a, b):
            if a == 0 and b == 0: return 0.5
            if a == 0: return 1
            if b == 0: return 0 
            cand1 = dfs(max(a-100, 0), b)
            cand2 = dfs(max(a-75, 0), max(b-25, 0))
            cand3 = dfs(max(a-50, 0), max(b-50, 0))
            cand4 = dfs(max(a-25, 0), max(b-75, 0))
            return (cand1 + cand2 + cand3 + cand4)/4

        return dfs(N, N) if N < 7500 else 1