## 11463 - Commandos

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

Moderator: Board moderators

### 11463 - Commandos

Hi,

i have no idea about this problem,

can anyone else help me?
wahaha
New poster

Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

### Re: 11463 - Commandos

Use Floyd-Warshall in O(|V|^3), or two bfs in O(|E|) time.
Robert Gerbicz
Experienced poster

Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek

### Re: 11463 - Commandos

for the sample
4
3
0 1
2 1
1 3
0 3

it seems i am confused about the problem

i know there needs two commandos and the path is

0->1->3 which needs two units time
0->1->2->1->3 which needs four units time

i think there are so many status and i can only think the searching algorithm, but it seems too slow.

i can not implement Floyd-Warshall or other algorithms for this problem, can you show me for details.

thanks a lot.
wahaha
New poster

Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

### Re: 11463 - Commandos

There is no restriction in how many commandos you use.
If there is N buildings, think about using N commandos (one command for one building).

-----
Rio

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

### Re: 11463 - Commandos

i got it and ac finally.

when i draw the graph in paper and finally realize it can simply reduce to a very simple formula.

thx a lot.

wahaha
New poster

Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

### Re: 11463 - Commandos

Hi, I am getting W.A in this problem.
Someone please help.
Code: Select all
`Removed after AC.`

Thanks in advance to all.
Last edited by mukit on Wed Sep 10, 2008 12:03 pm, edited 1 time in total.
mukit
New poster

Posts: 48
Joined: Wed Nov 21, 2007 10:09 am
Location: Dhaka , Bangladesh

### Re: 11463 - Commandos

Mukit, your approach is correct, but it is not clear what you were trying to do after finding the all pair shortest path.

The actual answer is MAX(dist[root][i]+dist[i][dest] ) for all i.

Hope this helps.

shamim
A great helper

Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Dhaka

### Re: 11463 - Commandos

My approach was first finding the most distant node and then calculating the distance of this from the meeting node
and then sum them.
However thanks a lot to Shamim vi. I got AC now.
mukit
New poster

Posts: 48
Joined: Wed Nov 21, 2007 10:09 am
Location: Dhaka , Bangladesh

### Re: 11463 - Commandos

hi all,
i am litle confused how to use Floyd-Warshall's algorithm in this problem.
i searched for that algorithm & i found this general code
can someone help plz
Code: Select all
`for i = 1 to N   for j = 1 to N      if there is an edge from i to j         dist[0][i][j] = the length of the edge from i to j      else         dist[0][i][j] = INFINITY  for k = 1 to N   for i = 1 to N      for j = 1 to N         dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])`
sohanasr
New poster

Posts: 2
Joined: Wed Aug 27, 2008 11:55 pm

### Re: 11463 - Commandos

You can find the all pair shortest path with Floyd-Warshall algorithm..
After that, you should do something more..

See shamim's post
helloneo
Guru

Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 11463 - Commandos

thx a lot helloneo
i figured it out but, unfortunately i got WA :S
here is my code
Code: Select all
`#include<iostream>using namespace std;int dist[2][100][100]={0};bool Array1[100][100];int N,root,dest;void Commandos (int x,int counter,int a){   int q=0;   for (int i=0;i<N;i++)   {      if (i==x)         continue;      if (Array1[x][i]==true && Array1[i][x]==true && dist[a][x][i]==0)      {         Array1[x][i]=false;counter++;         if (a==1)            dist[a][dest][i]=counter;         else            dist[a][root][i]=counter;         Commandos(i,counter,a);         counter--;      }      else         q++;   }   if (q==N-1)      return;}int main(){   int count=0,counter=0,T,R;   scanf("%d",&T);   for (int z=0;z<T;z++)   {      counter=0;count++;bool Array[100][100]={false};      scanf("%d\n%d",&N,&R);      for (int y=0;y<R;y++)      {         scanf("%d %d",&root,&dest);         Array[root][dest]=true;         Array[dest][root]=true;      }      scanf("%d\n%d",&root,&dest);      for (int i=0;i<N;i++)         for (int j=0;j<N;j++)            Array1[i][j]=Array[i][j];      Commandos(dest,0,1);      for (int i=0;i<N;i++)         for (int j=0;j<N;j++)            Array1[i][j]=Array[i][j];      Commandos(root,0,0);      for (int i=0;i<N;i++)         if (counter<dist[0][root][i]+ dist[1][dest][i])               counter=dist[0][root][i]+ dist[1][dest][i];      printf("Case %d: %d\n",count,counter);      for (int i=0;i<N;i++)         for (int j=0;j<N;j++)         {            dist[0][i][j]=0;            dist[1][i][j]=0;         }   }   return 0;}`
sohanasr
New poster

Posts: 2
Joined: Wed Aug 27, 2008 11:55 pm

### Re: 11463 - Commandos

I used two bfs.
Tested input output.Still WA.
Can anyone give some critical input output?
Code: Select all
`3430 12 11 30 3210 11 0430 12 11 30 0`

output:
Code: Select all
`Case 1: 4Case 2: 1Case 3: 4`

lnr
Experienced poster

Posts: 134
Joined: Sat Jun 30, 2007 2:52 pm
Location: (DU,CSE)Dhaka,Bangladesh

### Re: 11463 - Commandos

Hi I try to solve this problem

But i get wa...........
I use two BFS...
Here is my code..............
PLZ help me..........

Code: Select all
`Cut after ACC.......`
Last edited by saiful_sust on Sat Sep 12, 2009 12:35 pm, edited 1 time in total.
saiful_sust
Learning poster

Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 11463 - Commandos

Some one PLZ help me .........

saiful_sust
Learning poster

Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 11463 - Commandos

Its boring no body help me

PLZ some one help me
saiful_sust
Learning poster

Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Next

Return to Volume CXIV

### Who is online

Users browsing this forum: No registered users and 0 guests