Mhammad1's blog

Three paths from top left to bottom right?
By Mhammad1, history, 9 years ago, In English

Hello everyone

The problem:

Given 2d array with numbers inside each cell, you should maximize the cost to get from top left (1,1) to bottom right (N,M) with three paths, When you pass to cell(i,j) the cost inside it will be removed for the next paths.

You're only allowed to move down or right.

How can I solve something like this?

I've read the tutorial here TopCoder Tutorial but I didn't understand the whole concept.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You realise that every time you move downward or to the right, either x or y is increased by 1. So after taking K steps, (x-1) + (y-1) = K.

Therefore, we can represent this DP state as (K, x of first path, x of second path, x of third path) = number of apples received after the first K steps of the three paths. This is O(N^4), which fits the limit of the problem.

Since each x can come from either the same x coordinate or x-1 in the previous diagonal, the transition would be:

f(k, x1, x2, x3) = max(f(k-1, x1, x2, x3), f(k-1, x1, x2, x3-1), f(k-1, x1, x2-1, x3) ... f(k-1, x1-1, x2-1, x3-1)) + (arr[x][k-x] for each unique x among x1, x2, x3)

Therefore we can solve the problem in O(N^4).

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can we use the index of row of x1 so the recurrence will be:

    f(y1, x1, x2, x3) and then we can get the other rows by (y1+x1) ?

    To be more specific, why do we use the steps number not the index of one row?

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

      I think when K >= N, the index of the first row remains at N if I am not mistaken.

      → Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

Note: you can also solve this using mincost maxflow.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we process the 3 path one after the other i.e. 1. find the path with max cost to get from top,left to bottom,right 2. update the cells covered by previous path as 0 (we have used up all the cost) 3. repeat #1 and #2 for second and third path

I don't think the choice of path1 affects path2 and so on, since they wouldn't intersect. What do you guys think?

→ Reply