rahul_1234's blog

By rahul_1234, history, 6 years ago, In English

Given a matrix of n*n. Each cell contain 0, 1, -1.

0 denotes there is no diamond but there is a path. 1 denotes there is diamond at that location with a path -1 denotes that the path is blocked.

Now you have start from 0,0 and reach to last cell & then return back to 0,0 collecting maximum no of diamonds. While going to last cell you can move only right and down. While returning back you can move only left and up.

Tags #dp
  • Vote: I like it
  • +9
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

This also came in one of my tests. Couldn't come up with anything good. One thing is clear that running naive algorithm twice will give incorrect results.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    It is same as two paths moving simultaneously from start to end. So we can see the distance travelled is always same i.e there are on same diagonal at each moment. So a dp with states as (diagonal,pos1,pos2) can be done with O(1) transitions. Hence O(n*n*n).

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please tell me why standard approach won't work here? That is normal maxCost path.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You cannot just take a path with maximum diamonds twice, you need to consider if a certain diamond was taken or not when going back

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice. Missed it. Thanks!