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 Jun 11, 2003 6:32 pm

if marcket and your home is in a same place , your output is zero .
but is that value zero all the time?
Though you have considered some cases, you have missed another.
__nOi.m....

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

Post by anupam » Thu Jun 12, 2003 9:40 am

:oops: :oops: :oops: missing your words.
will you be a little bit clear?
wanting help from all of you.
--
:oops: :oops: [/b]
"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 Jun 12, 2003 7:47 pm

your uses in your code :

if(s==d){printf("0\n");continue;}
here you don't consider further more check.
it is not always 0 for all input. you need futher check.

I have just found this bug on your code. Besides this , your code seems right to me. I can't say if there were any bugs.
__nOi.m....

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

Post by anupam » Sat Jun 14, 2003 1:31 pm

as i have to avoid the nodes in the shortest path.
if boss doesn't come s & d places so what cost there may be?
--
may be my problem was little like a fool. but i have no idea yet.
"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 » Sat Jun 14, 2003 6:36 pm

if(s==d){printf("0\n");continue;}
Here you have broken for processing further more.
as i have to avoid the nodes in the shortest path.
if boss doesn't come s & d places so what cost there may be?


yes you have to avoid the nodes in the shortest path of your boss.
But you have not consider boss's path if s==d. Why are you thinking if your_home==marcket && (office!=your_marcket || boss_home!=marcket) , then boss won't visit the marcket or your_home.

if i am not still clear, please tell me. i will try to give some sample input here.

i wish now you could solve this problem. :)
__nOi.m....

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

Post by anupam » Sun Jun 15, 2003 2:14 pm

i think i have got it.
but i will be happier if you give a sample input and corresponding output.
--
thanks for your great help.
---
:oops: :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 » Sun Jun 15, 2003 3:51 pm

hi,


Sample input:
3 3 1 2 3 3
1 2 8
1 3 4
2 3 3
I think this will clear you what i want to say. :)

wish you good luck.

[/list]
__nOi.m....

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

Post by Observer » Tue Jul 22, 2003 10:08 am

Shantanu wrote:2. Then find the nodes which are in the shortest path of boss (source to dest)
I don't understand...

Would there be more than ONE shortest path form the office and your boss' home?? If so, how can we do step 2 (quoted above) efficiently?


By DFS? DP??
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

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

Post by Noim » Tue Jul 22, 2003 10:22 am

hi observer,

i have got AC 2 times for this problem.
first i got AC considering only one shortest path from boss home to office.
then considering multiple shortest path.

as i got AC for both consideration independently, i think there is no inputs of multiple shortest path from boss home to offce.

Again, the interesting matter is that: the problem setter told the output of the intput given by Even (in page 1) is MISSION IMPOSSILBE. But if any program outputs "30" for that input, it would get AC. (i don't know if there declared any rejudgement for this problems or not).
__nOi.m....

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

Post by Observer » Tue Jul 22, 2003 10:27 am

Then I'll just have to use Dijkstra for this part... :D

Thx! I'll try it.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

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

Post by Noim » Tue Jul 22, 2003 12:19 pm

yes observer,

i have used Disktra' Algorithm too. :D
__nOi.m....

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

Post by anupam » Tue Jul 22, 2003 5:07 pm

hello noim, and even,
so why getting wa noe.
i think i figured out your test test cases perfectly..
here is the modified code..


Code: Select all

#include<stdio.h> 
#define INF 10000
#define N 10
int a[N][N],p[N][N],c[N],l,n,b[N][N]; 
int plus(int a,int b) 
{ 
   if(a==INF || b==INF) return INF; 
   return a+b; 
} 
void fw() 
{ 
   int i,j,k; 
   for(k=0;k<n;k++) 
      for(i=0;i<n;i++) 
         for(j=0;j<n;j++) 
            if(plus(b[i][k],b[k][j])<b[i][j]) 
            { 
               b[i][j]=b[i][k]+b[k][j]; 
               p[i][j]=p[k][j]; 
            } 
} 
void print(int i,int j) 
{ 
   if(i!=j) print(i,p[i][j]); 
   c[l++]=j; 
} 
main() 
{ 
   int m,bs,bd,s,d,i,j,in,inn,cost; 
   while(scanf("%d%d%d%d%d%d",&n,&m,&bs,&bd,&s,&d)!=EOF) 
   { 
      for(i=0;i<n;i++) for(j=0;j<n;j++) {a[i][j]=INF;p[i][j]=i;} 
      for(i=0;i<n;i++) a[i][i]=0; 
      for(i=0;i<m;i++) 
      { 
         scanf("%d%d%d",&in,&inn,&cost); 
         if(in!=inn) a[in-1][inn-1]=a[inn-1][in-1]=cost; 
      } 
      while(1) 
      { 
         for(i=0;i<n;i++) for(j=0;j<n;j++) b[i][j]=a[i][j],p[i][j]=i;; 
         fw(); 
         if(b[bs-1][bd-1]==INF) break; 
         l=0; 
         print(bs-1,bd-1); 
         for(i=0;i<l;i++) 
         { 
            for(j=0;j<n;j++) a[c[i]][j]=INF; 
         } 
      } 
      if(a[s-1][d-1]==INF || s==bs || s==bd || d==bs || d==bd) printf("MISSION IMPOSSIBLE.\n"); 
			else if(s==d)
			{
				printf("0\n");
			}
			else			printf("%d\n",a[s-1][d-1]);
   } 
   return 0; 
} 
plz help.
not getting ac for many dayz :oops: :oops: [/b]
"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 » Tue Jul 22, 2003 11:16 pm

Anupum vai,

there is a sample input below. may be this is only input you didn't consider.

Inputs:
5 5 1 2 3 4
1 2 1
1 5 10
5 2 10
3 5 1
5 4 1
outputs:
2
if you again got WA, please inform me.
__nOi.m....

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

Post by Noim » Wed Jul 23, 2003 12:50 am

Anupum vai,

you asigned the value of N as only 10.
but the value can be maximum 100.

your program even does not work for the input:

input:
9 5 1 2 3 4
3 5 1
5 6 1
6 7 1
7 8 1
8 4 1
output:
5
may be this is because of you used variable a[][] instead of b[][]. (may be absent mindly)
else printf("%d\n",a[s-1][d-1]);


it may be b[s-1][d-1]

&& also:
if(a[s-1][d-1]==INF || s==bs || s==bd || d==bs || d==bd) printf("MISSION IMPOSSIBLE.\n");


it may also be if(b[s-1][d-1]==INF....

you have calculated shortest path using b[][], and a[][] is used to cut the boss's path and copying to b[][] before using floyed-warshall algorithm on b[][] matrix. so b[][] contain the shortest path distance at the last of the program.
please don't mind if my explanation is wrong.

you have to consider another case:

if there is office on the shortest way to marcket from the home even office can not be reached from the boss home.
__nOi.m....

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

Post by Observer » Wed Jul 23, 2003 3:12 am

Excuse me...

According to the problem description:
"you must go outside your home to reach market and your boss must come outside to reach home (from office) or office (from home). "
and
"Your boss must not see you outside your home."
Does that mean that
1. Your home and the market are NOT at the same place;
2. The boss' home and the office are also NOT on the same spot;
3. Your home and the office are NOT on the same spot;
4. And your home and boss' home are NOT at the same place?

Then can
1. the market and the office be on the same spot;
2. the market and boss' home be on the same spot?

Thx for your attention!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Post Reply

Return to “Volume 103 (10300-10399)”