## 11419 - Sam I Am

Moderator: Board moderators

### 11419 - Sam I Am

Hello guys!
I am trying to solve this problem, but get WA.
Maybe someone with AC may tell me whether my approach is right/wrong? I greedily fire the cannon at row or col which has maximum enemies in it, after what I do erase enemies and update matrices. To store information about enemies I use R*C matrix of boolean type (is there an enemy on position (i;j) ) and two linear matrices for storing how much enemies there are in given row or col.

upd: by the way, new forum is nice, fresh-looking.
Now I lay me down to sleep...
my profile
andysoft
Experienced poster

Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS

### Re: 11419 - Sam I Am

This problem can be solved using König's theorem.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

### Re: 11419 - Sam I Am

Is memoization too slow for this problem?
Samiul
New poster

Posts: 36
Joined: Thu Dec 13, 2007 3:01 pm

### Re: 11419 - Sam I Am

Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

### Re: 11419 - Sam I Am

In function memo, I send two ints r and c. Then I check if there is any enemy on row r, after and including column c, and on column c after and including row r.If there is, res[r][c] = min( res[r + 1][c] , min[r][c + 1] ) + 1, else
res[r][c] = res[r + 1][c + 1].

My idea is, if I shoot on row r, then all I have to think about is the rectangle (r+1,c) to (row,col), because row r contains no more enemies.

My code:
Code: Select all
#include<iostream>

using namespace std ;

#define MAX 1005

int row ;
int col ;
bool board[MAX][MAX] ;
int res[MAX][MAX] ;
int move[MAX][MAX] ;

int memo(int r , int c)
{
if(r == row + 1 || c == col + 1)
return 0 ;

if(res[r][c] != -1)
return res[r][c] ;

bool enemy = false ;
for(int i = c ; i <= col ; i++)
{
if(board[r][i] == true)
{
enemy = true ;
break ;
}
}
for(int i = r ; i <= row ; i++)
{
if(board[i][c] == true)
{
enemy = true ;
break ;
}
}
if(!enemy)
{
res[r][c] = memo(r + 1 , c + 1) ;
move[r][c] = 2 ;
return res[r][c] ;
}

if(memo(r , c + 1) < memo(r + 1 , c))
move[r][c] = 1 ;
else
move[r][c] = 3 ;

res[r][c] = min(memo(r , c + 1) , memo(r + 1 , c)) + 1 ;
return res[r][c] ;
}

void show(int r , int c)
{
if(r == row + 1 || c == col + 1)
return ;

if(move[r][c] == 2)
show(r + 1 , c + 1) ;
else if(move[r][c] == 1)
{
printf(" c%d" , c) ;
show(r , c + 1) ;
}
else
{
printf(" r%d" , r) ;
show(r + 1 , c) ;
}
}

int main()
{
int n ;

freopen("1.txt" , "r" , stdin) ;

while(scanf("%d %d %d" , &row , &col , &n) && row && col && n)
{
memset(board , false , sizeof(board)) ;
memset(res , -1 , sizeof(res)) ;
for(int i = 0 ; i < n ; i++)
{
int r , c ;
scanf("%d %d" , &r , &c) ;
board[r][c] = true ;
}
printf("%d" , memo(1 , 1)) ;
show(1 , 1) ;
printf("\n") ;
}
}
Samiul
New poster

Posts: 36
Joined: Thu Dec 13, 2007 3:01 pm

### Re: 11419 - Sam I Am

Try the case.

Input:
Code: Select all
9 14 20
1 5
1 7
2 2
2 3
2 4
3 4
3 9
3 13
4 2
4 5
4 8
5 10
7 1
7 4
7 6
7 7
7 8
8 1
8 5
9 3
0 0 0

Output:
Code: Select all
8 r1 r2 r3 r4 r5 r7 r8 r9

Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

### Re: 11419 - Sam I Am

Thanks. I see my idea was wrong.
Last edited by Samiul on Sun Aug 17, 2008 2:12 pm, edited 1 time in total.
Samiul
New poster

Posts: 36
Joined: Thu Dec 13, 2007 3:01 pm

### Re: 11419 - Sam I Am

I tried to solve this prob but getting WA. Here is my code.
anyone can tell me what i have done wrong here.
Code: Select all
Got AC.........
Last edited by mmonish on Sun May 11, 2008 3:05 pm, edited 2 times in total.
mmonish
Experienced poster

Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

### Re: 11419 - Sam I Am

Try the case below.

Input:
Code: Select all
5 8 8
1 6
2 2
2 8
3 3
3 8
4 2
4 3
5 8
0 0 0

Output:
Code: Select all
4 r1 c2 c3 c8

Hope it helps.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

### Re: 11419 - Sam I Am

thx Jan.Silly mistake on coding.
Now i correct it but still i m getting WA.

I edit my previous post with new code.
mmonish
Experienced poster

Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

### Re: 11419 - Sam I Am

Try the case. Almost similar error.

Input:
Code: Select all
12 16 25
1 2
1 16
2 5
2 9
3 4
4 14
5 4
5 10
5 15
5 16
6 4
7 2
7 14
8 6
8 11
8 13
9 13
9 16
10 4
10 8
10 15
11 16
12 7
12 11
12 15
0 0 0

Output:
Code: Select all
10 r2 r5 r8 r9 r10 r12 c2 c4 c14 c16
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

### Re: 11419 - Sam I Am

@Jan

I thought about minimum vertex cover with a graph, has right side N rows & N Cols & left side has Ids for points.
Edge from right to left side when the (Row/Col) can fire this point. I think that this answer the problem, but it can not fit in time.

Sleep enough after death, it is the time to work.
898989
Learning poster

Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt

### Re: 11419 - Sam I Am

I solved this problem using min-cut.

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

### Re: 11419 - Sam I Am

yes, min-cut will lead to same value.

can you explain the idea ( in specific do u have time problems)?
Sleep enough after death, it is the time to work.
898989
Learning poster

Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt

### Re: 11419 - Sam I Am

No, I didn't have any problem related to time limit.

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am