10457 - Magic Car

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

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

10457 - Magic Car

Post by Whinii F. » Wed Mar 05, 2003 12:51 pm

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

User avatar
mathijs
New poster
Posts: 7
Joined: Tue Mar 04, 2003 5:15 pm
Location: Groningen, The Netherlands
Contact:

Post by mathijs » Wed Mar 05, 2003 3:35 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Mar 05, 2003 7:53 pm

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

Post by ditrix » Thu Mar 06, 2003 1:11 am

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:

Post by Yarin » Thu Mar 06, 2003 9:54 pm

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:

Post by Alexander Grushetsky » Thu Mar 06, 2003 11:25 pm

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:

Post by Whinii F. » Sat Mar 08, 2003 8:22 am

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 :D 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:

Post by Alexander Grushetsky » Sat Mar 08, 2003 7:26 pm

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:

Post by Whinii F. » Mon Mar 10, 2003 9:18 am

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! :D 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

Post by windows2k » Sat Apr 05, 2003 3:34 pm

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

Post by sqrt3lj » Sat Apr 26, 2003 3:59 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

Post by carneiro » Sun May 18, 2003 1:26 am

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.
[]s
Mauricio Oliveira Carneiro

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

Post by Alexander Grushetsky » Sun May 18, 2003 9:17 am

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:

Post by carneiro » Mon May 19, 2003 8:26 am

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 ?

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

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

Post by Alexander Grushetsky » Mon May 19, 2003 6:58 pm

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)

Post Reply

Return to “Volume 104 (10400-10499)”