10074 - Take the Land

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

Moderator: Board moderators

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

Hi

Post by cyfra » Mon Jun 24, 2002 11:18 am

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 :wink:

Kamp
New poster
Posts: 18
Joined: Tue Mar 05, 2002 2:00 am
Location: Poland (3-city)
Contact:

Post by Kamp » Mon Jun 24, 2002 11:51 am

Thx very much :D

Stupid mistake :roll:

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

O(N^2) solution ?!

Post by Sedefcho » Fri Jul 22, 2005 11:20 am

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
New poster
Posts: 18
Joined: Wed Jul 21, 2004 5:09 pm
Contact:

10074 - WA

Post by Yaron Wittenstein » Tue Oct 25, 2005 6:30 pm

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
New poster
Posts: 27
Joined: Fri Sep 02, 2005 6:33 am

10074 take the land: need test case

Post by zero_cool » Wed Jan 18, 2006 3:40 am

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

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Thu Jan 19, 2006 12:23 pm

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

Post by zero_cool » Sun Jan 22, 2006 5:19 pm

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;
}
_____________________________________________________________

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Thu Feb 02, 2006 9:49 am

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
New poster
Posts: 27
Joined: Fri Sep 02, 2005 6:33 am

Post by zero_cool » Sat Mar 11, 2006 9:49 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

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Sun Nov 19, 2006 8:07 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

Post by minhquankq » Thu Jul 28, 2011 10:44 am

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
New poster
Posts: 4
Joined: Sat Jun 21, 2014 1:24 am

uva 10074: Take the Land WA

Post by jishnu1 » Sat Jun 21, 2014 9:38 pm

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;

}

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

Post by brianfry713 » Mon Jun 23, 2014 11:24 pm

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

Post by jishnu1 » Wed Jun 25, 2014 2:15 am

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

Re: uva 10074: Take the Land WA

Post by brianfry713 » Wed Jun 25, 2014 7:26 pm

Post your updated code.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 100 (10000-10099)”