11635 - Hotel booking

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

Moderator: Board moderators

Target979
New poster
Posts: 5
Joined: Wed Oct 08, 2014 10:52 am

Re: 11635 - Hotel booking

Post by Target979 » Wed Oct 08, 2014 2:30 pm

I always (in the code) visit a city if it can be reached in less time than any of the previous visits during the same day or if it hasn't been visited yet. This cover all cases I can think of. I get the correct output for all testcases in this thread but WA when I submit :cry:

catweazle352
New poster
Posts: 10
Joined: Wed Aug 14, 2013 7:53 pm

Re: 11635 - Hotel booking

Post by catweazle352 » Wed Oct 08, 2014 3:11 pm

I am not quite sure if I understand your bfs code correctly, so I'd like to apologize in advance for any misunderstanding. I think one must use a kind of priority queue of visits during the bfs in order to get the correct answer and I cannot quite find a prio queue in your code (Sorry again if I misunderstood your code).

My strategy was to store all "visits" (consisting of the city, the preceeding visit, the no of hotels slept in (including this visit) and the minutes since last sleeping visit) into a prio queue.

Then I did a bfs. During that bfs I created new "visits" into my prio queue. But I did *not* use *each* edge but checked each edge of the current node and checked each edge against those visits stored in the prio queue in order to avoid cycling infinite. The distance criteria I used was a pair consisting of (#1No Of Hotels, #2minutes since last stay).

That strategy worked for me.

Kind Regards

Christof
It's easy to beef about something - but it's much harder to make it better

Target979
New poster
Posts: 5
Joined: Wed Oct 08, 2014 10:52 am

Re: 11635 - Hotel booking

Post by Target979 » Wed Oct 08, 2014 3:33 pm

My approach is to perform a bfs-search from the first node and visit all nodes I can visit without violating the time constraint. All nodes encountered containing a hotel are added to a queue and if the final node is reached the algorithm terminates. Once no more nodes can be reached a new bfs-search is performed from every hotel node in the queue and adding all reachable hotels. This continue until there are no more hotels to visit or a solution is found.

I think it should be possible to solve it with this approach, but I will have a look at your suggestion and see what I can come up with.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11635 - Hotel booking

Post by brianfry713 » Wed Oct 08, 2014 9:21 pm

Input:

Code: Select all

19
10 2 4 5 6 8 9 10 11 15 19
17
16 2 160
8 2 511
19 3 58
6 4 292
17 3 125
4 10 196
2 17 513
9 12 295
1 6 579
16 3 577
14 12 593
15 2 18
17 9 295
17 4 89
1 2 431
10 6 83
4 15 396
0
AC output:

Code: Select all

1
Check input and AC output for thousands of problems on uDebug!

Target979
New poster
Posts: 5
Joined: Wed Oct 08, 2014 10:52 am

Re: 11635 - Hotel booking

Post by Target979 » Thu Oct 09, 2014 1:29 am

Think there must be an error in your AC output (should be one). The following path can be taken with one hotel stay: 1 - 6 STAY 6 - 10 - 4 - 17 -3 - 19.

By the way thanks to all of you for taking some of your time to help me out. Really appreciated.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11635 - Hotel booking

Post by brianfry713 » Thu Oct 09, 2014 8:50 pm

You are correct, I edited my previous post.

See:
http://www.udebug.com/UVa/11635
Click "Random Input", "Go!"
Your code fails on some of them.

I solved it by running Dijkstra's Algorithm once for each day until you reach city n or can't reach a hotel you haven't already stayed at. On day 0 you start from only city 1, on each following day you start from all hotels you could reach the previous day and hadn't already stayed at.
Check input and AC output for thousands of problems on uDebug!

Target979
New poster
Posts: 5
Joined: Wed Oct 08, 2014 10:52 am

Re: 11635 - Hotel booking

Post by Target979 » Thu Oct 09, 2014 11:09 pm

Random input, what a nifty feature!

Now I have something to work with, thanks a lot.

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 11635 - Hotel booking

Post by Repon kumar Roy » Tue Oct 28, 2014 7:39 pm

Code: Select all

Get AC
Last edited by Repon kumar Roy on Thu Oct 30, 2014 12:03 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11635 - Hotel booking

Post by brianfry713 » Wed Oct 29, 2014 10:29 pm

Try the random input at http://www.udebug.com/UVa/11635
Check input and AC output for thousands of problems on uDebug!

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 11635 - Hotel booking

Post by Repon kumar Roy » Wed Oct 29, 2014 11:37 pm

This input saved my day :evil:

Code: Select all

9 
3 1 3 4 
14
8 5 18 
4 8 122 
6 5 234 
7 7 404 
8 7 188 
3 6 596 
8 7 12 
6 6 26 
3 4 69 
4 8 400
 8 1 325 
5 9 381 
7 3 580 
5 4 400 
AC output : 1

Please check ....

Post Reply

Return to “Volume 116 (11600-11699)”