Longest-Sum Path in a Rectangle

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

Jacob

12 лет назад, # |

Your strategy is solving problem with different set of moves.

→ Ответить

dalex

12 лет назад, # |

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.

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

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..

→ Ответить

12 лет назад, # ^ |

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.

→ Ответить

12 лет назад, # |

← Rev. 7 →

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

→ Ответить

12 лет назад, # ^ |

What do you mean with 'In Rev.5' ?

→ Ответить

12 лет назад, # ^ |

I mean that the code is in revision 5 of my last post. If you can't find it, here it is

→ Ответить

12 лет назад, # |

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].

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

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

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

→ Ответить

12 лет назад, # ^ |

#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;
}

→ Ответить

12 лет назад, # ^ |

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.

→ Ответить

12 лет назад, # ^ |

What about Fcdkbear's solution ???

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

What about my idea? Did you tested it?

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

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.

→ Ответить

12 лет назад, # ^ |

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.

→ Ответить