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

10278 - Fire Station

Post by Krzysztof Sikora » Mon Sep 02, 2002 4:48 pm

I solved this problem but I got WA.
I used Dijkstra and set all cities with fire station on 0, others on infinity.
Could you help me? Maybe a trick?
-- Krzysztof Sikora

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

Post by dwyak » Mon Sep 02, 2002 7:24 pm

I found no trick. I just use a simple Floyd.
Are you sure there's nothing wrong with your program.

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

Post by Krzysztof Sikora » Mon Sep 02, 2002 11:45 pm

I'm sure. Last year there was a contest in Poland. One of problem was the same meaning and I got ACCEPTED.
-- Krzysztof Sikora

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

Post by Even » Sun Sep 15, 2002 8:46 pm

Krzysztof Sikora wrote:I'm sure. Last year there was a contest in Poland. One of problem was the same meaning and I got ACCEPTED.
If the original input need no more fire station for minimize the max distance ... that is, if input like

2 2
1
2

what is your output ? :)

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

time limit exceeded

Post by hongping » Sun Sep 15, 2002 11:43 pm

hi i tried using dijkstra n^3 to find distances between all pairs. then iterate through all possible intersection for placement of the new firestation, and then recalculate the max distance, and then find the best.
but i get time limit exceeded. any way to speed up?

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

Post by Krzysztof Sikora » Sat Sep 21, 2002 11:00 am

2 2
1
2
my output is 1.
Last edited by Krzysztof Sikora on Sat Sep 21, 2002 3:21 pm, edited 1 time in total.
-- Krzysztof Sikora

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

Post by Krzysztof Sikora » Sat Sep 21, 2002 11:05 am

To Hongping.

You needn't iterate through all possible intersection.
Initially, you can put all firestations to heap and run Dijkstra.
Than find the intersection with the lowest distance.
Time Complexity O(E*logV).
Last edited by Krzysztof Sikora on Sat Sep 21, 2002 3:20 pm, edited 1 time in total.
-- Krzysztof Sikora

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

Post by hongping » Sat Sep 21, 2002 2:50 pm

Krzysztof,
thanks for the hint.
so i only need to do dijkstra for all the intersections with firestations.

what do you mean by " find the intersection with the lowest distance"?
how do i use this to find which position to place the new fire station?

thanks.

hongping

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

Post by Krzysztof Sikora » Sat Sep 21, 2002 3:33 pm

Sorry, no lowest but highest. Find max in array of dist.

Normally we use Dijksta with one vertex (source) and dist for this vertex is 0.
In this case we use Dijkstra with a set (set of firestations) and for all vertex from this set dist is 0.
Now you must launch Dijksta. After it

Code: Select all

max := -1;
for all vertex v do
  if dist[v] > max then max := dist[v];
writeln(v);
v is the furthest place from firestations.

I wish it worked, but I don't know why.
-- Krzysztof Sikora

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 » Tue Sep 24, 2002 2:23 am

hi guys,
i'm in the middle of testing my solution. could you tell me what is the output for the following input?

Code: Select all

2

3 6
2 
5 
4
1 2 20
2 3 10
3 4 15
4 5 20
5 6 10
6 1 10

4 6
2 
3 
4 
5
1 2 20
2 3 10
3 4 15
4 5 20
5 6 10
6 1 10
thank you :)

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

Post by Krzysztof Sikora » Tue Sep 24, 2002 9:58 am

Output:

Code: Select all

1

1
Warning. My program is not ACCEPTED.
-- Krzysztof Sikora

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 » Wed Sep 25, 2002 1:46 am

hmmm, same as mine... i still got WA too..
i have test the judge input using halt() (pascal), and it looks like there's an input when there's already one or more firestation in every intersection. So i think i have to find how to solve that case, but how :-?

some of my though:
1. put the firestation in the 1st intersection which have the _least_ firestation relative to the other. for example:

Code: Select all

6 4
1
1
2
2
3
4
1 2 10
2 3 10
3 4 10
4 1 10
i would output 3, since intersect #1 and #2 already have 2 firestations but #3 and #4 have 1.

2. if above doesn't work (all intersection have the same number of firestation), put the firestation on intersection which have the most connecting road. for example:

Code: Select all

4 4
1
2
3
4
1 2 1
1 3 1 
1 4 1
4 1 1
output is 2 (1 have 3 connecting roads, while others have only 1)

however, the judge still giving me WA :( anything that i miss? or my though above was wrong? please help....anyone :)

thanks

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

Post by Even » Wed Sep 25, 2002 9:25 am

arc16 wrote:hmmm, same as mine... i still got WA too..
i have test the judge input using halt() (pascal), and it looks like there's an input when there's already one or more firestation in every intersection. So i think i have to find how to solve that case, but how :-?

some of my though:
1. put the firestation in the 1st intersection which have the _least_ firestation relative to the other. for example:

Code: Select all

6 4
1
1
2
2
3
4
1 2 10
2 3 10
3 4 10
4 1 10
i would output 3, since intersect #1 and #2 already have 2 firestations but #3 and #4 have 1.

2. if above doesn't work (all intersection have the same number of firestation), put the firestation on intersection which have the most connecting road. for example:

Code: Select all

4 4
1
2
3
4
1 2 1
1 3 1 
1 4 1
4 1 1
output is 2 (1 have 3 connecting roads, while others have only 1)

however, the judge still giving me WA :( anything that i miss? or my though above was wrong? please help....anyone :)

thanks
both output should be 1 ( the minimun number )

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

How about this...

Post by Even » Wed Sep 25, 2002 9:28 am

4

3 3
1
2
3
1 2 10
2 3 10
3 1 10

0 5

0 4
1 2 10
2 3 10
2 4 10

1 2
1
1 2 5

try it...

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 » Wed Sep 25, 2002 10:25 am

output is

Code: Select all

1

1

1

2
is it correct?

Post Reply

Return to “Volume 102 (10200-10299)”