## 10349 - Antenna Placement

Moderator: Board moderators

erdos
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

### 10349 - Antenna Placement

Hi,

I was trying to solve this problem but it seems by algorithm has some flaw.
My idea was to go thru the map from left to right and top to bottom (as usually) when we find and '*', increment antennaCount, signal this place (i, j) as covered.If there's another antenna at right signal it as covered too else if there's another another antenna at bottom signal as covered.
This works for the examples and only requires 2 types of antennas.
I don't know what's wrong with this line of thinking...
Could someone tell me ? It would be great to see a test case where this doesn't work (I can't think of any...this seems simple).
Does this problem has any other trick or is there something else in the problem description I did not understood ?

Regards,

Jose Santos

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
Can your algorithm handle cases like:

Code: Select all

``````***
*oo
*oo
*oo
``````
?

erdos
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:
Yes, it can.It gives 3 that's the optimal solution.
(What i do is to try to see if it's first on next row and then if it's on next column, I said the opposite in the first post)

However, if I changed the ordered of placement the solution would be 4.
I can now think what's wrong, the problem is harder than what I thought.

Thanks!

Regards,

Jose Santos

uzioriluzan
New poster
Posts: 27
Joined: Thu Feb 14, 2002 2:00 am
I've seen this hint at :
http://www.ioiforum.org/en/view.asp?id=32521

- let m be the number of '*' & n be maxmatch of '*'s, the answer is m - n

Does anyone know the meaning of "number of maxmatch of *s"?

I've tried it using DFS, but it obviously gives Time Limit Exceeded...

Thanks a lot!
[/url]

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
This is a bipartite matching problem (although it has other solutions as well, one of them is dynamic programming). If you think of the whole region as a big chess board, you'll notice that each antenna placement will cover one black square and one white square. Thus you can create a bipartite graph with all squares to be covered on white squares in one partition and all squares to be covered on black squares in another partition. Connect two squares if they're adjacent to one another.

The maximum matching in this graph corresponds to which placements you should put to cover exactly two squares. If there are 10 squares in partition A and 7 square in partition B, and the maximum matching is, say, 5, this means that you can cover 10 of the 17 with 5 placements and the remaining 7 have to be covered one by by one. Thus the answer is 12 which happens to be 17-maxmatching.

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela
Thanxs Yarin.

Talking about matcihng i would like to know where I can found information or somebody who could explain it here how i implement minimum cost perfect matching. I know that this is not the problem here and that Bipartite matching is a lot more easy to do but i am interested in this subject. Any help would be appretiated.
Those Who Don't Know History are doomed to repeat it

uzioriluzan
New poster
Posts: 27
Joined: Thu Feb 14, 2002 2:00 am
Thanks Yarin! I've solved it today using this different approach:

Greed Algorithm: at each step choose the point of interest not covered which is adjacent to the biggest amount of points of interests which are not yet covered. If there is more than one point of interest with the same minimum, choose one arbitrarily.

This point chosen, select arbitrarily one of its edges and mark the adjacent vertice.

Example:

*****
oo*oo

1) choose (0,0) (0,4) or (1,2). All of them are adjacent to exactly one point of interest not yet covered. suppose you choose (0,0). Then select the edge (0,0)-(0,1) and mark both (0,0) and (0,1) as covered.

2) choose (0,4) or (1,2). They both are adjacent to one point of interest not covered. Suppose you choose (0,4). Then select the edge (0,4)-(0,3) and mark both (0,4) and (0,3) as covered.

3) chose (0,2) or (1,2). They both are adjacent to one point of interest not covered. Suppose you choose (0,2). Then select the edge (0,2)-(1,2) and mark both (0,2) and (1,2) as covered.

4) You are done since every point of interest is covered...

I'm quite sure this algorithm works, since it got Accepted. Can anyone find a counter-example?

Yarin wrote:This is a bipartite matching problem (although it has other solutions as well, one of them is dynamic programming). If you think of the whole region as a big chess board, you'll notice that each antenna placement will cover one black square and one white square. Thus you can create a bipartite graph with all squares to be covered on white squares in one partition and all squares to be covered on black squares in another partition. Connect two squares if they're adjacent to one another.

The maximum matching in this graph corresponds to which placements you should put to cover exactly two squares. If there are 10 squares in partition A and 7 square in partition B, and the maximum matching is, say, 5, this means that you can cover 10 of the 17 with 5 placements and the remaining 7 have to be covered one by by one. Thus the answer is 12 which happens to be 17-maxmatching.

Shih-Chia Cheng
New poster
Posts: 17
Joined: Fri May 24, 2002 4:24 am
Location: Taiwan
Contact:
uzioriluzan wrote:Thanks Yarin! I've solved it today using this different approach:

Greed Algorithm: at each step choose the point of interest not covered which is adjacent to the biggest amount of points of interests which are not yet covered. If there is more than one point of interest with the same minimum, choose one arbitrarily.

This point chosen, select arbitrarily one of its edges and mark the adjacent vertice.

Example:

*****
oo*oo

1) choose (0,0) (0,4) or (1,2). All of them are adjacent to exactly one point of interest not yet covered. suppose you choose (0,0). Then select the edge (0,0)-(0,1) and mark both (0,0) and (0,1) as covered.

2) choose (0,4) or (1,2). They both are adjacent to one point of interest not covered. Suppose you choose (0,4). Then select the edge (0,4)-(0,3) and mark both (0,4) and (0,3) as covered.

3) chose (0,2) or (1,2). They both are adjacent to one point of interest not covered. Suppose you choose (0,2). Then select the edge (0,2)-(1,2) and mark both (0,2) and (1,2) as covered.

4) You are done since every point of interest is covered...

I'm quite sure this algorithm works, since it got Accepted. Can anyone find a counter-example?
I adopt the same algorithm like yours.
And I think there is no counter example because you can use induction to prove the correctness of it.

uzioriluzan
New poster
Posts: 27
Joined: Thu Feb 14, 2002 2:00 am

### Judge is wrong

Just to let you know...
Although the problem description states that h < 40 and w < 10, there is in the judge's input a data set with h=40 and w=10. Be careful!

pernick
New poster
Posts: 2
Joined: Thu Sep 12, 2002 8:38 am
uzioriluzan wrote:Greed Algorithm: at each step choose the point of interest not covered which is adjacent to the biggest amount of points of interests which are not yet covered. If there is more than one point of interest with the same minimum, choose one arbitrarily.

This point chosen, select arbitrarily one of its edges and mark the adjacent vertice.

Example:

*****
oo*oo

1) choose (0,0) (0,4) or (1,2). All of them are adjacent to exactly one point of interest not yet covered. suppose you choose (0,0). Then select the edge (0,0)-(0,1) and mark both (0,0) and (0,1) as covered.

2) choose (0,4) or (1,2). They both are adjacent to one point of interest not covered. Suppose you choose (0,4). Then select the edge (0,4)-(0,3) and mark both (0,4) and (0,3) as covered.

3) chose (0,2) or (1,2). They both are adjacent to one point of interest not covered. Suppose you choose (0,2). Then select the edge (0,2)-(1,2) and mark both (0,2) and (1,2) as covered.

4) You are done since every point of interest is covered...

I'm quite sure this algorithm works, since it got Accepted. Can anyone find a counter-example?
****o**
*oo****
*oo*ooo
**o*ooo
****ooo

One cannot arbitrarily choose an edge

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Not an arbitrary edge, but with the right precedence you can use greedy. In every mark-step you search for an unmarked '*' with 0/1 unmarked adjacent '*'. If there is no such '*' select an arbitrary unmarked '*' with 2 unmarked adjacent '*'.

pernick
New poster
Posts: 2
Joined: Thu Sep 12, 2002 8:38 am
Here is example:
****o**
*oo****
*oo*ooo
**o*ooo
****ooo
There is no '*' with 0/1 unmarked adjacent '*'. So select an arbitrary unmarked '*' with 2 unmarked adjacent '*'.
a***o**
aoo****
*oo*ooo
**o*ooo
****ooo
And so on by greedy algorithm:
1223o*5
1oo3445
*oo6ooo
99o6ooo
8877ooo
But the optimal
1122o44
0oo3355
0oo6ooo
99o6ooo
8877ooo

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Ok, you are right.
I should have tried it before saying something.

jupiter777
New poster
Posts: 8
Joined: Sun Mar 30, 2003 9:44 pm

### help!p:-10349

i can't find out whats the wrong with my code! plz help me with that.
here's my code:-
.............................................................................................................
#include<stdio.h>
#include<string.h>
void dfs_visit(long r, long c);
long valid(long r, long c);
long m,n,count;
char grid[41][41];
long dfs(void){

long r,c;
for(r=0;r<m;r++)
for(c=0;c<n;c++)
if(grid[r][c]=='*'){
if((grid[r][c-1]=='*')||(grid[r][c+1]=='*')||(grid[r-1][c]=='*')||(grid[r+1][c]=='*')){
grid[r][c]='o';
if(grid[r][c-1]=='*')c=c-1;
else if(grid[r][c+1]=='*')c=c+1;
else if(grid[r-1][c]=='*')r=r-1;
else if(grid[r+1][c]=='*')r=r+1;
// count++;
dfs_visit(r,c);
}
else dfs_visit(r,c);
}
return count;
}
void dfs_visit(long r, long c){
long i,nr,nc;
long dr[4]={0,-1,0,1};
long dc[4]={-1,0,1,0};
grid[r][c]='o';
count++;
for(i=0;i<4;i++){
nr=r+dr;
nc=c+dc;
if((valid(nr,nc)==1)&&('*'==grid[nr][nc])) {
if((grid[nr][nc-1]=='*')||(grid[nr][nc+1]=='*')||(grid[nr-1][nc]=='*')||(grid[nr+1][nc]=='*')){
grid[nr][nc]='o';
if(grid[nr][nc-1]=='*')nc=nc-1;
else if(grid[nr][nc+1]=='*')nc=nc+1;
else if(grid[nr-1][nc]=='*')nr=nr-1;
else if(grid[nr+1][nc]=='*')nr=nr+1;
dfs_visit(nr,nc);
}
else dfs_visit(nr,nc);
}
}
}
long valid(long r, long c) {

if(r<0||c<0||r>=m||c>=n)return 0;
return 1;
}
int main(){
// freopen("10349.in","rt",stdin);
// freopen("300.out","w",stdout);

long i,j,co,test,u;
char ch;
while(scanf("%ld",&test)==1){
fflush(stdin);
for(u=0;u<test;u++){
count=0;
scanf("%ld%ld",&m,&n);

//if(m==0&&n==0)break;

for(i=0;i<m;i++) {
scanf("%c",&ch);
for(j=0;j<n;j++)
scanf("%c",&grid[j]);
}

co=dfs();
printf("%ld\n",co);
fflush(stdin);
} }
return 0;

}

jupiter777
New poster
Posts: 8
Joined: Sun Mar 30, 2003 9:44 pm

### help!p:-10349

i can't find out whats the wrong with my code! plz help me with that.
here's my code:-
.............................................................................................................
#include<stdio.h>
#include<string.h>
void dfs_visit(long r, long c);
long valid(long r, long c);
long m,n,count;
char grid[41][41];
long dfs(void){

long r,c;
for(r=0;r<m;r++)
for(c=0;c<n;c++)
if(grid[r][c]=='*'){
if((grid[r][c-1]=='*')||(grid[r][c+1]=='*')||(grid[r-1][c]=='*')||(grid[r+1][c]=='*')){
grid[r][c]='o';
if(grid[r][c-1]=='*')c=c-1;
else if(grid[r][c+1]=='*')c=c+1;
else if(grid[r-1][c]=='*')r=r-1;
else if(grid[r+1][c]=='*')r=r+1;
// count++;
dfs_visit(r,c);
}
else dfs_visit(r,c);
}
return count;
}
void dfs_visit(long r, long c){
long i,nr,nc;
long dr[4]={0,-1,0,1};
long dc[4]={-1,0,1,0};
grid[r][c]='o';
count++;
for(i=0;i<4;i++){
nr=r+dr;
nc=c+dc;
if((valid(nr,nc)==1)&&('*'==grid[nr][nc])) {
if((grid[nr][nc-1]=='*')||(grid[nr][nc+1]=='*')||(grid[nr-1][nc]=='*')||(grid[nr+1][nc]=='*')){
grid[nr][nc]='o';
if(grid[nr][nc-1]=='*')nc=nc-1;
else if(grid[nr][nc+1]=='*')nc=nc+1;
else if(grid[nr-1][nc]=='*')nr=nr-1;
else if(grid[nr+1][nc]=='*')nr=nr+1;
dfs_visit(nr,nc);
}
else dfs_visit(nr,nc);
}
}
}
long valid(long r, long c) {

if(r<0||c<0||r>=m||c>=n)return 0;
return 1;
}
int main(){
// freopen("10349.in","rt",stdin);
// freopen("300.out","w",stdout);

long i,j,co,test,u;
char ch;
while(scanf("%ld",&test)==1){
fflush(stdin);
for(u=0;u<test;u++){
count=0;
scanf("%ld%ld",&m,&n);

//if(m==0&&n==0)break;

for(i=0;i<m;i++) {
scanf("%c",&ch);
for(j=0;j<n;j++)
scanf("%c",&grid[j]);
}

co=dfs();
printf("%ld\n",co);
fflush(stdin);
} }
return 0;

}