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


Log in to reply
 

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