Soup Servings

medium dp memoization probability

Problem

There are two soups A and B, each starting with n ml. Each turn, one of four equally likely operations runs (serving 100/0, 75/25, 50/50, 25/75 of A/B). Return the probability that A empties first plus half the probability they empty together.

Inputn = 50

Output0.62500

With small n direct simulation; for n >= 4800 answer ~ 1.

from functools import lru_cache

def soupServings(n):
    if n >= 4800:
        return 1.0
    units = (n + 24) // 25
    @lru_cache(maxsize=None)
    def dp(a, b):
        if a <= 0 and b <= 0: return 0.5
        if a <= 0: return 1.0
        if b <= 0: return 0.0
        return 0.25 * (dp(a-4,b) + dp(a-3,b-1) + dp(a-2,b-2) + dp(a-1,b-3))
    return dp(units, units)

var soupServings = function(n) {
    if (n >= 4800) return 1.0;
    const units = Math.ceil(n / 25);
    const memo = new Map();
    const dp = (a, b) => {
        if (a <= 0 && b <= 0) return 0.5;
        if (a <= 0) return 1.0;
        if (b <= 0) return 0.0;
        const key = a * 5000 + b;
        if (memo.has(key)) return memo.get(key);
        const v = 0.25 * (dp(a-4,b) + dp(a-3,b-1) + dp(a-2,b-2) + dp(a-1,b-3));
        memo.set(key, v); return v;
    };
    return dp(units, units);
};

class Solution {
    private double[][] memo;
    public double soupServings(int n) {
        if (n >= 4800) return 1.0;
        int units = (n + 24) / 25;
        memo = new double[units+1][units+1];
        for (double[] r : memo) java.util.Arrays.fill(r, -1);
        return dp(units, units);
    }
    private double dp(int a, int b) {
        if (a <= 0 && b <= 0) return 0.5;
        if (a <= 0) return 1.0;
        if (b <= 0) return 0.0;
        if (memo[a][b] >= 0) return memo[a][b];
        return memo[a][b] = 0.25 * (dp(Math.max(a-4,0),b) + dp(Math.max(a-3,0),b-1) + dp(Math.max(a-2,0),Math.max(b-2,0)) + dp(a-1,Math.max(b-3,0)));
    }
}

class Solution {
    vector<vector<double>> memo;
    double dp(int a, int b) {
        if (a <= 0 && b <= 0) return 0.5;
        if (a <= 0) return 1.0;
        if (b <= 0) return 0.0;
        if (memo[a][b] >= 0) return memo[a][b];
        return memo[a][b] = 0.25 * (dp(max(a-4,0),b) + dp(max(a-3,0),b-1) + dp(max(a-2,0),max(b-2,0)) + dp(a-1,max(b-3,0)));
    }
public:
    double soupServings(int n) {
        if (n >= 4800) return 1.0;
        int units = (n + 24) / 25;
        memo.assign(units+1, vector<double>(units+1, -1));
        return dp(units, units);
    }
};

Explanation

This is a probability problem solved with memoized recursion. From any state we have four equally likely serving operations, so the answer for a state is just the average (each weighted by 0.25) of the answers for the four states it leads to.

First a neat shortcut: every serving amount is a multiple of 25ml, so we rescale by dividing by 25, turning n ml into units "quarter portions." That shrinks the state space a lot. The four operations then subtract (4,0), (3,1), (2,2), (1,3) from (a, b).

The base cases capture who empties first: if both empty together return 0.5 (a tie counts half), if only a empties return 1.0 (A finished first — a full win), and if only b empties return 0.0. lru_cache stores each (a, b) so it is computed once.

There is also a large-n shortcut: when n >= 4800, operations that drain A are heavier, so the probability A empties first races to essentially 1, and we just return 1.0 without any recursion.

Example: for n = 50 the recursion fans out over the small grid and returns 0.625. Each state is solved once, so the cost is roughly O(n²) in the rescaled units.

Time: O(n^2) Space: O(n^2)