10349 - Antenna Placement

[erdos]

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]

Can your algorithm handle cases like:

Code: Select all

***
*oo
*oo
*oo

?

[erdos]

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]

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]

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]

Thanxs Yarin.

Very instructive your explanation.

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.

[uzioriluzan]

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?

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]

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]

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]

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

[Adrian Kuegel]

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]

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
Answer is 11
But the optimal
1122o44
0oo3355
0oo6ooo
99o6ooo
8877ooo
Answer is 10

[Adrian Kuegel]

Ok, you are right.
I should have tried it before saying something.

[jupiter777]

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]

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;

}