10278 - Fire Station

[Krzysztof Sikora]

My program write the same output. But I'm given WA.

[Even]

output is

Code: Select all

1

1

1

2

is it correct?

1

1

2

2

that's correct...

[Krzysztof Sikora]

OK. Output belongs to Even is correct.
At last I've got ACCEPTED.
My algorithm is almost good. It produced bad solutions for m = 0.
For this case you can find solution in time O(E) and overall O(ElogV).
In spite of that, my program has O(VElogV) complexity because there was less modification to create it.

[arc16]

okay, now could you tell me why the 3rd case output from Even is 2? i still don't understand it

[hongping]

the test data:

Code: Select all

0 4 
1 2 10 
2 3 10 
2 4 10 

answer is 2.

node 1 to node 2 is 10. and from node 2, you can go to 3 and 4, distance of 10 each.

2 is the "central" node, and if you place firestation there, all other nodes only have a distance of 10 from node 2.

if you place the station at 1, 1 to 3 (1->2->3) is 20, and 1 to 4 is 20 as well.

did i understand this correctly?

Krzysztof, I understand you algorithm with a starting set of all nodes with firestations before launching dijkstra. so what was the error that caused your program to be Not accepted previously?

thanks.
=)

[arc16]

so i have to find the intersection which have the most/average shortest path to another intersection? from the matrix, can i just sum the total distance of every intersection to other intersection and find the minimum?
for the previous test case, my floydd matrix is:

Code: Select all

0 10 20 20
10 0 10 10
20 10 0 20
20 10 20 0

sum of intersect #1 = 10+20+20 = 50
sum of intersect #2 = 10+10+10 = 30
sum of intersect #3 = 20+10+20 = 50
sum of intersect #4 = 20+10+20 = 50

so the answer is 2. Is it correct? If it is, why i'm still getting WA

(...almost give up...)

[hongping]

i think you are right... hmm... but i get WA too.

when there isnt any existing fire station, is it so that we should put the firestation at an intersection which has the
minimum (Maximum (shortest distance to ALL other nodes))

?

[Even]

hello...arc16...

according to your method...

sample input can form an floyd like

Code: Select all

0 1 2 3 2 1 += 9
1 0 1 2 3 2 += 9
2 1 0 1 2 3 += 9
3 2 1 0 1 2 += 9
2 3 2 1 0 1 += 9
1 3 3 2 1 0 += 9

your answer?? every intersection is the minimum...

do you miss understand what the problem means?

or I miss understand your method...

[Even]

i think you are right... hmm... but i get WA too.

when there isnt any existing fire station, is it so that we should put the firestation at an intersection which has the
minimum (Maximum (shortest distance to ALL other nodes))

?

we should "always" put the new firestation at an intersection which has no other firestation and can cause the min_max_distance...
not only when there isn't any existing firestation...
if no such firestation exist, output is "1".

[Krzysztof Sikora]

Krzysztof, I understand you algorithm with a starting set of all nodes with firestations before launching dijkstra. so what was the error that caused your program to be Not accepted previously?

Because if #fs = 0 then for all vertex dist. from firestation to it was infinity and '1' was written and it is not correct.

[arc16]

hi even,
first, thank you so much for your help
according to your hint, i change my algo to the following, please tell me where i go wrong...

Code: Select all

min = inf, nmin = -1
for all intersect i do
   for all intersect j do
       if no firestation in intersection j and distance[i,j]<min then
             nmin = j
             min = distance[i,j]
       end if
   end for
end for
if nmin=-1 then nmin=1

[Even]

Code: Select all

min = inf, nmin = -1
for all intersect i do
   for all intersect j do
       if no firestation in intersection j and distance[i,j]<min then
             nmin = j
             min = distance[i,j]
       end if
   end for
end for
if nmin=-1 then nmin=1

nonono...this problem want us to set a new firestation for minimum the maximun distance from any intersect to its nearest firestation...

that is... if there are three sites A, B, C, two roads AB 1, BC 2, and existing one firestation [] at C...
I express it as A -2- B -1- [C]

then the distance from each site to its nearest firestation is

A B C
3 1 0 ... and the maximum distance is 3

now, we wanna set a new firestation to minimize the maximun distance

if set at A
then the distance from each site to its nearest firestation become

A B C
0 1 0 ... and the maximum distance is 1

if set at B
then the distance from each site to its nearest firestation become

A B C
2 0 0 ... and the maximum distance is 2

we should set at A for the maximum distance is less than if we set at B

according to this example...

My method first find the minimum distance from any pair d[j]
and find ecah site its nearest distance to the nearest firestation min

second,

MIN_MAX ( the maximum distance before add a new firestation )
MIN_MAX_P = 1
for each site i which is not firestation {
for ecah site j which is not firestation
max = maximun( max, minimun( d[j], min ) )
if max < MIN_MAX then MIN_MAX = max, MIN_MAX_P = i ;
}

wish you understand it... Good Luck

[arc16]

thank you very much Even, and all who help me
i'm still not getting AC, but now i got TLE. I think it's much better than WA just need a little tweak here and there...
once again, thank you thank you thank you

[Julien Cornebise]

Hello

I'm having problems with this very problem.
I've got a Time Limit Exceed. After having tested around, I found that it was my floyd algorithm who was too long (no TLE because of infinte loop in input parsing, nothing of the kind).
I'm doing floyd on the whole graph (where the vertices are the intersections and the edges are the road)... Does anyone use the same, or should I use something else ?

Thanks by advance

[Julien Cornebise]

I'm still having problem... If anyone got it AC and read this message, any hint is really welcome