# Soup Servings

• @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).

• @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

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

• 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.

• 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);
}

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