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 » Fri Apr 04, 2008 10:34 pm

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 » Sat Apr 05, 2008 12:22 am

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 » Fri May 02, 2008 10:27 am

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 » Fri May 02, 2008 11:47 am

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 » Fri May 02, 2008 2:06 pm

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 » Sat May 03, 2008 2:16 pm

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 » Sat May 03, 2008 3:08 pm

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 » Fri May 09, 2008 6:49 pm

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 » Sat May 10, 2008 11:46 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

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

Re: 11419 - Sam I Am

Post by mmonish » Sat May 10, 2008 6:05 pm

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 » Sat May 10, 2008 6:52 pm

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 » Fri Aug 15, 2008 12:44 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.

Can you please elaborate on your idea? Or correct me?
Sleep enough after death, it is the time to work.
Mostafa Saad

User avatar
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 » Tue Aug 19, 2008 8:03 pm

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 » Wed Aug 20, 2008 12:25 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.
Mostafa Saad

User avatar
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 » Fri Aug 22, 2008 10:41 am

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

Post Reply

Return to “Volume 114 (11400-11499)”