Page 1 of 4
10801 - Lift Hopping
Posted: Tue Jan 18, 2005 5:14 pm
I used modified floyd-warshall & managed a wrong ans.
please give me some I/O.
Re: Need I/O-10801
Posted: Wed Jan 19, 2005 5:38 pm
Zuberul wrote:I used modified floyd-warshall & managed a wrong ans.
please give me some I/O.
Code: Select all
100 100 1
0 2 4 5 6 7 8 21 22 23 24 25 26 30
1 2 19 11 12 13 14 15 16 30
1 10 30
Posted: Fri Jan 21, 2005 6:04 pm
hmm changed a bit & got the correct ans .
but this time got TLE.
what is the faster method to solve it.
can you explain please.
thanks for the help.
Posted: Fri Jan 21, 2005 9:51 pm
Research Dijkstra's shortest path algorithm. The Big White book (Cormen, et al. "Introduction to Algorithms") is a good reference.
Posted: Mon Jan 24, 2005 1:11 pm
What should be the output of this input?
9900? or 417?
Posted: Mon Jan 24, 2005 1:16 pm
Posted: Mon Jan 24, 2005 1:20 pm
Oh.. that doesn't make sense
No wonder why shortest path works for this problem.
Posted: Mon Jan 24, 2005 2:33 pm
But this is a regular shortest path problem. What would you expect?
Posted: Mon Jan 24, 2005 3:12 pm
The issue Cho was pointing to: Consider the test case he posted. The optimal solution is: take lift 1 from 0 to 1, take lift 2 from 1 to 98, take lift 1 from... oh, wait! Isn't the slow lift 1 somewhere around floor 2 now? How is it possible that suddenly it is here and I can take it again (to get to the floor 99)?
I think a way around this problem is to assume that if a lift is empty, it may move faster than if it is transporting a person. Then the assumption about waiting 60 seconds may make sense.
Posted: Mon Jan 24, 2005 3:14 pm
I fully agree with cho on this matter. I think problem descriptions should withstand the reality check, otherwise they are misleading.
In cho's case:
1. take elevator 1 to floor 1, which takes 100 seconds
2. wait 60 seconds for elevator 2
3. take elevator 2 to floor 98, which takes 97 seconds
4. wait 60 seconds for elevator 1
5. tale elevator 1 to floor 99, which takes 100 seconds
The total trip takes 100+60+97+60+100 = 417 seconds.
But between step 2. and step 4. elevator 1 has 60+60+97 = 217 seconds to get from floor 1 to floor 98 at a speed of 100 seconds per floor. This is absurd. Or does it magically teleports from one floor to another if nobody is in it? Why wait 60 seconds then?
Posted: Mon Jan 24, 2005 3:21 pm
I don't agree. The problem statement says:
(for simplicity) the operation of switching an elevator on some floor always takes exactly a minute.
This information is enough. If it always
takes a minute, we shouldn't worry about slow elevators at all.
Posted: Mon Jan 24, 2005 3:38 pm
Sure, the problem description is complete in the sense that it contains enough information to solve the problem. My point is, however, that it pretends to describe a real life situation, but misses the reality check by several orders of magnitude.
Of course, to make a problem out of a real life situation, one has to make simplifications, assumptions and idealisations, but in my opinion they should only have a minor effect on the outcome of the problem. This is simply stretching it too far and therefore misleading.
But maybe I'm being too philosophical about it.
Posted: Mon Jan 24, 2005 7:27 pm
Cho and little joey, you're absolutely right. I could say that elevators use "subspace teleporting" to move between floors, but that procedure is dangerous to humans and it always takes exactly 60 seconds.
This is a poor defence though. Next time, I will do this problem the correct way. Stay tuned for "Lift Hopping 2.0"...
Posted: Thu Jan 27, 2005 8:29 am
Hello, I thought it's a simple shortest path problem.
I used Dijksta's algorithm to solve and passed all the IO above.
But still get WA.
Could someone offer more input/output? THx
Posted: Sun Jan 30, 2005 2:28 pm
Could somebody tell me how to read input in this task - I don't know how make my program stop reading list of floors that I am able to achieve using current elevator.. In C or C++