Page 1 of 2
Hi
Posted: Mon Jun 24, 2002 11:18 am
by 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
Posted: Mon Jun 24, 2002 11:51 am
by Kamp
Thx very much
Stupid mistake
O(N^2) solution ?!
Posted: Fri Jul 22, 2005 11:20 am
by 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.
10074 - WA
Posted: Tue Oct 25, 2005 6:30 pm
by 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!!
10074 take the land: need test case
Posted: Wed Jan 18, 2006 3:40 am
by zero_cool
can anybody give me some critical test cases for problem 10074? Thank you.
Posted: Thu Jan 19, 2006 12:23 pm
by emotional blind
Posted: Sun Jan 22, 2006 5:19 pm
by 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;
}
_____________________________________________________________
Posted: Thu Feb 02, 2006 9:49 am
by 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
Posted: Sat Mar 11, 2006 9:49 am
by 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
Posted: Sun Nov 19, 2006 8:07 am
by 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!
10074 - Take the Land
Posted: Thu Jul 28, 2011 10:44 am
by 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;
}
uva 10074: Take the Land WA
Posted: Sat Jun 21, 2014 9:38 pm
by 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;
}
Re: uva 10074: Take the Land WA
Posted: Mon Jun 23, 2014 11:24 pm
by 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.
Re: uva 10074: Take the Land WA
Posted: Wed Jun 25, 2014 2:15 am
by jishnu1
I have tried printing that way too but i still get a WA
Re: uva 10074: Take the Land WA
Posted: Wed Jun 25, 2014 7:26 pm
by brianfry713
Post your updated code.