## 10074 - Take the Land

Moderator: Board moderators

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

### Hi

Hi!

You have one very small mistake in your program....

Your algoritm is OK but you print "0" at the end of your output.....

because you don't have "Writeln" in your "if n<>0" command

Change it and you will have AC....

Don't worry and try not to make such stupid bugs again Good Luck Kamp
New poster
Posts: 18
Joined: Tue Mar 05, 2002 2:00 am
Location: Poland (3-city)
Contact:
Thx very much Stupid mistake Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### O(N^2) solution ?!

I have a solution to this problem which has time complexity
O(N^3) and memory complexity also O(N^3)
/ Let's assume N = M , this is not important /

I am wondering if there's an algorithm with time complexity
O(N^2) which solves this problem 10074.
The memory complexity is not so important for me right now.

Yaron Wittenstein
New poster
Posts: 18
Joined: Wed Jul 21, 2004 5:09 pm
Contact:

### 10074 - WA

Hi!!!!
I have no idea why i get WA!!
the algorithm I use goes like this:
every two points (r1, c1) and (r2, c2) define exactly one rectangle if and only if
r1 != r2 and c1 != c2 (its easy to figure this out)

In my program r1 < r2 and c1 < c2
now the scanning goes like this: I check all the possible rectangles.
This is by done by defining one point as constant and by changing the coordinates
of the other point and vice versa.

Checking whether the rectangle created by (r1, c1) and (r2, c2) is a valid one (i.e has no trees) takes O(c2 - c1) because answering to the question how many trees
are between (r2, c) and (r2, c) takes O(1) for c1 <= c <= c2 (see countTrees for that)
That my code:

Code: Select all

``````
#include <stdio.h>

#define  MAXSIZE  100

#define white      0
#define black !white

int a[MAXSIZE + 1][MAXSIZE];
int m, n;

void init()
{
int i;
for(i = 0; i < n; i++) {
a[i] = white;
}
}

void countTrees()
{
int i, j;

for(i = 1; i <= m; i++) {
for(j = 0; j < n; j++) {
a[i][j] += a[i - 1][j];
}
}
}

int treesNum(int r1, int r2, int c)
{
return (a[r2][c] - a[r1 - 1][c]);
}

int isValidRect(int r1, int c1, int r2, int c2)
{
for(; c2 >= c1; c2--) {
if (treesNum(r1, r2, c2) > 0) {
return 0; /* not a VALID rectangle */
}
}
return 1; /* a VALID rectangle */
}

/* r2 and c2 remain constant here */
int calcRect(int r2, int c2)
{
int r1, c1;
for(r1 = 1; r1 < r2; r1++) {
for(c1 = 0; c1 < c2; c1++) {
if (isValidRect(r1, c1, r2, c2)) { /* i.e no trees */
return (r2 - r1 + 1) * (c2 - c1 + 1);
}
}
}
return 0;
}

int solve()
{
int maxRect = 0;
int temp;
int r2, c2;

for(r2 = m; r2 > 1; r2--) {
for(c2 = n - 1; c2 > 0; c2--) {
/* if the maximum potential rectangle is smaller then
the maximum rectangle we currently have we finish  */
if (maxRect > (r2 * n)) {
return maxRect;
}

temp = calcRect(r2, c2);
if (maxRect < temp) {
maxRect = temp;
}
}
}
return maxRect;
}

int main()
{
int i, j;
while (scanf("%d%d", &m, &n) == 2) {
if ( (m == 0) && (n == 0) ) break;

init();
for(i = 1; i <= m; i++) {
for(j = 0; j < n; j++) {
scanf("%d", &a[i][j]);
}
}
countTrees();
printf("%d\n", solve());
}

return 0;
}
``````
Please try to help me here guys thanx!!

zero_cool
New poster
Posts: 27
Joined: Fri Sep 02, 2005 6:33 am

### 10074 take the land: need test case

can anybody give me some critical test cases for problem 10074? Thank you.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
try this

Code: Select all

``````1 1
0
1 1
1``````

zero_cool
New poster
Posts: 27
Joined: Fri Sep 02, 2005 6:33 am
I don't know what's wrong with my code but I kept getting WA. Could somebody give me critical test case or check my program?

_____________________________________________________________
#include <iostream>

using namespace std;

const int maxSize=101;
const int MIN=-999999;

int main() {
int a,b,tmp,max;
int arr[maxSize][maxSize];
int i,j,k,l;

cin >> a >> b;
while (a!=0||b!=0) {
for (i=1;i<=a;i++)
for (j=1;j<=b;j++) {
cin >> arr[j];
if (arr[j]==0)
arr[j]=1;
else
arr[j]=MIN;
}
for (i=0;i<=a;i++)
arr=0;
for (j=0;j<=b;j++)
arr[j]=0;

max=0;
for (i=1;i<=a;i++)
for (j=1;j<=b;j++)
arr[j]=arr[j]+arr[i-1][j]-arr[i-1][j-1]+arr[j-1];
for (i=1;i<=a;i++)
for (j=1;j<=b;j++)
for (k=1;k<=i;k++)
for (l=1;l<=j;l++) {
tmp=arr[j]-arr[k-1][j]+arr[k-1][l-1]-arr[l-1];
if (tmp>max)
max=tmp;
}
cout << max << endl;
cin >> a >> b;
}

return 0;
}
_____________________________________________________________

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
for (k=1;k<=i;k++)
for (l=1;l<=j;l++) {
but i think it should be

Code: Select all

``````for (k=i;k<=i;k++)
for (l=j;l<=j;l++) {
``````
try now
keep posting

zero_cool
New poster
Posts: 27
Joined: Fri Sep 02, 2005 6:33 am
I think it is impossible to change this code to

for (k=1;k<=i;k++)
for (l=1;l<=j;l++) {

for (k=i;k<=i;k++)
for (l=j;l<=j;l++) {

because it means deleting the last two for (l from j to j and k from i to i means nothing) and also if I change that code it will produce wrong answer

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am
let me suggest you something...
better have two arrays instead of one array, it will make it look simple.
instead of manipulating the data to -inf or 1 or 0, let them be as they are, find the sum of the rect using dp just as you did.

all i did was just checking whether the sum of that rect is zero or not.

Code: Select all

`````` for(i=1;i<=m;i++)
for(j=1;j<=n;j++) {
for(k=i;k<=m;k++)
for(l=j;l<=n;l++) {
if(!rect(i,j,k,l)) {
ans = (k-i+1)*(l-j+1);
best>?=ans;
}
}
}
``````
its simple.. best wishes!
fahim
#include <smile.h>

minhquankq
New poster
Posts: 1
Joined: Thu Jul 28, 2011 10:40 am

### 10074 - Take the Land

I'm get WA in problem Take the Land....

here my code:

Code: Select all

``````#include <stdio.h>

int t;
int m, n;

int Max(int a, int b) {return (a>b)?a:b;}

int main(){
int tam;
freopen("10074.ind", "r", stdin);
freopen("10074.out", "w", stdout);
while(1){
scanf("%d%d", &m, &n);
if(m==0 && n==0) return 0;

for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
scanf("%d", &tam);
if(i==0){
if(tam==1) t[i][j]=0;
else       t[i][j]=1;
}
else{
if(tam==1) t[i][j]=t[i-1][j];
else       t[i][j]=t[i-1][j]+1;
}
}
}

for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
printf("%d ", t[i][j]);
}
printf("\n");
}

int kq=0;

for(int i=0; i<m; i++){
int temp=0;
for(int j=0; j<n; j++){
if(i==0){
if(t[i][j]==1) temp++;
else {kq=Max(kq, temp); temp=0;}
}
else{
if(t[i][j]!=t[i-1][j]) temp++;
else {kq=Max(kq, temp); temp=0;}
}
}
kq=Max(kq, temp);
}

for(int i=0; i<m-1; i++){
for(int j=i+1; j<m; j++){
int temp=0;
for(int k=0; k<n; k++){
if((j-i)==(t[j][k]-t[i][k])) temp+=j-i+1;
else {kq=Max(kq, temp); temp=0;}
}
//kq=Max(kq, temp);
}
//kq=Max(kq, temp);
}

printf("%d\n", kq);

}
return 0;
}
``````

jishnu1
New poster
Posts: 4
Joined: Sat Jun 21, 2014 1:24 am

### uva 10074: Take the Land WA

I have tried many test cases they all seem to come up with the right answer but when i submit to the judge i get a WA

The idea is this: I have maintained two matrices A and B one for the number of zeroes and other for the number of ones.
i.e A[j] gives the number of zeores in the sub matrix from (0,0) to (1,1) similar action is taken by B for ones. Then I run through all combinations of sub matrices in O(n^4) and see which of them have no ones in them, among these matrices I take the one which has the highest number of zeroes. I cannot see why I am getting the WA verdict.

The code:

Code: Select all

``````
#include <algorithm>
#include <cstdio>
using namespace std;

int n,m,x, A, B, maxSubRectz, subRectz, subRecto;

int main() {
while (1){

scanf("%d %d", &n,&m);
if (n == 0 && m == 0) return 0;

for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
scanf("%d", &x);

if (x==0){A[i][j]=1; B[i][j]=0;}
else{A[i][j]=0; B[i][j]=1;}

if (i > 0) A[i][j] += A[i - 1][j] ; B[i][j] += B[i-1][j];

if (j > 0) A[i][j] += A[i][j-1] ; B[i][j] += B[i][j-1];

if (i > 0 && j > 0) A[i][j] = A[i][j] - A[i-1][j-1] ; B[i][j] = B[i][j] - B[i-1][j-1];

}

maxSubRectz = 0;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
for (int k = i; k < n; k++) for (int l = j; l < m; l++) {
subRectz = A[k][l]; subRecto = B[k][l];
if (i > 0) {subRectz -= A[i - 1][l]; subRecto -= B[i - 1][l];}
if (j > 0) {subRectz -= A[k][j - 1]; subRecto -= B[k][j-1];}
if (i > 0 && j > 0) {subRectz += A[i - 1][j - 1]; subRecto += B[i - 1][j - 1]; }

if (subRecto == 0){ maxSubRectz = max(maxSubRectz, subRectz);} }

printf("%d\n", maxSubRectz);

}
return 0;

}

``````
Last edited by jishnu1 on Sat Jun 28, 2014 9:18 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: uva 10074: Take the Land WA

Don't print a blank line at the start of the output.
Always print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

jishnu1
New poster
Posts: 4
Joined: Sat Jun 21, 2014 1:24 am

### Re: uva 10074: Take the Land WA

I have tried printing that way too but i still get a WA brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA