10502  Counting Rectangles
Moderator: Board moderators

 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
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
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.
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.
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.......
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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
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)
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)

 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.
My code took .119s.

 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:
it worked for all cases that i tested on udebug.
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 += kj1;
for( k = i+1; k <= n && board[k][j] == '1'; k++ );
fimLinha = k;
t += ki1;
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;
}

 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!