10457 - Magic Car

[Whinii F.]

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?

Thanks in advance !!!

[mathijs]

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

[Adrian Kuegel]

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]

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.

[Yarin]

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]

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

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]

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

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]

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]

Is the output like this?
50
50
55
54
54
54
53
53

[carneiro]

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 ?
please reply me ... i'm god damn curious about it.

[Alexander Grushetsky]

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]

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 ?

sorry to bother you with those questions Alexander, it's just that I am really curious about this approach you made.

[Alexander Grushetsky]

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

So, in your last example:
f1(0) = 4
f2(4) = 1
f1(1) = 5
f2(5) = 3
f1(3) = 7
f2(7) = 4
The best difference is 2.

(f1(x) - ignores pathes with speed <=x and searches minimum, f2 - ignores pathes with speed >x and searches maximum)