11153 - Museums

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

rimu
New poster
Posts: 9
Joined: Sat Feb 26, 2005 4:41 pm

11153 - Museums

Post by rimu » Sun Dec 31, 2006 8:56 am

my dfs (backtracking) solution is getting TLE
what heuristics may i add to cut the run time?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Dec 31, 2006 10:20 am

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.

Hao Hu
New poster
Posts: 5
Joined: Mon Jan 01, 2007 8:22 am
Location: Nanjing University, China
Contact:

Post by Hao Hu » Mon Jan 01, 2007 10:55 am

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Jan 01, 2007 3:56 pm

Another hint:
Precalculate the fastest routes between any two nodes. You are not interested in how many times you passed a node, just how many times a route stops there, so you can imagine having direct connections corresponding to fastest routes.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Jan 01, 2007 4:40 pm

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Jan 01, 2007 4:48 pm

Yes, that was also my method. I just wanted to show how to optimize his dfs function.

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Mon Jan 01, 2007 9:57 pm

This trick is often being met on TC events...
Remember Never Give Up
Regrads
Miras

coolguy
New poster
Posts: 30
Joined: Tue Oct 17, 2006 5:59 pm

Post by coolguy » Tue Jan 02, 2007 2:38 am

mf wrote:
Actually, 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.
but what about the restriction on the money. how are you gonna handle it ??? please help
BYE
In good company

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Jan 02, 2007 3:14 am

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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Jan 02, 2007 3:15 am

coolguy wrote:but what about the restriction on the money. how are you gonna handle it ??? please help
As I said, you can actually generate and check every possible subset of museums. Just ignore those subsets, which you can't afford due to time or money contraints.

coolguy
New poster
Posts: 30
Joined: Tue Oct 17, 2006 5:59 pm

thank you

Post by coolguy » Tue Jan 02, 2007 3:55 am

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
In good company

rimu
New poster
Posts: 9
Joined: Sat Feb 26, 2005 4:41 pm

Post by rimu » Tue Jan 02, 2007 7:29 am

To mf:
how to code using bitmask dp? i googled but found
nothing. can you tell me how it is done or give me
any link from where i can learn it?


To observer:
can you give some hint on the Dijkstra method of
solving this problem?


Thanks.
i'll be back

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Jan 02, 2007 7:41 am

About the Dijkstra method:
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.
This hint by Adrian basically describes how we can apply Dijkstra algorithm. :D

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

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

Post by rammestain » Thu Aug 16, 2007 9:30 am

I got several WA for this problem, :(
please give me some IO

Bert
New poster
Posts: 3
Joined: Mon Jun 19, 2006 9:57 am
Location: Hong Kong

Post by Bert » Wed Aug 29, 2007 8:21 am

Ya, can anyone post some tricky test cases?

Post Reply

Return to “Volume 111 (11100-11199)”