## 10502 - Counting Rectangles

Moderator: Board moderators

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm

### 10502 - Counting Rectangles

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

### 10502 Any better approach?

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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Exist method which have time complexity O(N^3) - I think, that maybe O(N^2) average and O(N^3) in worst case ....
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
??? 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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I don't think that 2 loops are neccessary ... I use only one "while" loop ....

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Just 1 while-loop? How???

P.S. This is my 111th post!!! Yeah~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
consider:
3
3
111
101
111

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

### 10502 - Help me! How to count rectangles correctly?

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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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.
Last edited by sohel on Wed Dec 24, 2003 7:08 am, edited 2 times in total.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Can someone post some sample input and output? I've tried tons of cases..

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
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
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
hey, how can u solve that in 0.000 sec??

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org