Cherry Pickup


  • 2

    Click here to see the full article post


  • 0
    Y

    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.


  • 0
    E

    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 write-ups. 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


  • 0

    @yren2 Corrected, thanks.
    @eggeggegg Thanks, appreciate it.


  • 0
    X

    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];
        }
    }
    

  • 0

    @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 re-update 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 re-update the state from bottom right to top left.


  • 0
    X

    @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:)


  • 0
    M

    Kindly noted, the Python solution has TLE. I think the problem should grant more time for Python..


  • 0

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


  • 0
    M

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


  • 0
    S

    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] and dp[r1][c1+1][c2] represent person1 taking a single step (either down or to right). But what does dp[r1+1][c1][c2+1] and dp[r1][c1+1][c2+1] mean? According to equation r2 = r1 + c1 - c2, plugging first set of coordinates in, r2 = (r1+1)+c1-(c2+1), 1's cancel out and r2=r1+c1-c2, stays the same. Is it supposed to be person2 taking a step?


  • 0
    S

    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 right

    The directions are a little confusing, but I am glad I am able to understand it. This might be helpful as part of the explanation! :)


  • 0
    M

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


  • 0
    P

    Thank you for your great detailed solutions.
    For Approach #3 it could get little improvement with just flipping dp and dp2 without new dp2 many times in loop.


Log in to reply
 

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