3283 Path

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

Post Reply
kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am

3283 Path

Post by kenneth » Thu Sep 29, 2005 3:00 pm

Hi There,

I am trying to solve 3283 by using DFS n times which means my algorithm is O(n ^ 2). However, I get timed out, does anyone have a suggestion on how to solve this problem efficiently?

http://acmicpc-live-archive.uva.es/nuev ... php?p=3283

Thanks

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Re: 3283 Path

Post by misof » Thu Sep 29, 2005 5:17 pm

kenneth wrote:Hi There,

I am trying to solve 3283 by using DFS n times which means my algorithm is O(n ^ 2). However, I get timed out, does anyone have a suggestion on how to solve this problem efficiently?

http://acmicpc-live-archive.uva.es/nuev ... php?p=3283

Thanks
dynamic programming from the leaves upwards
for each vertex compute the longest path going downwards
then, combine this information to get the result (note that each path has one topmost vertex and two paths going down from there)

kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am

Post by kenneth » Sat Oct 01, 2005 5:06 am

Thanks. That will be much more efficient then my current implementation.

However, now I am getting Memory Limit Exceeded. Would anyone have some suggestion? The following is my memory usage:

Code: Select all

typedef vector <map <int, int> > VMII;
typedef vector <int> VI;

int profit(VMII& graph)
{
    int road = 0;
    VI maxPath(graph.size(), 0);
}

Post Reply

Return to “ACM ICPC Archive Board”