SoupServings [source code]


public class SoupServings {
static
/******************************************************************************/
class Solution {
    Map<String, Double> memo;

    static int[][] servings = {
        {-100, 0}, {-75, -25}, {-50, -50}, {-25, -75},
    };

    public double soupServings(int N) {
        if (N >= 14000)
            return 1.0;
        memo = new HashMap<> ();
        return search (N, N);
    }

    double search (int A, int B) {
        String memo_key = A + " " + B;
        if (memo.containsKey (memo_key))
            return memo.get (memo_key);
        double res = 0.0;
        if (A <= 0 && B <= 0) {
            res = 0.5;
        } else if (A <= 0) {
            res = 1.0;
        } else if (B <= 0) {
            res = 0.0;
        }
        else {
            for (int[] serve : servings) {
                res += 0.25 * search (A + serve[0], B + serve[1]);
            }
        }
        memo.put (memo_key, res);
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SoupServings.Solution tester = new SoupServings.Solution();
        double[] inputs = {
            50, 0.625,
            1, 0.625,
            51, 0.65625,
            75, 0.65625,
            800, 0.96162,
            100, 0.71875,
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            System.out.println (Printer.separator ());
            int N = (int) inputs[2 * i];
            double ans = inputs[2 * i + 1], output = tester.soupServings (N);
            System.out.printf ("%s\n%s, expected: %f\n", 
                N, Printer.wrap (output + "", output == ans ? 92 : 91), ans
            );
        }
    }
}

看起来是一个概率题, 不过感觉题目意思其实是一个搜索+count的题目;

题目给的例子不够代表性, 所以只能自己举一个例子然后trace;

比想象当中的难很多; 调了半天, 最后被test5也就是800给TLE掉了; 算法本身好像有问题, 本地也跑不完. 尝试加了memo(因为2和4两个operation容易产生等价), 还是不行;

contest刚结束时候的rate:

排行榜也只有前15名做出来了; 哦不对, 后面也有零星做出来的人;

草稿:

看了contest一个中国人的做法之后(下面), 感觉我这个加个memo应该可以啊; 我先尝试改一下, 这个是我原来的做法:

class Solution {  
    String indent = "";  
    boolean DEBUG = true;  

    static int[][] servings = {  
        {-100, 0}, {-75, -25}, {-50, -50}, {-25, -75},  
    };  

    public double soupServings(int N) {  
        double[] scales = {1.0, 1.0, 1.0};  
        if (N > 100) {  
            int count = N / 100;  
            for (int i = 0; i < 3; i++)  
                scales[i] *=   
            N = N % 100 == 0 ? 100 : N % 100;  
        }  
        int[] res = search (N, N, 1 << 30);  
        return (double) (res[0] + 0.5 * res[1]) / (res[0] + res[1] + res[2]);  
    }  

    int[] search (int A, int B, int weight) {  
        String old_indent = indent, header = "";  
        if (DEBUG) header = String.format ("%sA:(%d), B:(%d), weight:(%s)", indent, A, B, weight + "");  
        indent += "    ";  
        if (DEBUG) System.out.println (header);  
        int[] res = new int[3];  
        int next_weight = weight >> 2;  
        if (A <= 0 && B <= 0) {  
            res[1] = next_weight;  
        } else if (A <= 0) {  
            res[0] = next_weight;  
        } else if (B <= 0) {  
            res[2] = next_weight;  
        }  
        else {  
            for (int[] serve : servings) {  
                int[] next_res = search (A + serve[0], B + serve[1], next_weight);  
                res[0] += next_res[0];  
                res[1] += next_res[1];  
                res[2] += next_res[2];  
            }  
        }  
        if (DEBUG) System.out.printf ("%s returns %s\n", header, Arrays.deepToString (new int[][] {res}));  
        indent = old_indent;  
        return res;  
    }  
}

2018-05-02 01:36:01 其实上面代码本身的设计还是没什么问题的, 这个题目一个比较难的地方在于最后这个base case比较绕人; 当时写A和B一起neg0, 实际上也是有点误打误撞的.

然后发现我的memo好像做的不对:

java> Map<int[], Integer> map = new HashMap<> ()  
java.util.Map<int[], java.lang.Integer> map = {}  
java> map.put (new int[] {1,1}, 1)  
java.lang.Object res1 = null  
java> map  
java.util.Map<int[], java.lang.Integer> map = {[I@6324f0b8=1}  
java> map.put (new int[] {1,1}, 2)  
java.lang.Object res2 = null  
java> map  
java.util.Map<int[], java.lang.Integer> map = {[I@54780c4f=2, [I@6324f0b8=1}

这就很尴尬了; 这个我是自己忘记了, array的hash是无效的!!!

然后加上一个正常的memo:

class Solution {  
    String indent = "";  
    boolean DEBUG = true;  
    Map<String, int[]> memo;  

    static int[][] servings = {  
        {-100, 0}, {-75, -25}, {-50, -50}, {-25, -75},  
    };  

    public double soupServings(int N) {  
        memo = new HashMap<> ();  
        int[] res = search (N, N, 1 << 30);  
        return (double) (res[0] + 0.5 * res[1]) / (res[0] + res[1] + res[2]);  
    }  

    int[] search (int A, int B, int weight) {  
        String memo_key = A + " " + B;  
        if (memo.containsKey (memo_key))  
            return memo.get (memo_key);  
        String old_indent = indent, header = "";  
        if (DEBUG) header = String.format ("%sA:(%d), B:(%d), weight:(%s)", indent, A, B, weight + "");  
        indent += "    ";  
        if (DEBUG) System.out.println (header);  
        int[] res = new int[3];  
        int next_weight = weight >> 2;  
        if (A <= 0 && B <= 0) {  
            res[1] = next_weight;  
        } else if (A <= 0) {  
            res[0] = next_weight;  
        } else if (B <= 0) {  
            res[2] = next_weight;  
        }  
        else {  
            for (int[] serve : servings) {  
                int[] next_res = search (A + serve[0], B + serve[1], next_weight);  
                res[0] += next_res[0];  
                res[1] += next_res[1];  
                res[2] += next_res[2];  
            }  
        }  
        if (DEBUG) System.out.printf ("%s returns %s\n", header, Arrays.deepToString (new int[][] {res}));  
        indent = old_indent;  
        memo.put (memo_key, res);  
        return res;  
    }  
}

还是不对; 这个时候就已经撞上了我这个方法的死结; 就是因为我的方法是依赖于count的, 所以最后的base case的定义, 会有点麻烦, 我先尝试改成他的这种直接计算概率的做法, 看看行不行;

然后按照看到的那个中国人的做法, 果然就AC了;

另外他这个14000的预处理, 不是随便搞得, 后面真的有一个六万多的数字的case, 然后这个会爆栈;

所以这个人应该也是稍微试探了一下OJ的, 不然鬼晓得他这个14000是怎么来的;

800得到的结果好像实际上还是有点浮点差异, 不过好像OJ也算过了;

那么下面要回答的问题就是, 为什么我直接count的办法不行;

另外注意这题是leaf位置判断base case更加方便, 一直在debug, 忘记提这茬了;

回头继续看我的代码, 发现一个毛病: base case里面给的应该是weight而不是next_weight; 不过这个改过来之后, 其他的test没有被break, 800这个还是不对;

最后破案了, 这个代码是能AC的:

class Solution {  
    Map<String, double[]> memo;  

    static int[][] servings = {  
        {-100, 0}, {-75, -25}, {-50, -50}, {-25, -75},  
    };  

    public double soupServings(int N) {  
        if (N > 14000)  
            return 1.0;  
        memo = new HashMap<> ();  
        double[] res = search (N, N, 1);  
        return (res[0] + 0.5 * res[1]) / (res[0] + res[1] + res[2]);  
    }  

    double[] search (int A, int B, double weight) {  
        String memo_key = A + " " + B;  
        if (memo.containsKey (memo_key))  
            return memo.get (memo_key);  
        double[] res = new double[3];  
        double next_weight = weight * 0.25;  
        if (A <= 0 && B <= 0) {  
            res[1] = weight;  
        } else if (A <= 0) {  
            res[0] = weight;  
        } else if (B <= 0) {  
            res[2] = weight;  
        }  
        else {  
            for (int[] serve : servings) {  
                double[] next_res = search (A + serve[0], B + serve[1], next_weight);  
                res[0] += next_res[0];  
                res[1] += next_res[1];  
                res[2] += next_res[2];  
            }  
        }  
        memo.put (memo_key, res);  
        return res;  
    }  
}

问题出在这里, 我的weight一开始给的最大值是1<<30, 结果看了一下trace之后发现, 800的N的时候, 最后这个weight居然是不够的;

2018-05-02 01:38:35 这个不够的意思是, 比如我给你8, 第一次分成4个2, 然后你这个2就没法儿分了: 再/4直接就变成0了, 这个有问题, 你2应该分成4个0.5, 不能变0, 所以最后不用double是不行的;

这种情况下, 只能干脆用double来计算算了; 因为我的weight还是代表一个node可以分配的distribution mass, 所以最后double本身并没有问题, 毕竟概率本来就是用[0,1]的浮点数比用count来表示更加的合理; 这里也是题目要求比较严格, 没有办法用count的方法来做了;

另外尽管这样, 严格来说我目前的水平还是不能算作是这题contest里面做出来了, 因为我没有想到:

不要用array作为hash的key: 这个主要还是手生, 其实是应该意识到的;
学会他们这里这种, 很ad-hoc的, 当时看OJ的结果之后, 想到用14000这样的一个数字来prune一下; 当然真正面试的时候肯定不行, 除非你敢说"我估计这么大的话, A获胜的概率几乎为100%了", 不过这种说法感觉面试的时候还是有点坑.

总体来说也是不错的体验;

另外对于这个base case的设置方式(比如为什么假如是(0, 10), 立刻就判断为A胜利)还是有点疑问. 就按照(0, 10)这个来说, 我认为应该继续再向下走一层? 这个可能看不出来, 比如(10, 0), 那么下一层是(-90, 0), (-65, -25), (-40, -50), (-15, -75), 这些应该判断为A, T, T, T, 所以实际上B并没有把(10, 0)的所有的概率都分走. 但是按照这里的这个base case的设置方式, 明显他们认为就应该是这样的;

我再想想:
因为题目是这样定义的, 反正在(10, 0)这里, 操作1是可以完成的(因为B足够, 虽然A不够). 操作234当然是不行的, 按照题目定义应该是停止, 所以(10, 0)按照0.25的概率到(-90, 0), 然后剩下的0.75((10, 0)的), 全都停止在(10, 0), 这个都属于是B胜利, 而0.25到(-90, 0)的这个, 应该算作是tie? 所以最后我还是不认为(10, 0)应该全部都算给B胜利; 虽然这里的代码写法明显是这样了;

不对, 我感觉是我自己没有理解清楚:

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.

所以这个意思其实是, 停止是, 只有0,0的时候才停止; 是这个意思吗; 只要两种当中至少还有一种有剩余, 就不停止;

仔细想了一下, 还是第二句我自己没有理解好; 其实这里的意思就是, 必须A和B都>0, 才能继续; 假如两个当中有任何一个没有了(到0了), 就停止;

感觉还是英语阅读的问题; 这种问题真正面试的时候自己还是得问清楚;

editorial

号称是O(1)的DP解法;

Approach #1: Dynamic Programming [Accepted]

Intuition

First, we can simplify all the numbers by dividing by 25. More specifically, each unit is 25ml, and partial quantities of 25ml are rounded up to a full quantity.

这个观察不错;

When N is small, this is a relatively straightforward dynamic programming problem: we have quantities of soup represented by the state (x, y), and we can either go to (x-4, y-0), (x-3, y-1), (x-2, y-2), or (x-1, y-3) each with equal probability.

When N is very large, this approach fails, so we need a different idea.

也没说为什么N很大的时候就fail了; 另外这里也是暴露一个问题, 我上面这个解法这个14000, 是有点赖皮的: awice这里就是明确告诉你了: 这题难就难在N很大的时候不好处理, 你直接一个special case处理掉了, 有点骗自己;

Instead of serving in batches of (4, 0), (3, 1), (2, 2), (1, 3), pretend we serve (1, 0) on the side first, and then serve from the fair distribution (3, 0), (2, 1), (1, 2), (0, 3). If the pots of soup initially start at (N, N), then after roughly less than N/2 servings, one pot will still have soup. Because of the (1, 0) servings on the side, this means that roughly speaking, pot A is used first if we serve N/2 fairly from the first pot before N from the second pot.

(3, 0), (2, 1), (1, 2), (0, 3)这个分布是很有意思的, 你看A和B的serving, 其实都是3,2,1,0, 所以如果算概率, 很容易的可以估计, 一次serving大概每一个减少1.5(需要用到对称这个条件);
另外他这里最后一句话我没看懂, 不过他这个大概意思还是理解了;

When N is very large, this almost always happens (better than 99.9999%, so we can output 1), and we can check this either experimentally or mathematically.

说的真好听, 大N最后还是赖皮处理; 不过数学上面只要面试能说清楚, 也还行吧; 另外注意他这里是/25 过了, 所以你看他下面代码的这个500, 实际上处理的是7500. 一开始N就/25的一个好处也包括了最后数字计算overflow什么的可能性也低一些. 不对, 其实无所谓, 就是自己想的时候方便一些;

Algorithm

We convert all units by dividing by 25 and rounding up. If N >= 500 (in new units), then by the above argument the answer is 1.

Otherwise, we will perform a dynamic programming algorithm to find the answer. Our Java implementation showcases a "bottom-up" approach, that fills memo diagonally from top left to bottom right, where s = i + j is the sum of the indices. Our Python implemtation showcases a "top-down" approach that uses memoization.

class Solution {  
    public double soupServings(int N) {  
        N = N/25 + (N%25 > 0 ? 1 : 0);  
        if (N >= 500) return 1.0;  

        double[][] memo = new double[N+1][N+1];  
        for (int s = 0; s <= 2*N; ++s) {  
            for (int i = 0; i <= N; ++i) {  
                int j = s-i;  
                if (j < 0 || j > N) continue;  
                double ans = 0.0;  
                if (i == 0) ans = 1.0;  
                if (i == 0 && j == 0) ans = 0.5;  
                if (i > 0 && j > 0) {  
                    ans = 0.25 * (memo[M(i-4)][j] + memo[M(i-3)][M(j-1)] +  
                                  memo[M(i-2)][M(j-2)] + memo[M(i-1)][M(j-3)]);  
                }  
                memo[i][j] = ans;  

            }  
        }  
        return memo[N][N];  
    }  

    public int M(int x) { return Math.max(0, x); }  
}

非常简短;

因为一开始的/25, 最后memo写起来也很简单;

你说是就是吧;

UNFINISHED

uwi:

class Solution {  
    public double soupServings(int N) {  
        if(N == 0)return 0.5;  
        if(N >= 10000)return 1.;  
        int n = (N+24)/25;  
        double[] dp = new double[n+1];  
        dp[n] = 1;  
        double P = 0;  
        for(int i = 0;i <= n/2+1;i++){  
            for(int j = 0;j <= n;j++){  
                for(int k = 1;k <= 4;k++){  
                    int b = 2*n-4*(i+1)-(j-k);  
                    if(j-k <= 0){  
                        if(b <= 0){  
                            P += dp[j]/4/2;  
                        }else{  
                            P += dp[j]/4;  
                        }  
                    }else if(b <= 0){  
                    }else{  
                        dp[j-k] += dp[j]/4;  
                    }  
                }  
                dp[j] = 0;  
            }  
        }  
        return P;  
    }  
}

好像是个DP做法; 难怪这么难;

这个是另外一个台湾人的:

const int M = 1000;  
double dp[M][M];  

class Solution {  
public:  
    double soupServings(int N) {  
  for (int i = 0; i < M; ++i) {  
    for (int j = 0; j < M; ++j) {  
      if (i == 0 && j == 0) dp[i][j] = 0.5;  
      else if (i == 0) dp[i][j] = 1;  
      else if (j == 0) dp[i][j] = 0;  
      else {  
        dp[i][j] = 0;  
        dp[i][j] += dp[max(0, i - 4)][j];  
        dp[i][j] += dp[max(0, i - 3)][max(0, j - 1)];  
        dp[i][j] += dp[max(0, i - 2)][max(0, j - 2)];  
        dp[i][j] += dp[max(0, i - 1)][max(0, j - 3)];  
        dp[i][j] /= 4.0;  
      }  
    }  
  }  
  N = (N + 24) / 25;  
        if (N < M) return dp[N][N];  
        return 1.0;  
    }  
};

代码更加简洁;

这个是一个中国人的Top-Down的做法:

class Solution(object):  
    def soupServings(self, N):  
        """  
        :type N: int  
        :rtype: float  
        """  
        self.memo = {}  
        if N >= 14000: return 1.0  
        return self.solve(N, N)  
    def solve(self, A, B):  
        if A <= 0 and B <= 0: return 0.5  
        if A <= 0: return 1  
        if B <= 0: return 0  
        if (A, B) in self.memo:  
            return self.memo[(A, B)]  
        ans = 0.25 * (self.solve(A - 100, B) + self.solve(A - 75, B - 25) + self.solve(A - 50, B - 50) + self.solve(A - 25, B - 75))  
        self.memo[(A, B)] = ans  
        return ans

这个代码极其简单啊, 为什么我的就不行呢? 感觉跟我的差不多啊;

Problem 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:

Serve 100 ml of soup A and 0 ml of soup B
Serve 75 ml of soup A and 25 ml of soup B
Serve 50 ml of soup A and 50 ml of soup B
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.

Difficulty:Medium
Total Accepted:1.6K
Total Submissions:5.2K
Contributor:awice
Companies
google
Related Topics
dynamic programming

LC826 SoupServings

SoupServings [source code]

editorial

Approach #1: Dynamic Programming [Accepted]

Problem Description

results matching ""

No results matching ""