## 10502 - Counting Rectangles

Moderator: Board moderators

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

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

### test cases .... right/wrong

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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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
i used a O(n^6) way and TLEed

New poster
Posts: 1
Joined: Thu Apr 26, 2007 3:51 am
Contact:
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
New poster
Posts: 10
Joined: Fri Sep 16, 2011 6:36 am

### Re: 10502 - Counting Rectangles

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

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

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