10667  Largest Block
Moderator: Board moderators
10667  Largest Block
I believed that many people have solved such problems before and are familiar with this one. But I got WA on this one. Can somebody give some critical input? And I always use O(n^4) algorithm to solve problems like this. It seems to take too much time. Can someone share your faster algorithm?

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
hmm
Hi!
Let's go on  there is O(n^2) algo.
Bye.
Andrey.
Let's go on  there is O(n^2) algo.
Bye.
Andrey.
Let's get letters straight (and ignore the problem statement that uses them in a different, less common way).
N is the dimension of the board. The algorithm mentioned above is (most probably) O(N^2) in this N, not in the number of rectangles Let the number of rectangles be R.
I'm not sure about an O(N^2) algorithm in this case (when the matrix in the input is given in a "compressed" way as a union of rectangles). You probably could beat it to some O(R^2 log R) using sweeping, but this would be too complicated to write in a contest.
Let's start by actually filling the board with zeroes and ones by drawing all the rectangles. This takes time O(RN^2) and is the most expensive part of our algorithm.
We are left with a classical problem: finding the largest rectangle of zeroes in a matrix. This can be done in O(N^2).
We will use DP. One possibility: For each square compute the following three numbers:
H[x][y]  height  if I start at [x,y] and go upwards, how many 0 do I find before the first 1?
L[x][y]  left  how far to the left can I extend a rectangle with bottom right corner at [x,y] and height H[x][y]?
R[x][y]  right  the same in the opposite direction
You compute these values with growing x. For a fixed x first you compute H[x][y] for all y (this is trivial), then in one lefttoright pass you compute L[x][y] for all y and finally you compute R[x][y] in the opposite direction. This can also be done in a very simple way, but I don't want to give away everything at once
The solution is then max_{x,y} ( H[x][y] * ( L[x][y] + R[x][y] + 1 ) )
was I clear enough or should I be more specific?
N is the dimension of the board. The algorithm mentioned above is (most probably) O(N^2) in this N, not in the number of rectangles Let the number of rectangles be R.
I'm not sure about an O(N^2) algorithm in this case (when the matrix in the input is given in a "compressed" way as a union of rectangles). You probably could beat it to some O(R^2 log R) using sweeping, but this would be too complicated to write in a contest.
Let's start by actually filling the board with zeroes and ones by drawing all the rectangles. This takes time O(RN^2) and is the most expensive part of our algorithm.
We are left with a classical problem: finding the largest rectangle of zeroes in a matrix. This can be done in O(N^2).
We will use DP. One possibility: For each square compute the following three numbers:
H[x][y]  height  if I start at [x,y] and go upwards, how many 0 do I find before the first 1?
L[x][y]  left  how far to the left can I extend a rectangle with bottom right corner at [x,y] and height H[x][y]?
R[x][y]  right  the same in the opposite direction
You compute these values with growing x. For a fixed x first you compute H[x][y] for all y (this is trivial), then in one lefttoright pass you compute L[x][y] for all y and finally you compute R[x][y] in the opposite direction. This can also be done in a very simple way, but I don't want to give away everything at once
The solution is then max_{x,y} ( H[x][y] * ( L[x][y] + R[x][y] + 1 ) )
was I clear enough or should I be more specific?
I applied your code as stated above, but getting WA.
Here it is.
Please check whether there is a simole mistake.
Or can you give some critical in out?
Here it is.
Please check whether there is a simole mistake.
Code: Select all
#include<stdio.h>
#define N 120
main()
{
int cas,z,a[N][N],b,n,i,j,r1,r2,c1,c2,h[N][N],l[N][N],r[N][N],y,max;
freopen("in.txt","r",stdin);
scanf("%d",&cas);
for(z=0;z<cas;z++)
{
scanf("%d",&n);
for(i=0;i<n;i++) for(j=0;j<n;j++) a[i][j]=0;
scanf("%d",&b);
for(y=0;y<b;y++)
{
scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
for(i=r11;i<r2;i++) for(j=c11;j<c2;j++) a[i][j]=1;
}
for(i=0;i<n;i++) for(j=0;j<n;j++) h[i][j]=l[i][j]=r[i][j]=0;
for(i=0;i<n;i++) if(a[0][i]==0) h[0][i]=1;
for(i=1;i<n;i++)
{
for(j=0;j<n;j++) if(a[i][j]==0) h[i][j]=h[i1][j]+1;
}
for(i=0;i<n;i++)
{
for(j=1;j<n;j++) if(a[i][j]==0 && h[i][j]<=h[i][j1]) l[i][j]=l[i][j1]+1;
}
for(i=0;i<n;i++)
{
for(j=n2;j>=0;j) if(a[i][j]==0 && h[i][j]<=h[i][j+1]) r[i][j]=r[i][j+1]+1;
}
max=0;
for(i=0;i<n;i++) for(j=0;j<n;j++)
{
b=(l[i][j]+r[i][j]+1)*h[i][j];
if(b>max) max=b;
}
printf("%d\n",max);
}
return 0;
}
"Everything should be made simple, but not always simpler"
anupam:
think of this case: (the square marked by X is number 0)
********
*****1**
**1110**
**00001*
**00000*
*100000*
*000000*
*00000X*
********
the L[] of the square left of the X square is obiviously 0, but the L[] of the X square is 4, not 0+1.
think of this case: (the square marked by X is number 0)
********
*****1**
**1110**
**00001*
**00000*
*100000*
*000000*
*00000X*
********
the L[] of the square left of the X square is obiviously 0, but the L[] of the X square is 4, not 0+1.
LPH [acronym]
= Let Program Heal us
 New Uncyclopedian Dictionary, Minmei Publishing Co.
= Let Program Heal us
 New Uncyclopedian Dictionary, Minmei Publishing Co.

 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 pm
Please check my I/O!!!
Input:
Output:
All are correct?
Input:
Code: Select all
7
10
3
2 2 5 5
7 3 9 9
4 6 3 8
20
1
1 1 1 5
10
2
5 1 5 10
1 5 5 5
25
3
1 1 5 5
5 5 10 10
7 7 20 20
25
2
1 1 5 5
5 5 10 10
20
4
5 5 11 11
1 3 1 20
7 8 7 9
6 9 10 9
16
3
1 1 3 3
4 3 10 3
8 3 9 10
Code: Select all
30
380
50
125
375
180
96