10472 - Fastest Vs Cheapest

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

Moderator: Board moderators

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

10472 - Fastest Vs Cheapest

Post by ditrix » Fri Mar 07, 2003 7:43 pm

Case#4:
-----------
from 0 to 1 there is only one way (on rickshaw) :
price = 23, time = 62.00
from 1 to 2 there are many ways:
1. by road "N":
1.1 rickshaw price = 5, time = 8.00
2. by road "M"
2.1 auto-rickshaw price = 20 time = 7.00
2.2 taxi-cab price = 20 time = 11.40
2.3 bus price = 2 time = 33.00

So the right solution is:
Fastest: price = 43, time = 69.00
Cheapest: price = 25, time = 95.00

But the sample output for this case is:

Case#4
25 68.00
25 68.00

Is my reasonement correct?
What do you think about?
@+!
DitriX

Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:

Post by Alexander Grushetsky » Fri Mar 07, 2003 8:26 pm

When you go from 0 to 2 on rickshaw, you don't let him go at 1. So you go all 12km with him, wait him and pay only once.

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan » Fri Mar 07, 2003 10:33 pm

Grushetsky is almost right. :wink:

When you're at 0, you wait for 2 minutes to get a rickshaw. You take it all the way (11 km) to reach 2.

Thus, the total time spent is 68 minutes (2 minutes for waiting + 66 minutes for travelling 11 km).

I took time to prepare the input/ouput/solution for this particular problem. So I'm quite sure that they are correct. However, it may be that the lengthy problem statement and the description of unfamiliar vehicles in this weird transport system is causing some confusion.

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

Post by ditrix » Sat Mar 08, 2003 4:28 am

Merci for explication. I have ajusted my program and it was accepted.
And about the problem statement, it's nice :)
@+!
DitriX

przygoda
New poster
Posts: 7
Joined: Fri Aug 09, 2002 12:26 pm
Location: Poland

Post by przygoda » Sun Mar 09, 2003 12:56 am

okey , I found the solution , but i think i have a small mistake in my code , it is possible for anybody to give me some interestin input-s with output-s .
Tnaks very much Martin :evil:
Please help me

Endrju
New poster
Posts: 4
Joined: Sat Mar 15, 2003 3:23 pm
Location: Poland

Post by Endrju » Sat Mar 15, 2003 3:36 pm

Can you give me a hint how to solve this problem? Is it Dijkstra alg. modification, or sth like that? :o

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan » Sat Mar 15, 2003 4:00 pm

The judge solution generates two separate graph: one for motorized vehicles, the other one for non-motorized vehicles. It then uses Floyd Warshall's all pair shortest path algorithm to get all the min distances. Then its a simple breadth first search, once to find the fastest path, then the cheapest path.

The problem-setter is dying to use dijkstra (instead of the bfs) to beat the better ranked times for this problem. :wink:

Any other innovative idea could also help. :P

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

Post by makbet » Sun Mar 16, 2003 3:46 pm

Are fractional fares possible in this problem? The table contains integer fares per 1 km, so does the point about fractional fares and paying extra have any meaning for the problem?

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

Post by ditrix » Sun Mar 16, 2003 3:57 pm

All costs are itegers in this problem. It means, that, for ex., if you get a bus for 1km you must pay a minimum fare of 2Tk.
On the contrary the travel time can be fractional.
@+!
DitriX

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

Post by makbet » Mon Mar 17, 2003 7:39 pm

I keep getting WA. Maybe you guys have got any tricky input that might help me in finding a bug?
thanks

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan » Mon Mar 17, 2003 7:46 pm

Just remembered one from Adrians pm.

To find the cheapest route, you may need to take one vehicle, travel some distance, get out of it and take the same type of vehicle again.

I found this out while testing an alternate judge solution. So far the problem statement is concerned, this case is perfectly alright. Thanks to Adrian for reminding me of it.

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

Post by makbet » Tue Mar 18, 2003 4:40 pm

I made that mistake, but it seems that it's not the only one, because I still have WA :roll:

Endrju
New poster
Posts: 4
Joined: Sat Mar 15, 2003 3:23 pm
Location: Poland

Post by Endrju » Sat Mar 29, 2003 1:41 pm

Big thx Tomal for your hint. My solution uses 2 Dijkstras after Floyd (one for fastest routes and one for cheapest). It's not as fast as yours but IT WORKS !! :D

User avatar
Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

Travel fare in fastest route

Post by Maxim » Sun May 04, 2003 4:47 pm

I've managed to calculate travel time in fastest route. What is the easiest way of finding value of travel fare in that route?

Maxim

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan » Sun May 04, 2003 5:12 pm

The easiest way to deal with it is to calculate both the time and the fare at the same time. As you'd see, the fare is not a function of the time alone. It depends on the distance of the roads and the mode of transport as well.

I simply used 2 parameters (instead of the time only) for the states of BFS. One parameter stored the time taken to come to the ith intersection, the other one stored the fare. I found the optimum (fastest or cheapest) solution based on these two parameters of a state.

Post Reply

Return to “Volume 104 (10400-10499)”