## 10457 - Magic Car

Moderator: Board moderators

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

### 10457 - Magic Car

Hi!

I tried to solve the problem by a binary search of O(M^2lgM) ..
I thought it would just fit in the time limit but I'm receiving TLEs.

Could anyone, who got Accepted, help me, with giving some hints?

mathijs
New poster
Posts: 7
Joined: Tue Mar 04, 2003 5:15 pm
Location: Groningen, The Netherlands
Contact:
I handled it as a complicated shortest-path problem, but the data stored at each vertex is not just one length, but a list of possible (minspeed, maxspeed, energyused) records.
I iteratively relaxed edges just like in Bellman Ford, and compared records in the same vertex list with eachother to determine if one is better then another one to keep the lists small (for instance, when the minspeed & maxspeed are the same, but the energyused of one of the records is lower than the other one).

That got me accepted. I'm curious about other approaches (I have seen some quicker solutions in the ranklist...)

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
You can observe that energyused = maxspeed - minspeed+constant-energy (I add it only before printing it). So you can compare if you have same maxspeed or if you have same minspeed. In both cases take the element with smaller value for energyused.

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris
I tryed in the same way - Bellman-Ford with energy = max_speed - min_speed + const, but i have a WA. I think, something is not correct with the judge.
@+!
DitriX

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
My solution is M^2*lg(M), and it's one of the fastest. I used the following approach:

Create a list of all unique speed limits
Loop over all minimum speed limits
For each minimum speed, perform a binary search on the maximum speed limit
Do a DFS in the graph, only traversing the edges with speed between minimum and maximum

Other optimziation include that instead of looping over all minimum speeds, I start with a binary search here to, to find the lowest possible minimum speed. doesn't alter complexity in worst case, but should improve average case quite a lot

I think this problem was very nice, one of the better at UVA.

Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:
Problem is good but I come with my solution enough quickly and for now it is on the first place (I think not for long).

At first I wrote 2 similar functions. The first ignores roads with speed lower than X and searches minimal speed Y so you can go from the start to the end by roads in [X,Y] (f1(x)=y). And the second ignores roads with speed bigger than Y and searches maximal speed X so you can go from the start to the end by roads in [X,Y] (f2(y)=x). I used modificated Dijkstra.

Then I do the next procedure:
b1=f1(0);
a1=f2(b1);
b2=f1(a1+1);
a2=f2(b2);
b3=f1(a2+1);
a3=f2(b3);
....
and so on while functions find pathes.
The best speed range is from [a1,b1],[a2,b2],[a3,b3],...

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
Yarin:

Yes, I think that's the exact method I used.
1. I collected differences of all edge speeds in S, and sorted them in order.
2. Do a binary search on S as the following:
2-1. For "used energy" S_i, iterate through all edges, assuming the edge will be the minimum-cost edge.
2-1-1. For the edge, binary search (edge_cost + S_i) from the edge list.
2-2. If there is one, do DFS only with edges between (edge_cost) and (edge_cost + S_i) .. see it's possible to reach the destination within the limit..

I think that's it. But I'm still receiving TLEs (I recoded the whole program to verify that it's not the matter with the code) .. I don't see any differences between mine and your algorithm. (Maybe I understanded your algorithm incorrectly..) Are there any differences?

Alexander:
Wow Good approach I've never thought of ..
BTW, do you mean a1+1 by the next-larger edge speed, or simply 6+1 = 7?

If it is the later one, doesn't your algorithm run slower when the edge speeds vary a lot? like 0 to 200000000 or something.. or the edges have real value speeds.

And if it's the first one, isn't your algorithm's time complexity O(VE^2)? How could that be that fast, I wonder.. @_@

Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:
BTW, do you mean a1+1 by the next-larger edge speed, or simply 6+1 = 7?
For real numbers it will be the next speed, but for integers you can use a1+1 as threshold for speed ignoring. Or f1 can be modificated so it ignores speeds that are lower or equal to a1.

There are at most E steps (usually much less), because after each step at least one road more is ignored. And for each step I use Dijkstra with complexity E*logV. So formally, the complexity of algorithm is E^2*logV.

I did not optimize my program, but I know how greatly speed up it. However, I have no time for it.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
Alexander: Oh, I've never thought of implementing Dijkstra with Fibonacci heaps. =) That's cool ~

Anyway: today I found an algorithm with O(E^2lgV) and got an AC.
Thanks for your sincere replies! It's one of the most interesting problems I solved these days.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
I try to solve this problem,but get wrong answer
could someone tell me the output for the input?Thx
9 14
1 2 5
2 3 10
5 6 14
5 4 20
1 6 8
2 5 6
3 4 13
6 7 8
5 8 11
4 9 3
9 8 6
7 8 4
7 9 33
9 7 14
20 30
8
1 2
5 8
3 7
8 2
9 6
1 9
4 7
2 7

sqrt3lj
New poster
Posts: 2
Joined: Fri Apr 18, 2003 8:37 am
Is the output like this?
50
50
55
54
54
54
53
53

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

### Alexander's solution

Alexander,

how would your solution do with this problem :

4 4
1 2 1
2 3 5
1 4 75
4 3 76
5 5
1
1 3

By what I understood from your algorithm, it'll choose first the lowest maximum speed he can use to have a path from 1 to 3 with vmin = 1. So it will find 5. Then you will try to get the maximum minimum speed with Y=5, that yields => 1.

so the answer would be [1,5] -> 5+5+4 = 14 .

but, if the algorithm chose the 75 way, it would do better.

Is that what you do ? Did I get that well ?
[]s
Mauricio Oliveira Carneiro

Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:
You did only the first step.
For the next step you should search the lowest maximum speed you can use (ignoring pathes with speed <=5). It will be 76. Then the maximum minimum speed (ignoring pathes with speed >76) will be 75. Calculate the answer for [75,76] (it is better than for [1,5]) and update the result. You cannot find path from 1 to 3 ignoring pathes with speed <=76 so algorighm stops. Otherwise, you should check another speed intervals and choose the best.

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
Alexander Grushetsky wrote:You did only the first step.
For the next step you should search the lowest maximum speed you can use (ignoring pathes with speed <=5). It will be 76. Then the maximum minimum speed (ignoring pathes with speed >76) will be 75. Calculate the answer for [75,76] (it is better than for [1,5]) and update the result. You cannot find path from 1 to 3 ignoring pathes with speed <=76 so algorighm stops. Otherwise, you should check another speed intervals and choose the best.
Now let me see if I get it ... IF I understood you, I found a counter for the algo. If you can, please tell me why it's not I'm still curious...

5 6
1 2 1
2 3 4
1 4 3
4 3 5
1 5 7
5 3 4
10 10
1
1 3

by your algorithm , the steps would be :

f1(1) = 4
f2(4) = 1
f1(4) = 7
f2(7) = 4
f1(7) -> no path. stops.

best difference : 3 (which is wrong because we got a difference of 2 if we go through 1->4->3)

Does your algorithm solves that ? how ?

[]s
Mauricio Oliveira Carneiro

Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:
Oh, I wrote incorrectly in my last post, but my first post is correct. You should read as "ignoring <=1" instead of "ignoring <=5" and "ignoring <=75" instead of "ignoring <=76".