11419 - SAM I AM

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

11419 - SAM I AM

Post by 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.
Now I lay me down to sleep...
my profile

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11419 - Sam I Am

Post by Jan »

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

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

Re: 11419 - Sam I Am

Post by Samiul »

Is memoization too slow for this problem?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11419 - Sam I Am

Post by Jan »

What is your idea?
Ami ekhono shopno dekhi...
HomePage

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

Re: 11419 - Sam I Am

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11419 - Sam I Am

Post by 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.
Ami ekhono shopno dekhi...
HomePage

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

Re: 11419 - Sam I Am

Post by Samiul »

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

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

Re: 11419 - Sam I Am

Post by 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.........
Last edited by mmonish on Sun May 11, 2008 3:05 pm, edited 2 times in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11419 - Sam I Am

Post by 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.
Ami ekhono shopno dekhi...
HomePage

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

Re: 11419 - Sam I Am

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11419 - Sam I Am

Post by 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
Ami ekhono shopno dekhi...
HomePage

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

Re: 11419 - Sam I Am

Post by 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?
Sleep enough after death, it is the time to work.
Mostafa Saad

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 11419 - Sam I Am

Post by emotional blind »

I solved this problem using min-cut.

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

Re: 11419 - Sam I Am

Post by 898989 »

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

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 11419 - Sam I Am

Post by emotional blind »

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

Post Reply

Return to “Volume 114 (11400-11499)”