Formatted question description: https://leetcode.ca/all/808.html

808. Soup Servings

Level

Medium

Description

There are two types of soup: type A and type B. Initially we have N ml of each type of soup. There are four kinds of operations:

  1. Serve 100 ml of soup A and 0 ml of soup B
  2. Serve 75 ml of soup A and 25 ml of soup B
  3. Serve 50 ml of soup A and 50 ml of soup B
  4. Serve 25 ml of soup A and 75 ml of soup B

When we serve some soup, we give it to someone and we no longer have it. Each turn, we will choose from the four operations with equal probability 0.25. If the remaining volume of soup is not enough to complete the operation, we will serve as much as we can. We stop once we no longer have some quantity of both types of soup.

Note that we do not have the operation where all 100 ml’s of soup B are used first.

Return the probability that soup A will be empty first, plus half the probability that A and B become empty at the same time.

Example:

Input: N = 50

Output: 0.625

Explanation:

If we choose the first two operations, A will become empty first. For the third operation, A and B will become empty at the same time. For the fourth operation, B will become empty first. So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.25 * (1 + 1 + 0.5 + 0) = 0.625.

Notes:

  • 0 <= N <= 10^9.
  • Answers within 10^-6 of the true value will be accepted as correct.

Solution

Since the amount of each type of soup served in ml is always a multiple of 25, divide N by 25 and add the quotient by 1 if there is remainder. For example, if N is 50, then the result after dividing N by 25 is 2. If N is 55, then the result after dividing N by 25 is 3. Let unit be the result after dividing N by 25.

Use dynamic programming. Create a 2D array dp of type double with units + 1 rows and units + 1 columns, where dp[i][j] represents the probability that soup A will be empty first plus half the probability that A and B become empty at the same time, when starting with i units of soup A and j units of soup B, where one units equals 25 ml of soup. According to the definition, dp[0][0] = 0.5. For i from 1 to units, there is dp[0][i] = 1 and dp[i][0] = 0. Aince four operations are chosen with equal probability, it can be concluded that for 0 < i <= units and 0 < j <= units, dp[i][j] = (dp[i - 4][j] + dp[i - 3][j - 1] + dp[i - 2][j - 2] + dp[i - 1][j - 3) / 4, where negative indices are replaced with index 0 (for example, if i == 3, then dp[i - 4][j] is just the same as dp[0][j]). Finally, dp[units][units] is the required result.

If the input N is very large, the algorithm is quite time-consuming, so other means should be tried for large inputs. It can be seen that when N >= 12500 or units >= 500, the probability is quite close to 1, so simply return 1 if units >= 500. For small inputs, use dynamic programming mentioned above to calculate the probability.

class Solution {
    public double soupServings(int N) {
        int units = (int) Math.ceil(N / 25.0);
        if (units >= 500)
            return 1;
        double[][] dp = new double[units + 1][units + 1];
        dp[0][0] = 0.5;
        for (int i = 1; i <= units; i++) {
            dp[0][i] = 1;
            dp[i][0] = 0;
        }
        for (int i = 1; i <= units; i++) {
            for (int j = 1; j <= units; j++) {
                int i1 = Math.max(i - 4, 0), j1 = j;
                int i2 = Math.max(i - 3, 0), j2 = Math.max(j - 1, 0);
                int i3 = Math.max(i - 2, 0), j3 = Math.max(j - 2, 0);
                int i4 = Math.max(i - 1, 0), j4 = Math.max(j - 3, 0);
                dp[i][j] = (dp[i1][j1] + dp[i2][j2] + dp[i3][j3] + dp[i4][j4]) / 4;
            }
        }
        return dp[units][units];
    }
}

All Problems

All Solutions