10349  Antenna Placement
Moderator: Board moderators
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
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

 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
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
(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

 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]
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]
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 17maxmatching.
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 17maxmatching.
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.
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.
Those Who Don't Know History are doomed to repeat it

 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 counterexample?
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 counterexample?
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 17maxmatching.

 New poster
 Posts: 17
 Joined: Fri May 24, 2002 4:24 am
 Location: Taiwan
 Contact:
I adopt the same algorithm like yours.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 counterexample?
And I think there is no counter example because you can use induction to prove the correctness of it.

 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!
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!
****o**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 counterexample?
*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
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
****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

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 New poster
 Posts: 8
 Joined: Sun Mar 30, 2003 9:44 pm
 Location: bangladesh
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][c1]=='*')(grid[r][c+1]=='*')(grid[r1][c]=='*')(grid[r+1][c]=='*')){
grid[r][c]='o';
if(grid[r][c1]=='*')c=c1;
else if(grid[r][c+1]=='*')c=c+1;
else if(grid[r1][c]=='*')r=r1;
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][nc1]=='*')(grid[nr][nc+1]=='*')(grid[nr1][nc]=='*')(grid[nr+1][nc]=='*')){
grid[nr][nc]='o';
if(grid[nr][nc1]=='*')nc=nc1;
else if(grid[nr][nc+1]=='*')nc=nc+1;
else if(grid[nr1][nc]=='*')nr=nr1;
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<0c<0r>=mc>=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;
}
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][c1]=='*')(grid[r][c+1]=='*')(grid[r1][c]=='*')(grid[r+1][c]=='*')){
grid[r][c]='o';
if(grid[r][c1]=='*')c=c1;
else if(grid[r][c+1]=='*')c=c+1;
else if(grid[r1][c]=='*')r=r1;
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][nc1]=='*')(grid[nr][nc+1]=='*')(grid[nr1][nc]=='*')(grid[nr+1][nc]=='*')){
grid[nr][nc]='o';
if(grid[nr][nc1]=='*')nc=nc1;
else if(grid[nr][nc+1]=='*')nc=nc+1;
else if(grid[nr1][nc]=='*')nr=nr1;
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<0c<0r>=mc>=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;
}

 New poster
 Posts: 8
 Joined: Sun Mar 30, 2003 9:44 pm
 Location: bangladesh
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][c1]=='*')(grid[r][c+1]=='*')(grid[r1][c]=='*')(grid[r+1][c]=='*')){
grid[r][c]='o';
if(grid[r][c1]=='*')c=c1;
else if(grid[r][c+1]=='*')c=c+1;
else if(grid[r1][c]=='*')r=r1;
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][nc1]=='*')(grid[nr][nc+1]=='*')(grid[nr1][nc]=='*')(grid[nr+1][nc]=='*')){
grid[nr][nc]='o';
if(grid[nr][nc1]=='*')nc=nc1;
else if(grid[nr][nc+1]=='*')nc=nc+1;
else if(grid[nr1][nc]=='*')nr=nr1;
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<0c<0r>=mc>=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;
}
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][c1]=='*')(grid[r][c+1]=='*')(grid[r1][c]=='*')(grid[r+1][c]=='*')){
grid[r][c]='o';
if(grid[r][c1]=='*')c=c1;
else if(grid[r][c+1]=='*')c=c+1;
else if(grid[r1][c]=='*')r=r1;
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][nc1]=='*')(grid[nr][nc+1]=='*')(grid[nr1][nc]=='*')(grid[nr+1][nc]=='*')){
grid[nr][nc]='o';
if(grid[nr][nc1]=='*')nc=nc1;
else if(grid[nr][nc+1]=='*')nc=nc+1;
else if(grid[nr1][nc]=='*')nr=nr1;
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<0c<0r>=mc>=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;
}