10278 - Fire Station

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Krzysztof Sikora
New poster
Posts: 11
Joined: Mon Sep 02, 2002 4:40 pm
Location: Poland

Post by Krzysztof Sikora » Wed Sep 25, 2002 11:39 am

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

Post by Even » Wed Sep 25, 2002 12:58 pm

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

Post by Krzysztof Sikora » Wed Sep 25, 2002 2:38 pm

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

Post by arc16 » Wed Sep 25, 2002 6:15 pm

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

Post by hongping » Wed Sep 25, 2002 9:20 pm

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
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 » Thu Sep 26, 2002 2:14 am

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

(...almost give up...)

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

WA too

Post by hongping » Thu Sep 26, 2002 2:38 am

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

Post by Even » Thu Sep 26, 2002 8:06 am

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

Re: WA too

Post by Even » Thu Sep 26, 2002 8:17 am

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

Post by Krzysztof Sikora » Thu Sep 26, 2002 11:40 am

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

Post by arc16 » Thu Sep 26, 2002 11:42 am

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

Post by Even » Thu Sep 26, 2002 2:44 pm

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

Post by arc16 » Thu Sep 26, 2002 5:00 pm

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

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Sun Aug 24, 2003 12:52 am

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
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Mon Sep 01, 2003 12:02 am

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

Post Reply

Return to “Volume 102 (10200-10299)”