10354 - Avoiding Your Boss

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

Moderator: Board moderators

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Wed Jul 23, 2003 8:43 pm

observer,

"you must go outside your home to reach market and your boss must come outside to reach home (from office) or office (from home). "
"Your boss must not see you outside your home."
yes, what you showed, have some logics but i think: there can occur anything what you have mentioned can be or can not be. i mean any two or three or all places of the four terminal places can be the same, though i am not sure. But my two accepted program considered these. you may check judge input and output by submitting as your concepts mentioned by you above.
__nOi.m....

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Thu Jul 24, 2003 8:36 am

noim yet not solved are you a std of BUET ME? leave your Details
Last edited by anupam on Fri Jul 25, 2003 7:29 am, edited 1 time in total.
"Everything should be made simple, but not always simpler"

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Thu Jul 24, 2003 6:08 pm

Dear observer,

I was wrong. There may have some multiple shortest path in the input of judge input. i solved this problem again with the help of Floyd Warshall method. At firt i got WA for floyd Warshall method. but when i make a consideration of multiple inputs, i got AC using floyd warshell algorithm.

and the terminal position can be all same or some of them are same.

i have to agree , in case of multiple shortest path judge input is not completed enough. But there issss multiple shortest path,in the input.

take care.
__nOi.m....

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

10354 -> Incomplete Judge input.

Post by Noim » Thu Jul 24, 2003 8:39 pm

Avoiding the boss ( 10354)

the judge input for this problem is not completed. i have accepted this program thrice. But i have found that my first accepted program gave wrong answer for some input. The inputs and outputs are:

input:
3 3 1 2 3 3
1 2 2
1 3 1
3 2 1
6 6 2 5 3 3
3 2 2
3 5 8
2 5 10
5 1 15
3 4 18
5 4 8
6 6 2 4 1 1
3 5 11
5 1 2
5 4 8
2 5 13
1 4 6
3 4 7
7 7 2 6 4 4
1 3 2
5 3 17
3 6 5
4 6 4
3 4 1
2 3 4
1 2 12
output:
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
i think the input of this program should be completed.
__nOi.m....

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Fri Jul 25, 2003 7:33 am

Please tell me the terminal cases again.
I have forget these.
:oops:
"Everything should be made simple, but not always simpler"

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Fri Jul 25, 2003 12:06 pm

Anupum vai,

your program give the right output for the terminal case input.
i have sent you detail in pm. check it. i have also sent you almost 12 inputs and outputs.

take care.
__nOi.m....

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Aug 12, 2003 10:11 am

Could anyone plz give me yet more test cases?

I'm getting WA......

P.S. It's easier to construct the shortest paths with Dijkstra (than Floyd) :P
Last edited by Observer on Tue Aug 12, 2003 3:07 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Aug 12, 2003 10:19 am

Finally got ACC...

I wasted more than an hour because of a silly little mistake in the variable declaration part.... darn... :evil:

[EDIT @ July 2006]
Let me add a sample case here:

Code: Select all

12 17 6 11 12 9
1 2 1
2 3 1
3 4 1
1 5 1
2 6 1
3 7 1
4 8 1
5 6 1
6 7 1
7 8 1
5 9 1
6 10 1
7 11 1
8 12 1
9 10 1 
10 11 1
11 12 1
The map looks like this:

Code: Select all

x--x--x--x
|  |  |  |
x--BH-x--x
|  |  |  |
M--x--OF-YH
Have fun~ :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

WA in 10354

Post by shihabrc » Mon Aug 21, 2006 10:09 pm

Getiing WA in this problem. Here's the code:

Code: Select all

#include<stdio.h>
#include<vector>
#include<string.h>

using namespace std;

#define NIL 0
#define MAX 500
#define INF 99999999

typedef struct Node_
{
	int id,d;
} Node_;

bool visited[MAX+1];
bool visitedByBoss[MAX+1];
vector<Node_> adj[MAX+1];
int d[MAX+1],pre[MAX+1];
int v,E,home,office,shop,bossHome;


int findMin();
void markPath(int,int);

void main()
{
	int i,u,j;
	int m,n,cost;
	Node_  next,temp;

	while(scanf("%d %d %d %d %d %d",&v,&E,&bossHome,&office,&home,&shop) == 6)
	{
		for( i = 1; i <= v; i++)
		{
			adj[i].clear();
			d[i] = INF;
		}

		d[bossHome] = 0;

		for( i = 0; i < E; i++)
		{
			scanf("%d %d %d",&m,&n,&cost);
			temp.id = n;temp.d = cost;
			adj[m].push_back(temp);temp.id = m;
			adj[n].push_back(temp);
		}

		memset(visited,false,sizeof(visited));
		memset(visitedByBoss,false,sizeof(visitedByBoss));
		memset(pre,NIL,sizeof(pre));
		visitedByBoss[bossHome] = true;

		for( i = 0 ; i < v - 1; i++)
		{
			u = findMin();
			visited[u] = true;

			for( j = 0; j < adj[u].size(); j++)
			{
				next = adj[u][j];
				if(!visited[next.id])
				{
					if(d[next.id] > d[u] + next.d)
					{
						d[next.id] = d[u] + next.d;
						pre[next.id] = u;
					}
				}
			}
		}

		markPath(bossHome,office);

		if(visitedByBoss[home] || visitedByBoss[shop])
		{
			puts("MISSION IMPOSSIBLE.");
			continue;
		}
		
		memset(visited,false,sizeof(visited));
		for( i = 1; i <= v; i++) d[i] = INF;
		d[home] = 0;

		for( i = 0; i < v - 1; i++)
		{
			u = findMin();
			visited[u] = true;

			if( !visitedByBoss[u] )
			{
				for( j = 0; j < adj[u].size(); j++)
				{
					next = adj[u][j];
					if( !visited[next.id])
					{
						if(d[next.id] > d[u] + next.d)
							d[next.id] = d[u] + next.d;
					}
				}
			}
		}

		if(d[shop] >= INF) puts("MISSION IMPOSSIBLE.");
		else printf("%d\n",d[shop]);
	}	
}


int findMin()
{
	int i,minIndex,Min = INF;

	for( i = 1; i <= v; i++)
	{
		if( !visited[i])
		{
			if( d[i] < Min)
			{
				Min = d[i];
				minIndex = i;
			}
		}
	}

	return minIndex;
}

void markPath(int s,int t)
{
	if( pre[t] == NIL ) return;
	else
	{
		visitedByBoss[t] = true;
		markPath(s,pre[t]);
	}
}
This code handles the terminal cases(all the req. points are same or some of them are same). But getting WA. Can some1 chk this plz. Or give me some suggestions | | sample I/O.
Shihab
CSE,BUET

rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka

What is the problem of my code????

Post by rhsumon » Wed Jun 27, 2007 8:59 pm

I've posted it somedays ago but now i mean i'm the right way to solve it...
But still i'm getting WA
Plz check my code and give some suggetion.........
I've got all output true for the inputs in the conversation..........
But I got WA actually i mean i cant properly remove the sortest paths of the graph... Plz anyone chake my code.......

Code: Select all

#include<stdio.h>

const int inf=1000000;

int w[105][105], d[105][105],b[105][105];
int P, R, BH,YH, OF, M;

void init(){
	int i,j;
	for (i=1; i<=P; i++){
		for (j=1; j<=P; j++)
			d[i][j] = w[i][j];
		d[i][i] = 0;
	}
		
}



int main()
{
	//freopen("10354.out","w",stdout);
	int i,j,st,lt,cost,k;
	while(scanf("%d%d%d%d%d%d",&P,&R,&BH,&OF,&YH,&M) == 6){

		for(i=1; i<=P; i++){
			for(j=1; j<=P; j++)
				w[i][j] = inf;
		}
		for(i=0; i<R; i++){
			scanf("%d%d%d",&st,&lt,&cost);
			if(st != lt){
				w[st][lt] = cost;
				w[lt][st] = cost;
			}
		}

		/*if(YH==BH || YH==OF || M==BH || M==OF){
			printf("MISSION IMPOSSIBLE.\n");
			continue;
		}*/

		init();
		for(k=1; k<=P; k++){
			for(i=1; i<=P; i++){
				for(j=1; j<=P; j++){
					if(d[i][j] > d[i][k] + d[k][j])
						d[i][j] = d[i][k] + d[k][j];

				}
			}
		}

		for(k=1; k<=P; k++){
			if(d[BH][k]+d[k][OF]==d[BH][OF]){
				for(i=1; i<=P; i++){
					w[k][i]=inf;
					w[i][k]=inf;
				}
			}
		}

		init();
		for(k=1; k<=P; k++){
			for(i=1; i<=P; i++){
				for(j=1; j<=P; j++){
					if(d[i][j] > d[i][k] + d[k][j])
						d[i][j] = d[i][k] + d[k][j];

				}
			}
		}

		if(d[YH][M] != inf && d[YH][M] != 0)
			printf("%d\n",d[YH][M]);
		else printf("MISSION IMPOSSIBLE.\n");

	}
	return 0;
}

Plz help anyone............ I'm worried.....






[/url]
Last edited by rhsumon on Tue Apr 15, 2008 5:04 pm, edited 1 time in total.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Fri Oct 12, 2007 11:11 pm

Code: Select all

int main() {
	int i,j,k,r;

#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
#endif

	while ( scanf("%d %d %d %d %d %d\n",&n,&r,&boss,&office,&me,&market) == 6 ) {
		--boss, --office, --me, --market;
		memset(g,0xff,sizeof(g));
		for ( i = 0 ; i < n; i++ ) g[i][i] = 0;
		while ( r-- ) {
			scanf("%d %d %d\n",&i,&j,&k);
			--i, --j;
			if ( i == j ) continue;
			assert( g[i][j] == oo );
			g[i][j] = g[j][i] = k;
		}

		if ( boss == me || office == me || market == boss || market == office ) {
			IMP;
			continue;
		}

		for ( i = 0; i < n; i++ )
			for ( w[i][i] = 0, j = i+1; j < n; j++ )
				w[i][j] = w[j][i] = g[i][j];
		for ( k = 0; k < n; k++ )
			for ( i = 0; i < n; i++ )
				for ( j = 0; j < n; j++ )
					if ( w[i][k] < oo && w[k][j] < oo && w[i][j] > w[i][k] + w[k][j] )
					   w[i][j] = w[i][k] + w[k][j];
		for ( i = 0; i < n; i++ )
			danger[i] = (w[boss][i] < oo && w[i][office] < oo && w[boss][i] + w[i][office] == w[boss][office]);
		danger[boss] = danger[office] = 1;
		dijkstra_avoiding_danger_points(me,market);
	}
	return 0;
}
Verdict: WA.
What's the mistery about this problem, after all?
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

safait
New poster
Posts: 4
Joined: Sat Jun 08, 2013 10:49 am

what is output? for 10354 no problem

Post by safait » Mon Jun 10, 2013 1:21 pm

i need some input and output for testing my code. problem no is 10354.
and there are some input . i also need output of these input:
12 17 6 11 12 9
1 2 1
2 3 1
3 4 1
1 5 1
2 6 1
3 7 1
4 8 1
5 6 1
6 7 1
7 8 1
5 9 1
6 10 1
7 11 1
8 12 1
9 10 1
10 11 1
11 12 1
3 3 1 2 3 3
1 2 2
1 3 1
3 2 1
6 6 2 5 3 3
3 2 2
3 5 8
2 5 10
5 1 15
3 4 18
5 4 8
6 6 2 4 1 1
3 5 11
5 1 2
5 4 8
2 5 13
1 4 6
3 4 7
7 7 2 6 4 4
1 3 2
5 3 17
3 6 5
4 6 4
3 4 1
2 3 4
1 2 12

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

Re: what is output? for 10354 no problem

Post by brianfry713 » Tue Jun 11, 2013 12:16 am

AC output for your input:
7
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
Check input and AC output for thousands of problems on uDebug!

Aarya
New poster
Posts: 8
Joined: Thu Nov 21, 2013 6:05 pm

Re: 10354 - Avoiding Your Boss

Post by Aarya » Sun Mar 09, 2014 6:21 pm

Your boss must not see you outside your home. You can assume that the cost of reaching another location in the same place is zero and you must go outside your home to reach market and your boss must come outside to reach home (from office) or office (from home)
If I understood this statement correctly then
for these input:
2 1 3 3 3 3
1 2 1

2 2 3 3 3 3
1 2 1
2 3 2

output should be:
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
rather than:
0
0
Aren't they?
But when I ran my friend's accepted code against this it produced:
0
0
:evil:

Please clarify anyone
Thanks.

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

Re: 10354 - Avoiding Your Boss

Post by brianfry713 » Mon Mar 10, 2014 8:47 pm

Your input is invalid.

P = Total number of places. (0<P<=100)
R = Total number of connecting roads. (0<=R<=4950)
BH = The Place where your boss lives. (0<BH<=P)
OF = The place where your office is situated. (0<OF<=P)
YH = The place where your home is situated. (0<YH<=P)
M = The place where the market is situated. (0<M<=P)
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 103 (10300-10399)”