11419 - SAM I AM

[andysoft]

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.

Thank you in advance.

upd: by the way, new forum is nice, fresh-looking.

[Jan]

This problem can be solved using König's theorem.

[Samiul]

Is memoization too slow for this problem?

[Jan]

What is your idea?

[Samiul]

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") ;
	}
}

[Jan]

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

But your code generates 9.

[Samiul]

Thanks. I see my idea was wrong.

[mmonish]

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

[Jan]

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.

[mmonish]

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

I edit my previous post with new code.

[Jan]

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

[898989]

@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.

Can you please elaborate on your idea? Or correct me?

[emotional blind]

I solved this problem using min-cut.

[898989]

yes, min-cut will lead to same value.

can you explain the idea ( in specific do u have time problems)?

[emotional blind]

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