Soup Servings - Practice Coding Problems

Soup Servings - Problem

You have two soups, A and B, each starting with n mL. On every turn, one of the following four serving operations is chosen at random, each with probability 0.25 independent of all previous turns:

Pour 100 mL from type A and 0 mL from type B
Pour 75 mL from type A and 25 mL from type B
Pour 50 mL from type A and 50 mL from type B
Pour 25 mL from type A and 75 mL from type B

Note: There is no operation that pours 0 mL from A and 100 mL from B. The amounts from A and B are poured simultaneously during the turn. If an operation asks you to pour more than you have left of a soup, pour all that remains of that soup. The process stops immediately after any turn in which one of the soups is used up.

Return the probability that A is used up before B, plus half the probability that both soups are used up in the same turn.

Answers within 10^-5 of the actual answer will be accepted.

Input & Output

Example 1 — Small Case

$ Input: n = 50

› Output: 0.625

💡 Note: With 50mL each, there are limited serving combinations. A has higher probability of finishing first due to higher average serving rate (62.5 vs 37.5 mL per turn).

Example 2 — Medium Case

$ Input: n = 100

› Output: 0.71875

💡 Note: With 100mL each, the probability increases as the law of large numbers makes A's higher serving rate more apparent.

Example 3 — Large Case

$ Input: n = 5000

› Output: 1.0

💡 Note: For large n, A's 67% higher serving rate means it will almost certainly finish first. The probability approaches 1.0.

Constraints

0 ≤ n ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Initial State

Both soups start with n mL

Random Operations

Four operations with different A:B serving ratios

Probability

Calculate P(A finishes first) + 0.5×P(both finish together)

Key Takeaway

🎯 Key Insight: Soup A has a higher average serving rate, making it more likely to finish first

Asked in

G Google 15 M Microsoft 12

The key insight is recognizing that soup A has a higher average serving rate (62.5 mL vs 37.5 mL per turn), making it more likely to finish first. Best approach uses memoized dynamic programming with mathematical optimization for large inputs. Time: O((n/25)²), Space: O((n/25)²)

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Dynamic Programming	O((n/25)²)	O((n/25)²)	Use memoization to cache results and avoid recalculating the same states
Recursive Brute Force	O(4^(n/25))	O(n/25)	Calculate probability by exploring all possible serving sequences recursively
Mathematical Optimization	O(1) for n≥5000, O((n/25)²) otherwise	O(1) for n≥5000, O((n/25)²) otherwise	For large n, recognize that A almost always finishes first and return 1.0

Memoized Dynamic Programming — Algorithm Steps

Create memo table to store calculated probabilities
Use same recursive logic but check memo first
Store result in memo before returning

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Cache

Look up (A,B) state in memo table

Calculate Once

If not cached, calculate and store result

Reuse Results

Future calls to same state return cached value

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STATES 10000

struct MemoEntry {
    int a, b;
    double prob;
};

struct MemoEntry memo[MAX_STATES];
int memoSize = 0;

double getMemo(int a, int b) {
    for (int i = 0; i < memoSize; i++) {
        if (memo[i].a == a && memo[i].b == b) {
            return memo[i].prob;
        }
    }
    return -1.0;
}

void setMemo(int a, int b, double prob) {
    if (memoSize < MAX_STATES) {
        memo[memoSize].a = a;
        memo[memoSize].b = b;
        memo[memoSize].prob = prob;
        memoSize++;
    }
}

double dfs(int a, int b) {
    double cached = getMemo(a, b);
    if (cached != -1.0) {
        return cached;
    }
    
    if (a <= 0 && b <= 0) {
        return 0.5;
    }
    if (a <= 0) {
        return 1.0;
    }
    if (b <= 0) {
        return 0.0;
    }
    
    double result = 0.25 * (dfs(a - 100, b) + 
                           dfs(a - 75, b - 25) + 
                           dfs(a - 50, b - 50) + 
                           dfs(a - 25, b - 75));
    
    setMemo(a, b, result);
    return result;
}

double solution(int n) {
    memoSize = 0;
    return dfs(n, n);
}

int main() {
    int n;
    scanf("%d", &n);
    double result = solution(n);
    printf("%f\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((n/25)²)

At most (n/25)² unique states to calculate once each

✓ Linear Growth

Space Complexity

O((n/25)²)

Memo table stores results for each unique (A,B) state

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler