Page 2 of 2
Posted: Tue Jun 29, 2004 2:11 pm
by cytmike
thanks.
lemme read then=p
test cases .... right/wrong
Posted: Tue Nov 09, 2004 12:34 pm
by 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
Posted: Tue Aug 16, 2005 6:59 pm
by 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.
Posted: Wed Aug 17, 2005 6:05 pm
by 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.......
Posted: Wed Aug 17, 2005 10:05 pm
by 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 ?
Posted: Mon Apr 02, 2007 10:13 am
by randomtea
i used a O(n^6) way and TLEed
Posted: Thu Apr 26, 2007 4:08 am
by 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)
Re: 10502 - Counting Rectangles
Posted: Sun Jul 28, 2013 1:00 am
by Muftee_Ruet
I used the same technique as the 836 - Largest Submatrix.
My code took .119s.
Re: 10502 - Counting Rectangles
Posted: Sun Jan 11, 2015 4:34 am
by 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.
Re: 10502 - Counting Rectangles
Posted: Tue Jan 13, 2015 3:01 am
by brianfry713
That code won't compile without any #include statements.