10502 - Counting Rectangles

[oriol78]

why WA? can anybody help me plz?
[cpp]

#include <iostream>
#include <vector>
using namespace std;

vector<vector<char> > matrix(100,vector<char>(100));

long int count;

int calc3(int x, int x2, int y, int y2)
{
for(int i = x; i <= x2; i++)
{
count++;
if(matrix[y2] != '1')
return 0;
}
return 1;
}

int calc2(int tamY, int x, int x2, int y)
{
int sum = 0;
int fitaY;
for(fitaY = y; fitaY < tamY; fitaY++)
{
if(matrix[x][fitaY] != '1' || matrix[x2][fitaY] != '1')
break;
}
for(int j = y; j < fitaY; j++)
sum += calc3(x,x2,y,j);
return sum;
}

int calc(int tamX, int tamY, int x, int y)
{

int sum = 0;
int fitaX;
for(fitaX = x; fitaX < tamX; fitaX++)
{
if(matrix[fitaX][y] != '1')
break;
}
for(int i = x; i < fitaX; i++)
sum += calc2(tamY,x,i,y);
return sum;
}

int proces(int x, int y)
{
int sum = 0;
count = 0;
for(int i = 0; i < x; i++)
{
for(int j = 0; j < y; j++)
cin >> matrix[j];
}
for(int i2 = 0; i2 < x; i2++)
{
for(int j2 = 0; j2 < y; j2++)
{
if(matrix[i2][j2] == '1')
sum += calc(x,y,i2,j2);
}
}
//cout << count << endl;
return sum;
}

int main()
{
int x, y;
while(cin >> x >> y)
cout << proces(x,y) << endl;
return 0;
}
[/cpp]

[Observer]

I used an O(n^4) algorithm and got accepted.

However, is there a more efficient method (e.g. O(n^3)) to solve this problem?

Plz share with me! Thx in advance.

[Dominik Michniewski]

Exist method which have time complexity O(N^3) - I think, that maybe O(N^2) average and O(N^3) in worst case ....
Think about it:
when you scan matrix, what happens in every point (x,y) of matrix - what should you do and how can help you counting maximal height of rectangle in column x ?

Best regards
DM

[Observer]

??? I don't quite understand......

Can you explain more clearly plz?

P.S. I use 2 for-loops and 2 while-loops in my code. So the time complexity is clearly O(n^4)...
Best case --> n^2 since the 2 while-loops will not be executed.

[Dominik Michniewski]

I don't think that 2 loops are neccessary ... I use only one "while" loop ....

Best regards
DM

[Observer]

Just 1 while-loop? How???

P.S. This is my 111th post!!! Yeah~

[Dominik Michniewski]

it's spoiler .... so you must be careful

for each row r
for each column c
{
prepare row in heights (O(N))
t = c
while(heights[t] > 0) /* do counting O(1) */
}

is enough .....

Best regards
DM

[Caesum]

consider:
3
3
111
101
111

correct answer is 20

[medv]

How to count rectangles correctly?
One 1 - it's a rectangle. Tho adacent 1's is a rectangle.
And so on.

In

4
3
110
101
111
011

I counted 27 rectangles, but not 22

In

3
3
111
101
111

there are 20, but I counted 27.

Can smb tell me, how correctly to count rectangles?

[sohel]

One 1 - it's a rectangle. Tho adacent 1's is a rectangle.
And so on.

I am afraid thats not quite correct. Adjacent 1's do form a rectangle if the 1's make a rectangular shape. May be you have considered non-rectangular shape as rectangles and perhaps that's why you got more that the required one.

For the first cases you have mentioned, the 22 rectangles are:
1** *1* *** *** *** *** *** *** ***
*** *** 1** **1 *** *** *** *** ***
*** *** *** *** 1** *1* **1 *** ***
*** *** *** *** *** *** *** *1* **1

11* 1** *** *** *** *** *** *** ***
*** 1** 1** *** *** **1 *** *** ***
*** *** 1** 11* *11 **1 **1 *** *1*
*** *** *** *** *** *** **1 *11 *1*

1** *** *** ***
1** *** **1 ***
1** 111 **1 *11
*** *** **1 *11

Hope it helps.

[Observer]

Please note that the following are NOT rectangles:

1*1 *1* 111
1*1 1*1 1*1
*** *1* 111

P.S. With an O(n^4) algorithm, I managed to get Acc with 0.00.00x CPU time! Of course, later I applied a more efficient algorithm and got a much higher ranking.

[Larry]

Can someone post some sample input and output? I've tried tons of cases..

[miras]

try with... this...

100
100
1 1 1 1 1 ... 1 1 1
1 1 1 1 1 ... 1 1 1
.
.
.
1 1 1 1 1 ... 1 1 1
1 1 1 1 1 ... 1 1 1



or with...
1
1
1

[cytmike]

hey, how can u solve that in 0.000 sec??

[Observer]

An O(n^4) algorithm would certainly NOT give you 0.00.000 sec. runtime.

Here you'll need an O(n^2) DP algorithm, and you have to process the data while they are being read.

The idea is a bit like that of Q10593 Kites /Q10667 Largest Block. I suggest you read topics related to the two tasks first.