10801 - Lift Hopping

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

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

10801 - Lift Hopping

Post by Zuberul » Tue Jan 18, 2005 5:14 pm

I used modified floyd-warshall & managed a wrong ans.
please give me some I/O.

User avatar
lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

Re: Need I/O-10801

Post by lord_burgos » Wed Jan 19, 2005 5:38 pm

Zuberul wrote:I used modified floyd-warshall & managed a wrong ans.
please give me some I/O.
Input

Code: Select all

3 30
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
Output

Code: Select all

449

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

Post by Zuberul » 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.

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

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Mon Jan 24, 2005 1:11 pm

What should be the output of this input?

Code: Select all

2 99
100 1
0 1 98 99
1 98
9900? or 417?

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Jan 24, 2005 1:16 pm

417.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Mon Jan 24, 2005 1:20 pm

Oh.. that doesn't make sense :evil:
No wonder why shortest path works for this problem.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Jan 24, 2005 2:33 pm

But this is a regular shortest path problem. What would you expect?

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » 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.

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

Post by little joey » 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?

Complete rubbish...

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » 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.

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

Post by little joey » 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.

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

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » 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 :D

sqm
New poster
Posts: 3
Joined: Sun Jan 30, 2005 2:18 pm
Location: Bialystok, POLAND

Post by sqm » 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++

Post Reply

Return to “Volume 108 (10800-10899)”