10502 - Counting Rectangles

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

Moderator: Board moderators

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Tue Jun 29, 2004 2:11 pm

thanks.
lemme read then=p

uzurpatorul
New poster
Posts: 5
Joined: Fri Oct 22, 2004 10:21 am

test cases .... right/wrong

Post by uzurpatorul » Tue Nov 09, 2004 12:34 pm

Could someone tell me if any of my test cases is wrong ?, is there any tricky test case ?

Regards,
R.

2
2
11
01
4
3
110
101
111
011
1
1
1
1
1
0
3
4
1111
1001
1001
4
4
1111
1111
1001
1001
3
3
111
111
111
4
4
1111
1111
1111
1111
5
5
11111
11111
11111
11111
11111
3
3
111
101
111
6
6
111111
100001
100001
100001
100001
111111
4
4
1011
1100
1011
1111
5
5
11101
01001
10110
11001
01101
4
7
1011011
1110001
1011111
1011011
10
10
1110001111
0101010101
1100110011
1110111100
1111111100
0011001111
1101101111
1111111111
0000000000
0000000000
4
4
0000
0000
0000
0000
2
4
0000
0000
2
4
1111
1111
0
------------------------------------------------------------------
5
22
1
0
20
44
36
100
225
20
80
30
26
59
270
0
0
30

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Tue Aug 16, 2005 6:59 pm

I invented two solutions.

First one has time complexity O(N^4) and gets ACC
in about 1.3 secs / memory complexity is O(N^2) /.

Second one is with time complexity O(N^3) and gets ACC
in exactly 0.051 secs / memory complexity is also O(N^3) /.
Much faster, that's clear. Dynamic Programming,
more memory usage for less running time. That's also clear.

Now... I have two questions.

1) Does this problem really have a O(N^2) solution ?!
I found such a statement in some other thread here dedicated
to problem 10502.

2) A weird fact ?! The judge says my first solution uses
468 kbytes of virtual memory AND my second one has only
low memory spent. How could that be ?! Once again have in mind
that my second solution uses O(N^3) memory and
my first one uses just O(N^2) ?! And that's not a coincidence,
I mean I made a lot of submissions and the Judge was always
giving these same results about the memory usage of my two
programs.

Any answers are welcome.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Aug 17, 2005 6:05 pm

Hi Sedefcho,

Yes there IS an O(n^2) solution!!!! However I don't wanna explain it here (for obvious reason; I currently hold the first rank for this problem :-)) Just a little hint for better timing: Do your DP as you get the input.

Btw, my O(n^4) solution (the one I have when I post this topic) gets Accpeted in 0.00.008 sec only....... :)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Aug 17, 2005 10:05 pm

Well, 0.008 secs with O(N^4) is pretty strange :)

OK, don't explain it. I will maybe do some research on
that O(N^2) algorithm when I have some time.

What about my second question ? Does anybody have
some explanation ?

randomtea
New poster
Posts: 5
Joined: Sun Apr 01, 2007 3:48 pm

Post by randomtea » Mon Apr 02, 2007 10:13 am

i used a O(n^6) way and TLEed

:o

toadstool
New poster
Posts: 1
Joined: Thu Apr 26, 2007 3:51 am
Contact:

Post by toadstool » Thu Apr 26, 2007 4:08 am

Why did I not read the input specifications? I always got timeout, even with a O(N^2) algorithm (both time and memory), until I found out that there were no spaces in input :P
At least I have a nice algorithm that is working

It's quite long time since your post, Sedefcho, but do you really use 486 KB for an O(N^2) algorithm? I mean, N<=100, it shouldn't need that much.

O(N^6) will fail, 100^6 (10^12) is too much. Try to do some preprocessing of the input, so that you don't have to check all squares in all possible rectangles, or do some cuts (a rectangle containing an invalid rectangle, is itself invalid, and all rectangles contained in a valid rectangle are valid)

Muftee_Ruet
New poster
Posts: 10
Joined: Fri Sep 16, 2011 6:36 am

Re: 10502 - Counting Rectangles

Post by Muftee_Ruet » Sun Jul 28, 2013 1:00 am

I used the same technique as the 836 - Largest Submatrix.

My code took .119s.

matheusdallrosa
New poster
Posts: 11
Joined: Fri Nov 08, 2013 11:04 pm

Re: 10502 - Counting Rectangles

Post by matheusdallrosa » Sun Jan 11, 2015 4:34 am

i tested exhaustively but i still get WA.

code:

Code: Select all

typedef long long int lld;

int main(){

	int n, m;
	char board[120][120];
	while( scanf(" %d", &n ) != EOF ){
		if(!n)break;
		scanf(" %d", &m );

		int t = 0;
		memset(board,'0',sizeof(board));
		for( int i = 1; i <= n; i++ ){
			for( int j = 1; j <= m; j++ ){
				scanf(" %c", &board[i][j] );

				if( board[i][j] == '1' ) t++;
			}
		}

		for( int i = 1; i <= n; i++ ){
			for( int j = 1; j <= m; j++ ){

				if( board[i][j] == '1' ){
	
					int k,fimColuna,fimLinha;

					for( k = j+1; k <= m && board[i][k] == '1'; k++ );
					fimColuna = k;
					t += k-j-1;

					for( k = i+1; k <= n && board[k][j] == '1'; k++ );
					fimLinha = k;
					t += k-i-1;
					
					for( int q = i+1; q < fimLinha; q++ ){
						
						for( int p = j+1; p < fimColuna; p++ ){
							if( board[q][p] == '0' ) {
								fimColuna--;
								break;
							}	
							else{		
								t++;
							}						
						}
					}
				}
			}
		}

		printf("%d\n", t );
	}

    return 0;
}
it worked for all cases that i tested on udebug.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10502 - Counting Rectangles

Post by brianfry713 » Tue Jan 13, 2015 3:01 am

That code won't compile without any #include statements.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 105 (10500-10599)”