11153  Museums
Moderator: Board moderators
11153  Museums
my dfs (backtracking) solution is getting TLE
what heuristics may i add to cut the run time?
what heuristics may i add to cut the run time?

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
You should avoid to get into equivalent states more than once. Note that a state consists of visited museums, current location and time used.
But this may still be too slow, since there are up to 68927488 states.
Note that actually you are only interested in the minimum time to reach a certain position having visited some subset of the museums.
But this may still be too slow, since there are up to 68927488 states.
Note that actually you are only interested in the minimum time to reach a certain position having visited some subset of the museums.

 New poster
 Posts: 5
 Joined: Mon Jan 01, 2007 8:22 am
 Location: Nanjing University, China
 Contact:
Can you give me some further hint on this problem?
I first thought to use the dynamic programming method that is similar to that in the Hamilton Path which runs in O(2^n*n^2) time but then found one can past a node several times...
my searching + optimization got TLE....
wondering what is the correct method for solving this problem ...
I first thought to use the dynamic programming method that is similar to that in the Hamilton Path which runs in O(2^n*n^2) time but then found one can past a node several times...
my searching + optimization got TLE....
wondering what is the correct method for solving this problem ...
Solo Player

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Actually, just a bitmask of visited museums and current location can be enough. This would be just about 54000 states.Adrian Kuegel wrote:Note that a state consists of visited museums, current location and time used.
But this may still be too slow, since there are up to 68927488 states.
You can use this DP to find minimum time required to visit a subset of museums, and then iterate over all subsets to check their feasibility and pick the one with maximum sum of fun indexes.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
mf wrote:
BYE
but what about the restriction on the money. how are you gonna handle it ??? please helpActually, just a bitmask of visited museums and current location can be enough. This would be just about 54000 states.
You can use this DP to find minimum time required to visit a subset of museums, and then iterate over all subsets to check their feasibility and pick the one with maximum sum of fun indexes.
BYE
In good company
Dear coolguy:
Please think about that yourself! The point you mentioned is important in getting an acceptable solution for this task. Hint: think how money used is computed.
By the way, we have made several judge solutions for this task. The DP one takes 0.2x seconds. Another acceptable solution is Dijkstra. That solution is longer, has an asymptotically larger time complexity, but is easier to understand. That solution takes about 1 second. The two solutions I wrote above are both in PASCAL.
Please think about that yourself! The point you mentioned is important in getting an acceptable solution for this task. Hint: think how money used is computed.
By the way, we have made several judge solutions for this task. The DP one takes 0.2x seconds. Another acceptable solution is Dijkstra. That solution is longer, has an asymptotically larger time complexity, but is easier to understand. That solution takes about 1 second. The two solutions I wrote above are both in PASCAL.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
thank you
hey thank you observer and mf.
just after posting in the board i came to understand what wf was trying to say. i got it accepted less than 1 sec. i wasnt understanding how you decreased your states. now i understand
thank you once again for letting me know about the idea:)
Bye
just after posting in the board i came to understand what wf was trying to say. i got it accepted less than 1 sec. i wasnt understanding how you decreased your states. now i understand
thank you once again for letting me know about the idea:)
Bye
In good company
About the Dijkstra method:
Thinking about the order this Dijkstra goes (i.e. what cases are traversed first) will lead you to the DP solution.
This hint by Adrian basically describes how we can apply Dijkstra algorithm.Adrian Kuegel wrote:Note that actually you are only interested in the minimum time to reach a certain position having visited some subset of the museums.
Thinking about the order this Dijkstra goes (i.e. what cases are traversed first) will lead you to the DP solution.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 New poster
 Posts: 18
 Joined: Fri Apr 21, 2006 11:34 am