10841 - Lift Hopping in the Real World

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

Moderator: Board moderators

Post Reply
User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

10841 - Lift Hopping in the Real World

Post by little joey » Fri May 13, 2005 10:32 am

"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.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Fri May 13, 2005 3:18 pm

I guess by retiring, he means retiring from ACM Contests but not from problemsetting and TC. But that is only a guess...

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun May 15, 2005 9:27 pm

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...
If only I had as much free time as I did in college...

Zuberul
New poster
Posts: 28
Joined: Sun Oct 24, 2004 9:46 pm
Location: dhaka
Contact:

Post by Zuberul » Sun Jun 12, 2005 11:08 pm

I got wrong answer.
Can someone give me some I/O.

tRipper
New poster
Posts: 22
Joined: Sun Mar 13, 2005 5:04 pm
Location: out there

Post by tRipper » Mon Jun 27, 2005 2:03 pm

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

Code: Select all

OUTPUT:

1295
8505
100
137
0
Hope it helps...
If I am out of my mind, it's all right with me.

Zuberul
New poster
Posts: 28
Joined: Sun Oct 24, 2004 9:46 pm
Location: dhaka
Contact:

Post by Zuberul » Tue Jun 28, 2005 10:26 pm

Thanks.

my code gives the same output.
but still WA.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 10841 - Lift Hopping in the Real World

Post by andmej » Tue May 27, 2008 9:38 pm

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?
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Re: 10841 - Lift Hopping in the Real World

Post by Abednego » Tue May 27, 2008 10:14 pm

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.
If only I had as much free time as I did in college...

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 10841 - Lift Hopping in the Real World

Post by andmej » Tue May 27, 2008 10:42 pm

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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Re: 10841 - Lift Hopping in the Real World

Post by Abednego » Tue May 27, 2008 10:55 pm

Great! That's exactly the reasoning I was hoping for.
If only I had as much free time as I did in college...

Post Reply

Return to “Volume 108 (10800-10899)”