goldenskygiang's blog

Maximum sum of 2 paths on a matrix
By goldenskygiang, history, 5 years ago, In English

You're given a matrix $$$A$$$ of size $$$N * M$$$, consisting of integers satisfying $$$|A_{i,j}| \leqslant 100$$$. Rows are numbered $$$1$$$ to $$$N$$$ downward, and columns are numbered $$$1$$$ to $$$N$$$ from left to right. There are 2 players, each one will move from block $$$(1, 1)$$$ to block $$$(N, M)$$$ and can only move to the right or downward. 2 paths made by the 2 players can only have $$$(1, 1)$$$ and $$$(N, M)$$$ as two common blocks. All other blocks in the 2 paths must be distinct. Find the 2 paths that have maximum sum when combined.

Input: the first line consists of 2 numbers $$$N$$$ and $$$M$$$. $$$(N, M \leqslant 200)$$$

Next $$$N$$$ lines consist of $$$M$$$ integers describing the matrix $$$A$$$. Note that $$$A_{1,1} = A_{N,M} = 0$$$.

Output: The maximum sum of the 2 paths.

Example Input:

3 3

0 2 3

4 5 6

7 8 0

Example Output:

32

This problem was included in an offline contest that I participated yesterday. Other contestants said that this is a DP problem but I couldn't figure out the solution.

Tags dp
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by goldenskygiang (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

This is a very old problem from codeforces. You can solve it with dynamic programming on diagonals, dp[diag][p1][p2] -> max sum of two paths, where diag — number of diagonal (row_id+col_id), p1 — position of first player on current diagonal, p2 — position of second player on current diagonal.

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

What are the bounds on N?

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

So the base idea of the solution is to build the two paths simultaneously and basically looks like this:

  static int solve(int x1, int y1, int x2, int y2) {
    if(x1<=0 || x2<=0 || y1<=0 || y2<=0) return -INF;
    if(x1>M || x2>M || y1>N || y2>N) return -INF;
    int sum = A[y1][x1] + A[y2][x2];
    if(x1==x2 && y1==y2) {
      if(x1==M && y1==N) return A[N][M];
      if(x1!=1 || y1!=1) return -INF;
      sum = A[1][1];
    }
    int best = -INF;
    for(int dx1 = 1, dy1 = 0, tmp; dx1>=0; tmp=dx1, dx1=-dy1, dy1=tmp) {
      for(int dx2 = 1, dy2 = 0; dx2>=0; tmp=dx2, dx2=-dy2, dy2=tmp) {
        best = Math.max(best, solve(x1+dx1, y1+dy1, x2+dx2, y2+dy2));
      }
    }
    return best + sum;
  }

Now you have to apply DP on top of this. Naively doing dp[x1][y1][x2][y2] will obviously lead to $$$O(N^2M^2)$$$. The trick is to realize that since the two paths are not independent, i.e. they move forwards at the same speed, you can do dp[moves][y1][y2] and x1 = moves - y1 x2 = moves - y2. This is $$$O((N+M)N^2)$$$.

(Depending on if you opt for 0-indexing or 1-indexing you may need a +/-1 here and there.)

→ Reply