10502 - Counting Rectangles

[cytmike]

thanks.
lemme read then=p

[uzurpatorul]

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

[Sedefcho]

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]

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

[Sedefcho]

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]

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

[toadstool]

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

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

My code took .119s.

[matheusdallrosa]

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]

That code won't compile without any #include statements.