10278 - Fire Station

Moderator: Board moderators

Krzysztof Sikora
New poster
Posts: 11
Joined: Mon Sep 02, 2002 4:40 pm
Location: Poland
My program write the same output. But I'm given WA.
-- Krzysztof Sikora

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
arc16 wrote:output is

Code: Select all

``````1

1

1

2
``````
is it correct?
1

1

2

2

that's correct...

Krzysztof Sikora
New poster
Posts: 11
Joined: Mon Sep 02, 2002 4:40 pm
Location: Poland
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.
-- Krzysztof Sikora

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
okay, now could you tell me why the 3rd case output from Even is 2? i still don't understand it

hongping
New poster
Posts: 11
Joined: Fri Jul 26, 2002 5:43 pm
the test data:

Code: Select all

``````0 4
1 2 10
2 3 10
2 4 10
``````

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
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
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
New poster
Posts: 11
Joined: Fri Jul 26, 2002 5:43 pm

WA too

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
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
hello...arc16...

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

do you miss understand what the problem means?

or I miss understand your method...

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Re: WA too

hongping wrote: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
New poster
Posts: 11
Joined: Mon Sep 02, 2002 4:40 pm
Location: Poland
hongping wrote: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.
-- Krzysztof Sikora

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
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
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

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
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
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
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
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 ?