Cherry Pickup


Hi @awice,
I think there is a typo in Approach #3 Java code.
Please change "ni" to "pi" and "nj" in "pj" in line 17 and 18.

I've noticed that you've been doing all of the editorial solutions for the contest problems and wanted to say thank you for all of these great solution writeups. I love reading these after struggling through the problems during the contest  you present very well written and easily digestible analyses. Thank you for your time


For solution 3, do we have to set the whole matrix to 1 at the start of each iteration?
Here is my code inspired by solution 3. It passes all current test cases. But I am not sure if it is correct.class Solution { public int cherryPickup(int[][] grid) { int n = grid.length; int[][] state = new int[n][n]; state[0][0] = grid[0][0]; for (int i = 0; i < n; i++) { Arrays.fill(state[i], 1); } state[0][0] = grid[0][0]; for (int m = 1; m < 2 * n  1; m++) { for (int i = Math.min(m, n  1); i >= Math.max(0, m  n + 1); i) { int j = m  i; for (int k = i; k >= Math.max(0, m  n + 1); k) { int l = m  k; if (grid[i][j] == 1  grid[k][l] == 1) { state[i][k] = 1; continue; } if (i > 0 && l > 0) { state[i][k] = Math.max(state[i][k], state[i  1][k]); } if (i > 0 && k > 0) { state[i][k] = Math.max(state[i][k], state[i  1][k  1]); } if (j > 0 && l > 0) { state[i][k] = Math.max(state[i][k], state[i][k]); } if (j > 0 && k > 0) { state[i][k] = Math.max(state[i][k], state[i][k  1]); } if (state[i][k] == 1) { continue; } state[i][k] += (i == k) ? grid[i][j] : grid[i][j] + grid[k][l]; // System.out.println(i + ", " + j + ", " + k + ", " + l + ": " + state[i][k]); } } } return state[n  1][n  1] == 1 ? 0 : state[n  1][n  1]; } }

@xh2277 I think your solution is correct, and it's a good idea.
Look at say, t = 2. We have possible coordinates (r1,c1) = (2,0), (1,1) and (0,2) for a single person. For two people, they can be represented by nine different (c1,c2). [ (0, 1, 2) x (0, 1, 2) where x is the cartesian product.] If we reupdate the state from bottom right to top left, we should be fine.
What about when the possible coordinates shrinks? If say N = 3, then for t = 3 with (2, 1), (1, 2), the possible (c1, c2) are only (1, 2). Investigating that, it remains okay to reupdate the state from bottom right to top left.

@awice
I think I get your point. Appreciate your reply. I think for me it is hard to come up with this solution in a real interview and prove it is correct. Maybe I will try the second approach with more space complexity:)

@manuel333 Which solution specifically is TLE. All solutions have been tested. If you mean Approach #1, that is intentionally WA.

@awice Yeah, you are right. What I mean is, the Python 3 version of your solution 3 will get TLE (c++ will work perfect of course), maybe it is because of the xrange/range overhead in different version... You need to tune the solution 'extremely' exactly for the test case to get a pass. Just a kind note to other ppl, no big deal. It is a good idea.

I'm struggling to understand the solution #2, can someone spare a moment to explain this part to me?
dp[r1][c1][c2] = Math(dp[r1+1][c1][c2], dp[r1][c1+1][c2], dp[r1+1][c1][c2+1], dp[r1][c1+1][c2+1])
There are 2 people walking from (r1, c1) and (r2, c2) to the end.
dp[r1+1][c1][c2]
anddp[r1][c1+1][c2]
represent person1 taking a single step (either down or to right). But what doesdp[r1+1][c1][c2+1]
anddp[r1][c1+1][c2+1]
mean? According to equationr2 = r1 + c1  c2
, plugging first set of coordinates in, r2 = (r1+1)+c1(c2+1), 1's cancel out and r2=r1+c1c2, stays the same. Is it supposed to be person2 taking a step?

Ah I see, both p1 and p2 and taking steps together so that each DP represents both P1 and P2's total number of cherries:
dp[r1+1][c1][c2] = Person 1 moves down, Person 2 moves down
dp[r1][c1+1][c2] = Person 1 moves right, Person 2 moves down
dp[r1+1][c1][c2+1] = Person 1 moves down, Person 2 moves right
dp[r1][c1+1][c2+1] = Person 1 moves right, Person 2 moves rightThe directions are a little confusing, but I am glad I am able to understand it. This might be helpful as part of the explanation! :)

@simonzhu91: One can convert the problem statement to the following equivalent statement:
two person starting from right bottom corner, stepping synchronously left or up, so that they are always located on the same diagonal, collecting maximum possible tokens.Trying to solve the problem with the third approach and a small twist, instead of {x,y} coordinates using {diagonal index, position inside diagonal} coordinates is instructional :).