10667 - Largest Block

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

10667 - Largest Block

Post by htl »

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? :roll:

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim »

There is an O(n^3) algorithm to solve such problem. It is similar to that of problem 108. Take a look on threads regarding problem 108 :wink:

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

hmm

Post by Andrey Mokhov »

Hi!

Let's go on - there is O(n^2) algo. :P

Bye.
Andrey.

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

Post by Faizur »

Hi Mokhov,
Can u pls explain the O(n^2)algo a little or give a reference ???
Thanx in advance
Regards
_________________________________
:) :lol: :D

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

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 :P 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 left-to-right 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?

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl »

Uh...Sorry for interrupting your discussion.. But could someone give some critical input? I think that it shouldn't be hard to get AC.

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

Post by Faizur »

Thanx misof for ur help. I solved the problem with ur algo in 0.083 s
Regards
______________________________
:) :lol: :D Faizur

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

I applied your code as stated above, but getting WA.

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=r1-1;i<r2;i++) for(j=c1-1;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[i-1][j]+1;			
		}		

		for(i=0;i<n;i++)
		{
			for(j=1;j<n;j++) if(a[i][j]==0 && h[i][j]<=h[i][j-1]) l[i][j]=l[i][j-1]+1;
		}		

		for(i=0;i<n;i++)
		{
			for(j=n-2;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;
}
Or can you give some critical in out?
"Everything should be made simple, but not always simpler"

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

:lol: :lol:

Accepted using O(n^3) algorithm. But, prev. algo was WA. What am I missing above?
Anupam
"Everything should be made simple, but not always simpler"

LPH
New poster
Posts: 34
Joined: Mon Nov 17, 2003 10:41 am

Post by LPH »

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.
LPH [acronym]
= Let Program Heal us
-- New Uncyclopedian Dictionary, Minmei Publishing Co.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 »

Please check my I/O!!!
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
Output:

Code: Select all

30
380
50
125
375
180
96
All are correct?

Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

Post by Spykaj »

Correct.

lena
New poster
Posts: 28
Joined: Mon Mar 05, 2007 5:44 pm

Post by lena »

how to deal L[x][y] in linear time.
L[x+1][y] = 0 iff H[x+1][y]>H[x][y]
L[x][y]+1 iff H[x+1][y] == H[x][y]
=? iff H[x+1][y] < H[x][y]

the third condition, I do not know how to deal with it. maybe my formula is wrong ,anyone can give me some tips?
Thanks in advance

Post Reply

Return to “Volume 106 (10600-10699)”