aajjbb's blog

Longest-Sum Path in a Rectangle
By aajjbb, 12 years ago, In English

Hi, I'm strugglin with the follow problem; Given a N * M rectangle with nums between -500 — 500, return the values of the longest sum of cells from cell (0, 0) to cell (N-1, M-1), you can make the moves (i + 1, j), (i, j + 1) and (i, j — 1), you can only visit a cell one time.

I tried the DP strategy:

//dp[i][j] is the longest sum path until the cell (i, j)
//maze[i][j] value in the cell (i, j)
dp[i][j] = max(maze[i][j], max(dp[i - 1][j] + maze[i][j], max(dp[i][j - 1] + maze[i][j], dp[i][j + 1] + maze[i][j])));

this strategy isn't working due to the test case:

81 28 240 10
40 10 100 240
20 180 110 35

the answer is: 1094 this strategy returns: 724.

what is the optimal strategy ? Thanks.

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

»
12 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

An obviously cubic solution:

dp[0][0] = maze[0][0];
for (int i = 0; i < n - 1; i++) {
	for (int j = 0; j < m; j++) {
		if (i == 0 && j != 0) {
			continue;
		}
		int leftsum = 0;
		for (int k = j - 1; k >= 0; k--) {
			leftsum += maze[i][k];
			dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + leftsum + maze[i + 1][k]);
		}
		int rightsum = 0;
		for (int k = j + 1; k < m; k++) {
			rightsum += maze[i][k];
			dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + rightsum + maze[i + 1][k]);
		}
	}
}

The answer will be in dp[n - 1][m - 1].

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

    Thanks, your approach is clever than mine, but it yet results 724 on this test case I've posted before...

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

      Try to transpose matrix (or simply change order of indexes and their bounds).

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

Your strategy is solving problem with different set of moves.

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

It's problem from Timus Online Judge again :) Timus is offline now, so this is Google cache link: 1029 — Ministry.
One difference is that you should find the minimal path, not maximal.

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

    Minimal path can be solved with more optimal (and obvious :) dijkstra in n2logn.

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

      Yes, I've started with the Dijsktra idea, but it doesn't work for 'Longest-Paths', so I moved to the dp solution, which isn't working till now..

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        It still can be solved in O(n*m) using graphs.
        Let's split each cell into three vertices:
        0 if we came using i+1 and can move in any allowed direction;
        1 if we came using j-1 and unable to move back(increasing j);
        2 if we came using j+1 and unable to move back(decreasing j).

        So there would be such edges(of course if they do not go out of the field): 

        [i][j][0] -> [i+1][j][0]  
[i][j][0] -> [i][j-1][1]  
[i][j][0] -> [i][j+1][2]  
[i][j][1] -> [i+1][j][0]  
[i][j][1] -> [i][j-1][1]  
[i][j][2] -> [i+1][j][0]  
[i][j][2] -> [i][j+1][2]

        such graph is acyclic so simple DFS/BFS will solve problem.

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

We can solve it in O(n*m) time. We can use DP with 3 parameters — current row, current column, and another parameter, which describes the direction we used to get on our current cell.

UPD: Oh, there was a silly bug in previous implementation (I forgot that the matrix can contain negative numbers). So, I believe that the right code is in Rev.5

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

I hope it is true solution:

for(i = 1; i <= m; i++)
    dp[1][i] = sum[1][i];

for(i = 2; i <= n; i++){
    for(j = 1; j <= m; j++){
        dp[i][j] = -INF;
        for(k = 1; k <= m; k++){
            if(k<=j)
                dp[i][j] = max(dp[i][j], dp[i-1][k] + sum[i][j] - sum[i][k-1]);
            else
                dp[i][j] = max(dp[i][j], dp[i-1][k] + sum[i][k] - sum[i][j-1]);
        }
    }
}

where sum[i][j] is sum of i'th row from 1 to j inclusive and dp[i][j] is the values of the longest sum of cells from cell (1, 1) to cell (i, j).

Answer will be in dp[n][m].

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

    This problem is trickier than I thought, this soluition looks correct, but In the test case I posted on previously, it returns 395. weird.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
      81 28 240 10
40 10 100 240
20 180 110 35

      for this test case ??? my comp returns 1094 !

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
        #include<stdio.h>
#include<algorithm>
using namespace std;

#define sc scanf
#define pr printf
#define INF 2000000000
#define MN 1002
int n, m, maze, dp[MN][MN], sum[MN][MN], i, j, k;
main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
sc("%d%d", &n, &m);
for(i = 1; i <= n; i++){
    for(j = 1; j <= m; j++){
        sc("%d", &maze);
        sum[i][j] = sum[i][j-1]+maze;
    }
}
for(i = 1; i <= m; i++)
    dp[1][i] = sum[1][i];

for(i = 2; i <= n; i++){
    for(j = 1; j <= m; j++){
        dp[i][j] = -INF;
        for(k = 1; k <= m; k++){
            if(k<=j)
                dp[i][j] = max(dp[i][j], dp[i-1][k] + sum[i][j] - sum[i][k-1]);
            else
                dp[i][j] = max(dp[i][j], dp[i-1][k] + sum[i][k] - sum[i][j-1]);
        }
    }
}
pr("%d\n", dp[n][m]);
return 0;
}
        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I'm sorry, your solution get TLE, ivan100sic solution is the one which get wrong answer... I'm really lost now, I think the solution must be O(N^2), but I can't think in a faster solution, they both looks right, I can't think the test case ivan100sic fails also.

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

            What about Fcdkbear's solution ???

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

              This solution gets WA... I really can't think in other possible states for this problem.

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

                What about my idea? Did you tested it?

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

                  I think, our ideas are almost identical. The only difference is that I don't build graph physically.

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

                Can you give a link to the problem? For example, constant -1000000000 depends on sizes of the rectangle.

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

                  Link I'm seeing your idea now, I'm confused in the way you are building the edges.

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

                  Got AC:) It was not so easy, because I don't know Portugal language and this problem has strange time limit(1-2 seconds, as it was mentioned in the problem statement :))
                  There was a bug in my code(in one place we should use y>0, not y>=0). So here is the link to my code.

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

                  Oh, thank you, I'm analyzing your code right now, as I'm newbie in this DP in recurrence relations with memorization I'll take a while do understand everything, thank you. if you know problems like these (with memorization with recursion solution) I'd appreciate if you send me, once again, thanks.

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

                  For example, a lot of this problems can be solved using recursion with memorization.

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

I think I have a linear time solution for this one, i'll post it soon.

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

    There you go, give it a spin:

    memset(Dp,128,sizeof(Dp)); //sets everything to -INF
    Dp[1][1] = A[1][1];
    for (i=2; i<=N+1; i++){
        //solving the i-th row will take 2 passes:
        memset(Left,128,sizeof(Left)); 
        memset(Right,128,sizeof(Right));
        Left[1] = Dp[i-1][1] + A[i][1];
        for (j=2; j<=M; j++) Left[j] = A[i][j] + max(Left[j-1] - A[i][j-1] + A[i-1][j] , Dp[i-1][j]);
        Right[M] = Dp[i-1][M] + A[i][M];
        for (j=M-1; j; j--) Right[j] = A[i][j] + max(Right[j+1] - A[i][j+1] + A[i-1][j] , Dp[i-1][j]);
        for (j=1; j<=M; j++) Dp[i][j] = max(Left[j],Right[j]);
    }

    The solution can be found in Dp[N+1][M] I used the (1,1)..(N,M) convention. Dp[i][j] stores the maximum value of a valid path from (1,1)..(i,j) which enters the field (i,j) from above, that is, from (i-1,j).

    Full implementation: Here

    → Reply