Page 1 of 1
10841 - Lift Hopping in the Real World
Posted: Fri May 13, 2005 10:32 am
by little joey
"I think problem descriptions should withstand the
reality check, otherwise they are misleading."
little joey
Great problem. May my critisism inspire you to write many more problems, Igor
Why are you considering retirement, BTW? Please don't...
OK, one minor point of critique. In your discussion of the first sample you write:
In the first example, the worst case is when elevator 1 is on floor 99 and will take 990 seconds to reach floor 0. You will then take it to floor 13 in 130 seconds, spend 5 second exiting and calling elevator 2, which is on floor 30. It will take 170 seconds to reach you and 170 seconds to take you to floor 30. The total is 1295 seconds.
But the second elevator takes 5 seconds per floor, so it takes 85 seconds to go from floor 30 to floor 13, and 85 seconds to go back again. The numbers then add up to 1295.
hmm
Posted: Fri May 13, 2005 3:18 pm
by shahriar_manzoor
I guess by retiring, he means retiring from ACM Contests but not from problemsetting and TC. But that is only a guess...
Posted: Sun May 15, 2005 9:27 pm
by Abednego
Thanks, little joey. Of course, I made a mistake again, as you have pointed out. :-( I hope it does not confuse too many people.
Shahriar is right. I'm only retired from the ACM, not from problem solving (just check the number of blue/green/red numbers in my profile ;-)). In fact, I'm almost ready with the second Graph Lovers' Contest. There is just one problem that I really want to add. Stay tuned...
Posted: Sun Jun 12, 2005 11:08 pm
by Zuberul
I got wrong answer.
Can someone give me some I/O.
Posted: Mon Jun 27, 2005 2:03 pm
by tRipper
Can someone give me some I/O.
Here's mine test data:
Code: Select all
INPUT:
2 30
10 5
0 1 3 5 7 9 11 13 15 20 99
4 13 15 19 20 25 30
3 50
10 50 100
0 10 30 40
0 20 30
0 20 50
5 1
1 2 3 4 50
0 2 6
2 3 5
3 8
1 8 20
0 1
5 1
1 2 3 4 100
0 2 6
2 3 5
3 8
1 8 20
0 1
5 0
1 2 3 4 50
0 2 6
2 3 5
3 8
1 8 20
0 1
Hope it helps...
Posted: Tue Jun 28, 2005 10:26 pm
by Zuberul
Thanks.
my code gives the same output.
but still WA.
Re: 10841 - Lift Hopping in the Real World
Posted: Tue May 27, 2008 9:38 pm
by andmej
If I use certain elevator and in the future I need to use it again, should I suppose it stays in the last floor it stopped? Or does it move to the furthest location again?
Re: 10841 - Lift Hopping in the Real World
Posted: Tue May 27, 2008 10:14 pm
by Abednego
andmej wrote:If I use certain elevator and in the future I need to use it again, should I suppose it stays in the last floor it stopped? Or does it move to the furthest location again?
Officially speaking, "No response. Please read the problem statement."
Unofficially, have a look at sample input #2 and think about it for a few seconds.
Re: 10841 - Lift Hopping in the Real World
Posted: Tue May 27, 2008 10:42 pm
by andmej
I still don't know what should happen with an elevator you just left, but I think that in the optimal solution you should never use an elevator twice.
Here's why:
If you want to use an elevator twice, it means you stopped in some floor f to switch. You then move to another floor g without using the first elevator and want to pick it up again at floor g. The elevator still has to go from floor f to g, which also takes time. If, instead, I had chosen to keep going in the first elevator until floor g, I wouldn't have added the extra time needed for the swap.
Am I right? If yes, then I think it doesn't matter if the elevator stays where I left it or moves to the furthest location, in any case Dijkstra's algorithm would still find a path that doesn't use an elevator twice.
Re: 10841 - Lift Hopping in the Real World
Posted: Tue May 27, 2008 10:55 pm
by Abednego
Great! That's exactly the reasoning I was hoping for.