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

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 10278 - Fire Station

Post by stcheung »

Here's 1 more tricky test case, where the correct output is 1 even though there's already a fire station there. So don't immediately reject any intersection that already has a fire station. Be careful on TLE though, because after making this change my code went from 1sec to 6sec.

1
1 2
1
1 2 0

ymgve
New poster
Posts: 7
Joined: Mon Oct 15, 2007 1:17 am

Re: 10278 - Fire Station

Post by ymgve »

stcheung wrote:Here's 1 more tricky test case, where the correct output is 1 even though there's already a fire station there. So don't immediately reject any intersection that already has a fire station. Be careful on TLE though, because after making this change my code went from 1sec to 6sec.

1
1 2
1
1 2 0
Isn't that wrong? The answer should be 2, since that location doesn't have any station already.

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 10278 - Fire Station

Post by mak(cse_DU) »

Actually the tricky part is below.
input:

Code: Select all

1
2 2
1
2
1 2 10
output will be:

Code: Select all

1
No intersection without fire station. so Answer is 1.
Mak
Help me PLZ!!

Stargazer71
New poster
Posts: 1
Joined: Fri Dec 17, 2010 6:16 am

Re: 10278 - Fire Station

Post by Stargazer71 »

I got snagged by some tricky inputs, so I'll give a sample output from my ACC program.

Most of these inputs have already been posted, but this combination was:

- Brutal on my program, and
- Easy to verify at a glance

Input:

Code: Select all

8

2 2
1
2
1 2 10

0 4
1 2 10
2 3 10
2 4 10

2 7
1
4
1 2 5
1 4 30
1 3 20
2 4 45
2 5 25
3 4 15
3 6 35
5 7 10
6 7 40

1 7
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
7 1 10 

1 6
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10

1 8
3
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1

1 9
3
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1

1 8
1
1 2 1
2 3 2
3 4 2
3 5 2
3 6 2
3 7 2
3 8 15
The correct output is:

Code: Select all

1

2

3

4

5

6

7

8
Hope this helps someone, and best of luck!

Chocolate
New poster
Posts: 3
Joined: Sat Jun 11, 2011 3:17 pm

Problem in reading input

Post by Chocolate »

Hi, im new to UVa and finds that sometimes input-output here quite non-trivial.

I just want to work on this problem http://uva.onlinejudge.org/index.php?op ... oblem=1219

but I can't code to detect the blank lines between each testcase. I also found that this kind of input format is common for UVa problems (reading input until some blank lines).

I have tried using getline but still not working.

Anyone can help me with C++ code for reading input like the problem above ? (http://uva.onlinejudge.org/index.php?op ... oblem=1219)
Thanks before

zslwyuan
New poster
Posts: 4
Joined: Sun Nov 28, 2010 10:04 am

I Ac All the Samples that you gave, But WA,WHY!!HELP!!!

Post by zslwyuan »

#include<cstdio>
#include<cstring>
using namespace std;
int map[501][501],zj[501],yl[102],now[501];
bool used[501];
int main()
{
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
int i,j,k,l,n,m,t,o=0;scanf("%d\n",&t);
while (t--)
{
if (o)printf("\n");o=1;
scanf("%d %d",&m,&n);
memset(used,0,sizeof(used));
memset(map,60,sizeof(map));
for (i=1;i<=m;i++){scanf("%d\n",&yl);used[yl]=1;}
char s[300];
gets(s);
while (gets(s) != NULL && s[0] != '\0')
{
int x,y,z;
sscanf(s, "%d%d%d", &x, &y, &z);
map[x][y] = map[y][x] = z;
}
for (i=1;i<=n;i++)map=0;
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
{
if (k==i)continue;
for (j=1;j<=n;j++)
if (j!=i&&j!=k&&map[k]+map[k][j]<map[j])
map[j]=map[k]+map[k][j];
}
memset(zj,50,sizeof(zj));
int gd=100000000,gdn=1;
for (k=1;k<=n;k++)
if (!used[k])
{
int big=-1,bn;yl[m+1]=k;
memset(zj,60,sizeof(zj));
for (i=1;i<=n;i++)
for (j=1;j<=m+1;j++)
if (zj>map[yl[j]])
zj[i]=map[i][yl[j]];
for (i=1;i<=n;i++)
if (big<zj[i]){big=zj[i];}
if (big<gd){gd=big;gdn=k;}
}
printf("%d\n",gdn);
}
return 0;
}

djsohrab2007
New poster
Posts: 2
Joined: Mon Apr 30, 2012 12:50 am

Re: 10278 - Fire Station

Post by djsohrab2007 »

Stargazer71 wrote:I got snagged by some tricky inputs, so I'll give a sample output from my ACC program.

Most of these inputs have already been posted, but this combination was:

- Brutal on my program, and
- Easy to verify at a glance

Input:

Code: Select all

8

2 2
1
2
1 2 10

0 4
1 2 10
2 3 10
2 4 10

2 7
1
4
1 2 5
1 4 30
1 3 20
2 4 45
2 5 25
3 4 15
3 6 35
5 7 10
6 7 40

1 7
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
7 1 10 

1 6
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10

1 8
3
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1

1 9
3
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1

1 8
1
1 2 1
2 3 2
3 4 2
3 5 2
3 6 2
3 7 2
3 8 15
The correct output is:

Code: Select all

1

2

3

4

5

6

7

8
Hope this helps someone, and best of luck!

why output of this input is 4, I think it must be 5 ?

Code: Select all

1

1 7
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
7 1 10
Because question is minimize the maximum distance from any intersection to its nearest fire station.
distance of Intersection 4 to Fire station 2 is 20, But distance of Intersection 5 to that Fire Station is 30.
Please help me,
I Can't get AC.

I write this Code :

Code: Select all

#include<iostream>
#include<string>
#include <sstream>
#define MAXINT 2147483647
#define size  502
using namespace std;

int floyd( int Graph[][size] , int I ,int f)
{
	int IndexMax = 1 ;
	if( f!= 0 )
	{
		int through_k;
		for( int k = 1 ; k <= I+1 ; k++ )
		{
			for(int i =1 ; i < I + 2 ; i++ )
			{
				for( int j =1 ; j < I + 2 ; j++ )
				{
					if(Graph[i][k] == MAXINT||Graph[k][j] ==MAXINT)
						through_k = MAXINT; 
					else
						through_k = Graph[i][k]+Graph[k][j];
					if(through_k < Graph[i][j])
						Graph[i][j]=through_k;
				}
			}
		}

		int MaxD = Graph[1][I+1];
		for( int i = 2 ; i < I + 1 ; i++ )
		{
			if ( MaxD < Graph[i][I+1] )
			{
				MaxD = Graph[i][I+1];
				IndexMax = i ;
			}
		}
		return IndexMax;
	}
	else
	{
		int MaxD = 0;
		for( int i = 1 ; i < I + 1 ; i++ )
		{
			int val = 0 ;
			for( int j = 1 ; j < I+1 ; j++ )
			{
				if( i == j )
					continue;
				val+=Graph[i][j];
			}
			if ( MaxD < val )
			{
				MaxD = val;
				IndexMax = i ;
			}
		}
		return IndexMax;
	}
}
int main()
{
	int NumberOfTestCase;
	cin>>NumberOfTestCase;
	for(int number = 0 ; number < NumberOfTestCase ; number++)
	{
		int Graph[ size ] [ size ];
		int F , I ;
		cin >> F >> I ;

		for( int i = 0 ; i < I + 2 ; i++ )
			for( int j = 0 ; j < I + 2 ; j++ )
				Graph[i][j]=MAXINT;

	
		for( int i = 0 ; i < F ; i++ )
		{
			int FirStation ;
			cin>>FirStation;
			Graph[I+1][FirStation] = 0;
			Graph[FirStation][I+1] = 0;
		}

		string Input ;
		cin.ignore(10, '\n' );
		getline(cin,Input,'\n');
	
		while( !Input.empty())
		{
			istringstream iss(Input);
			int v1 , v2 , Edge;
			iss>>v1;
			iss>>v2;
			iss>>Edge;
			Graph[v1][v2] = Edge;
			Graph[v2][v1] = Edge;
			getline(cin,Input,'\n');
		}

		cout<<floyd(Graph , I , F ) <<endl ;
	}
	return 0 ;
}
Thank you,

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10278 - Fire Station

Post by brianfry713 »

For this input, there is already a fire station at 2:

Code: Select all

1

1 7
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
7 1 10
If you put the new fire station at 4, the distance from each intersection to the nearest fire station is:
1: 10
2: 0
3: 10
4: 0
5: 10
6: 20
7: 20

If you put the new fire station at 5, the distance from each intersection to the nearest fire station is:
1: 10
2: 0
3: 10
4: 10
5: 0
6: 10
7: 20

I think you misunderstood the question. You are to find the intersection to put the new fire station to minimize the maximum distance from any intersection to the nearest fire station. If you put the new fire station at intersection 4 or 5 the max distance is 20 so in that case you pick the lowest intersection number.
Check input and AC output for thousands of problems on uDebug!

djsohrab2007
New poster
Posts: 2
Joined: Mon Apr 30, 2012 12:50 am

Re: 10278 - Fire Station

Post by djsohrab2007 »

Thank you,
I write this code for minimize maximum dis. but I got Run-time error,
I don't know why,
I compiled this code , every thing was Okay.

Code: Select all

#include<iostream>
#include<sstream>
#include<vector>
#define INF 2147483647
#define SIZE  502

using namespace std;
template <class T> 
class PriorityQueue
{
private:
	vector<int> Key;
	vector<T> element;
	vector<int>::iterator it;

	
	void insert(const T &value,const int &key ,const int l ,const int h)
	{
		if( h<=l )
		{
			if(Key.at(l)>= key )
			{
				it = element.begin();
				//it++;
				element.insert(it+l,value);

				it = Key.begin();
				//it++;
				Key.insert(it+l,key);
			}
			else
			{
				it = element.begin();
				it++;
				element.insert(it+l,value);

				it = Key.begin();
				it++;
				Key.insert(it+l,key);
			}
		}
		else
		{
			int mid = ( l + h ) / 2 ;

			if ( Key.at( mid ) == key )	// maybe queue have two element with same Priority 
			{
				it = element.begin();
				//it++;
				element.insert(it+mid,value);

				it = Key.begin();
				//it++;
				Key.insert(it+mid,key);
			} 
		    else if( Key.at( mid ) > key )
			{
				insert(value,key,l,mid-1 );
			}
			else if	( Key.at( mid ) < key )
			{
				insert(value,key,mid+1,h );
				
			}
			
		}
		
	}
public:
	PriorityQueue(const PriorityQueue& Copy)
	{
		Key = Copy.Key;
		element = Copy.element;
		
	}
	PriorityQueue operator=(const PriorityQueue& Copy)
	{
		Key = Copy.Key;
		element = Copy.element;
		return *this;
	}
	PriorityQueue()
	{
	}
	bool empty()
	{
		return element.empty();
	}
	int size()
	{
		return element.size();
	}
	void push(const T& value ,const int& key)
	{
		if(element.empty())
		{
			element.push_back(value);
			Key.push_back(key);
		}
		else
		{
			int s= element.size()-1;
			insert(value,key,0,s);
		}
	}
	T popLowestPriority()
	{
		
		T temp = element.at(0);

		it = element.begin();
		element.erase(it);

		it = Key.begin();
		Key.erase(it);

		return temp ;
	}
	T popHighestPriority()
	{
		
		T temp = element.back();
		element.pop_back();

		Key.pop_back();

		return temp ;
	}
	void changePriority(T value  , int newKey)
	{
		it = element.begin();
		int elementSize = element.size();
		for( int i = 0 ; i < elementSize ; i++ )
		{
			if( element.at( i ) == value )
			{
				element.erase( it+i);

				it = Key.begin();
				Key.erase(it+i);

				this->push(value,newKey);
			}
		}
	}
};	
class graph
{
	
private:
	vector<int> GraphAdj[ 3 ];
	vector<int> Locate;
	int Order;

	
public:
	graph( const graph& Copy )
	{
		for( int i = 0 ; i < 3 ; i++ )
		{
			GraphAdj[ i ] = Copy.GraphAdj[ i ];
		}
		Locate = Copy.Locate;
		Order = Copy.Order;
	}
	graph operator=(const graph& Copy )
	{
		for( int i = 0 ; i < 3 ; i++ )
		{
			GraphAdj[ i ] = Copy.GraphAdj[ i ];
		}
		Locate = Copy.Locate;
		Order = Copy.Order;
		return *this;

	}
	int getOrder()
	{
		return Order;
	}
	int getSize()
	{
		return GraphAdj[ 2 ].at( 0 );
	}
	void UpdateLocate()
	{
		int LocateSize = Locate.size();
		int GraphAdjSize = GraphAdj[0].size();
		
		for( int i = 1 ; i < LocateSize ; i++ )
			Locate.at( i ) = -1 ;
		//
		int temp = GraphAdj[0].at( 1 );
		Locate.at(temp) = 1;

		for( int i = temp + 1 ; i < GraphAdjSize ; i++ )
		{
			if ( temp != GraphAdj[ 0 ].at( i ) )
			{
				temp = GraphAdj[0].at( i );
				Locate.at(temp) = i;
			}
		}
	}
	int Dijkstra_Find_farestCity(const int& s)
	{
		//cout<<endl << endl <<"Start"<<endl<<endl ;

		PriorityQueue<int> Q ;
		vector<int> d (Order);
		int dSize = d.size();
		for( int i = 1 ; i < dSize ; i++ )
		{
			if( i != s )
			{
				Q.push(i, INF );
				d.at( i ) = INF ;
			}
			else if ( i == s )
			{
				Q.push(i, 0 );
				d.at( i ) = 0;
			}
		}

		//
		//cout<<"Size Q is: " << Q.size() <<endl;
		while( !Q.empty() )
		{
			int u = Q.popLowestPriority();
			int LocateU = Locate.at( u ) ;
			int temp = GraphAdj[ 0 ].at( LocateU );
			int i = LocateU;


			int GraphAdjSize = GraphAdj[1].size();

			while( i < GraphAdjSize && (temp == GraphAdj[ 0 ].at( i )))
			{
				int v = GraphAdj[ 1 ].at( i ) ;
				int wuv = GraphAdj[2].at( i );
				int dist;
				if( d.at( u ) == INF )
					dist = INF;
				else
				{
					dist = d.at( u ) + wuv ;
				}
				if( d.at( v ) > dist )
				{
					d.at( v ) = dist ;
					Q.changePriority(v,dist);
				}
				i++;
			}

		}
		int maxD = 0;

		for( int i = 1 ; i <dSize -1 ; i++ )
			if ( d.at( i ) != INF && maxD < d.at( i ) )
				maxD = d.at( i ) ;
		return maxD;

	}
	int getEdge( const int& v1 , const int& v2 )
	{
		int i1 = Locate.at( v1 ) ;
		if( i1 == -1 )
			return INF ;


		int temp = GraphAdj[ 0 ].at( i1 );
	
		int i2 = i1 ;
		int GraphAdjSize = GraphAdj[ 1 ].size();
		while( ( i2 <GraphAdjSize ) && ( temp == (GraphAdj[ 0 ].at( i2 ))) )
		{
			if( GraphAdj[ 1 ].at( i2 ) == v2 )
				return GraphAdj[2].at(i2);
			else
				i2++;
		}


		return INF;
	
	}
	void addEdge(const int& v1,const int& v2 ,const int& w , bool update=false )
	{
		if( GraphAdj[ 0 ].size() == 1 )
		{

		}
		int i = 1 ;
		int GraphAdjSize = GraphAdj[ 0 ].size();
		while( i < GraphAdjSize && GraphAdj[ 0 ].at( i ) < v1 )
		{
			i++;
		}

		if( i == GraphAdj[ 0 ].size() )
		{
			GraphAdj[ 0 ].push_back( v1 );
			GraphAdj[ 1 ].push_back( v2 );
			GraphAdj[ 2 ].push_back( w );
		}
		else
		{
			vector<int>::iterator it;

			it = GraphAdj[0].begin();
			GraphAdj[ 0 ].insert(it+i,v1);

			it = GraphAdj[1].begin();
			GraphAdj[ 1 ].insert(it+i,v2);

			it = GraphAdj[2].begin();
			GraphAdj[ 2 ].insert(it+i,w);
		}
		GraphAdj[2].at(0)++;
		//update Locate
		if( update == true )
		{
			UpdateLocate();
		}
		
	}
	void removeEdge(const int& v1 , const int& v2 )
	{
		int i1 = Locate.at( v1 ) ;
		if( i1 == -1 )
			return ;
		int temp = GraphAdj[ 0 ].at( i1 );
	
		int i2 = i1 ;
		int GraphAdjSize = GraphAdj[ 1 ].size();
		while( ( i2 <GraphAdjSize ) && ( temp == (GraphAdj[ 0 ].at( i2 ))) )
		{
				if( GraphAdj[ 1 ].at( i2 ) == v2 )
				{
					vector<int>::iterator it;

					it = GraphAdj[ 0 ].begin();
					GraphAdj[0].erase(it+i2);

					it = GraphAdj[ 1 ].begin();
					GraphAdj[1].erase(it+i2);

					it = GraphAdj[ 2 ].begin();
					GraphAdj[2].erase(it+i2);
					GraphAdj[2].at(0)--;
					//update Locate
					UpdateLocate();
					return;
				}
				else
					i2++;
		}

	}

	graph(int order)
	{
		Order = order+1;
		//Locate.resize(Order);
		for( int i = 0 ; i < Order ; i++ )
			Locate.push_back(-1);
		GraphAdj[ 0 ].push_back(Order);
		GraphAdj[ 1 ].push_back(Order);
		GraphAdj[ 2 ].push_back(0);
	}
};

int findIntersection( graph& g , int I ,int NumberOfFireStation)
{
	vector<int>	MaxDistance ( I+2 ) ;
		//
	
	for( int i = 1 ; i < I + 1 ; i++ )
	{
		//Build FireStation on Intersetion i
		graph g1 = g ;
		int sg = g.getSize();
		g1.addEdge(i,I+1,0);
		g1.addEdge(I+1,i,0,true);
		int sg1 = g1.getSize();
		
		MaxDistance[ i ] = g1.Dijkstra_Find_farestCity(I+1);
	}
	int MinD = MaxDistance[1],IndexMin = 1 ;
	for( int i = 2 ; i < I + 1 ; i++ )
	{
		if( MinD > MaxDistance[ i ] )
		{
			MinD = MaxDistance[ i ];
			IndexMin = i ;
		}

	}
	return IndexMin;
}

int main()
{
	int NumberOfTestCase;
	cin>>NumberOfTestCase;
	for(int number = 0 ; number < NumberOfTestCase ; number++)
	{
		//structure of Graph 
		vector<int> GraphAdj[ 3 ];
		
		int F , I ;
		cin >> F >> I ;
		if( I == 1 )
		{
			cout<<"1"<<endl;
		}
		else
		{
			graph g(I+1);
			//
			for( int i = 0 ; i < F ; i++ )
			{
				int FirStation ;
				cin>>FirStation;

				g.addEdge(FirStation,I+1,0);
				g.addEdge(I+1,FirStation,0);
			}

			string Input ;
			cin.ignore(10, '\n' );
			getline(cin,Input,'\n');

			while( !Input.empty())
			{
				istringstream iss(Input);
				int v1 , v2 , Edge;
				iss>>v1;
				iss>>v2;
				iss>>Edge;

				g.addEdge(v1,v2,Edge);
				g.addEdge(v2,v1,Edge);
				
				getline(cin,Input,'\n');
			}
			g.UpdateLocate();
			cout<<findIntersection(g,I , F ) <<endl ;
			
			if( number != NumberOfTestCase - 1 )
				cout<<endl;
		}
	
	}
	return 0;
}






brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10278 - Fire Station

Post by brianfry713 »

Input:

Code: Select all

2

1 1
1

1 7
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
7 1 10
AC output:

Code: Select all

1

4
Check input and AC output for thousands of problems on uDebug!

Ryan
New poster
Posts: 1
Joined: Thu May 24, 2012 8:49 pm

Re: 10278 - Fire Station

Post by Ryan »

Nice article of yours about "10278 - Fire Station". I like your well post. How can I help you ? I think your topic about road distance between cities with fire station. Thanks for your fine sharing.

cyberdragon
New poster
Posts: 20
Joined: Fri Aug 30, 2013 5:42 am

10278 - Fire Station

Post by cyberdragon »


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10278 - Fire Station

Post by brianfry713 »

Input:

Code: Select all

1

1 15
13
1 2 92
1 3 24
1 7 56
1 8 38
1 11 23
1 12 66
1 13 68
1 14 17
2 3 47
2 4 58
2 5 11
2 6 73
2 7 66
2 10 24
2 11 37
2 12 84
2 13 49
3 5 58
3 6 29
3 9 42
3 10 65
3 11 80
3 12 60
3 13 37
3 15 57
4 6 74
4 7 45
4 8 30
4 11 62
5 9 57
5 13 95
5 15 55
6 7 5
6 9 61
6 10 9
6 11 56
6 12 15
6 13 56
6 14 84
6 15 78
7 9 25
7 11 81
7 12 49
8 9 19
8 10 4
8 11 60
8 12 8
8 13 51
8 14 17
9 10 25
9 11 72
9 12 36
9 13 85
9 15 80
10 12 24
10 14 24
10 15 62
11 12 85
11 13 15
11 14 33
11 15 23
12 14 42
12 15 46
13 15 26
AC output 10
Check input and AC output for thousands of problems on uDebug!

Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

Re: 10278 - Fire Station

Post by Farsan »

Is there anyway to solve the problem by running dijkstra's algo only once instead of placing firestation at every possible intersection?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10278 - Fire Station

Post by brianfry713 »

I got AC in 0.022 seconds by running Dijkstra's Algorithm from every intersection that doesn't already have a fire station.

I got AC in 1.356 seconds using the Floyd-Warshall Algorithm.

This line from the problem statement is not met in the judge's input: "there will exist a route between any pair of intersections."
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 102 (10200-10299)”