10841 - Lift Hopping in the Real World

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

[shahriar_manzoor]

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

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

[Zuberul]

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

[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

Code: Select all

OUTPUT:

1295
8505
100
137
0

Hope it helps...

[Zuberul]

Thanks.

my code gives the same output.
but still WA.

[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?

[Abednego]

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.

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

[Abednego]

Great! That's exactly the reasoning I was hoping for.