10457  Magic Car
Moderator: Board moderators

 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?
Thanks in advance !!!
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
 New poster
 Posts: 7
 Joined: Tue Mar 04, 2003 5:15 pm
 Location: Groningen, The Netherlands
 Contact:
I handled it as a complicated shortestpath 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...)
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
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.
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.

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

 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:
21. For "used energy" S_i, iterate through all edges, assuming the edge will be the minimumcost edge.
211. For the edge, binary search (edge_cost + S_i) from the edge list.
22. 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 nextlarger 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.. @_@
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:
21. For "used energy" S_i, iterate through all edges, assuming the edge will be the minimumcost edge.
211. For the edge, binary search (edge_cost + S_i) from the edge list.
22. 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 nextlarger 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.. @_@

 New poster
 Posts: 28
 Joined: Wed Jul 31, 2002 10:33 am
 Location: Ukraine
 Contact:
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.BTW, do you mean a1+1 by the nextlarger edge speed, or simply 6+1 = 7?
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.

 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 ?
please reply me ... i'm god damn curious about it.
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.
[]s
Mauricio Oliveira Carneiro
Mauricio Oliveira Carneiro

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

 Learning poster
 Posts: 54
 Joined: Sun May 18, 2003 1:19 am
 Location: Rio de Janeiro, Brazil
 Contact:
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...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.
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.
[]s
Mauricio Oliveira Carneiro
Mauricio Oliveira Carneiro

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