10074 - Take the Land

[cyfra]

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]

Thx very much

Stupid mistake

[Sedefcho]

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.

Thanks in advance.

[Yaron Wittenstein]

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[0][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]

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

[emotional blind]

try this

Code: Select all

1 1
0
1 1
1

[zero_cool]

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]=0;
for (j=0;j<=b;j++)
arr[0][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]

your code

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
buy

[zero_cool]

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]

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!

[minhquankq]

I'm get WA in problem Take the Land....
i use O(n^2)... test ok, but i still get WA... please help me!...

here my code:

Code: Select all

#include <stdio.h>

int t[111][111];
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]

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[101][101], B[101][101], 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;

}

[brianfry713]

Don't print a blank line at the start of the output.
Always print a newline char at the end of the last line.

[jishnu1]

I have tried printing that way too but i still get a WA

[brianfry713]

Post your updated code.