Soup Servings


  • 0

    Click here to see the full article post


  • 0

    @awice

    1. It's not clear to me how you chose the N >= 500 where you return 1.
    2. If the numbers where not divisible by 25, would the algorithm still work? Would it still be 500?

    I'm still having a hard time understanding the algorithm. From looking at the code, it seems that

    • Normalize N into soup units by dividing by 25 since all the operation is a factor of 25. if this was not true, then you won't be able to do this. This is only an optimization so this part could be left out
    • Then you loop the whole amount of soup which is 2*N = A + B. It looks like you then loop N amount of soup, subtracting how much soup A and B based on how much soup exist (A has) vs. what is left (B has). And i'm guessing because A and B have exactly N amount of soup that is why you loop from 0 to N in the inner loop.
    • In the internal logic of the inner loop, you are trying to calculate the probability = (probability of A being empty first ) + 1/2(probability of A and B both being empty). It will keep looping till, the amount of soup in B is empty or there is no units of soup is left.
      • When there is no soup, that means Probability = 0 + 1/2(1) = 0.5
      • If the soup amount is out of range, set probability to be 0
      • If there is no soup left for A, but there is j amount for B this means that there is a Probability = 1 + 1/2(0) = 1
      • For valid ranges of A and B, it adds up the probability of selecting one of the four operation until there is no soup for B left. Probability = 1/4 (probability of selecting out of the four operation) *
        ((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)] which is basically taking into account the probability calculated for selecting either of the four operations.

    I think it's hard for me to see how the last step is equivalent in calculating (probability of A being empty first ) + 1/2(probability of A and B both being empty).


  • 0
    R

    @dare_wreck54-yahoo-com

    It seems that the probability is monotonic increasing as N grows:

    [(50, 0.625),
     (100, 0.71875),
     (150, 0.7578125),
     (200, 0.796875),
     (250, 0.82763671875),
     (300, 0.8521728515625),
     (350, 0.87255859375),
     (400, 0.8896331787109375),
     (450, 0.9040584564208984),
     (500, 0.916344165802002),
     (550, 0.9268695116043091),
    ...
     (5600, 0.9999990943903253),
    

    5600 / 25 = 224, you can reduce 500 in solution to 224, and it will still pass the grader I believe, since 0.9999990943903253 is within 10^-6 to 1


  • 0
    Q

    How do you determine N=500 (in the new units)? or it is just a large number?


  • 0
    Z

    Returning 1.0 when N >= 500 is a trick here, so the time complexity is in fact O(N^2) instead of O(1), I think.


  • 0
    Z

    No need to decide N >= 500 or some number, since you don't know the number beforehand!
    My approach is just initialize all with 1.0. Then during the bottom-up, just jump out of loop if 1 - dp[i][i] < 10^-6.
    It makes much more sense..

    public double soupServings(int N) {
    if(N > 100000) return 1.0; // put any making-sense large number here to save space
    int n = (int) Math.ceil(N / 25.0);
    double[][] dp = new double[n + 1][n + 1];
    for(int i = 0; i <= n; i++){
    Arrays.fill(dp[i], 1);
    }
    dp[0][0] = 0.5;
    for(int i = 1; i <= n; i++){
    dp[i][0] = 0;
    }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = 0.25 * (dp[M(i - 4)][j] + dp[M(i -3)][j - 1] 
                                   + dp[M(i - 2)][M(j - 2)] + dp[i - 1][M(j - 3)]);
                if(1 - dp[i][j] < 0.000001)
                    break;
            }
            if(1 - dp[i][i] < 0.000001)
                break;
        }
        return dp[n][n];
    }
    

    private int M(int i){
    return Math.max(i, 0);
    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.