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

aybek
New poster
Posts: 19
Joined: Fri Jul 19, 2013 10:25 am
Contact:

Re: uva 10074: Take the Land WA

Post by aybek » Fri Jun 27, 2014 8:06 pm

Correct your output code to printf("%d\n", maxSubRectz);
and you have errors in your code.

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

Re: uva 10074: Take the Land WA

Post by jishnu1 » Sat Jun 28, 2014 9:23 pm

@aybek
Sorry for the late reply.

I have tried printing that way too but i still receive a WA. I have updated the code. It compiles without errors (g++ compiler) and runs well on several test cases i provide on my computer. So if there are any errors pls be kind and notify them.
Thankx

aybek
New poster
Posts: 19
Joined: Fri Jul 19, 2013 10:25 am
Contact:

Re: uva 10074: Take the Land WA

Post by aybek » Tue Jul 01, 2014 1:55 pm

jishnu1, I don't know what test case will break your solution, I can give you my code of solution,
and you might generate outputs from it and compare them with your solution outs.

Code: Select all

#include <iostream>
using namespace std;

int M, N;
int a[ 101 ][ 101 ];
int s[ 101 ][ 101 ];

void count_s() {
	int i, j;
	s[1][1] = a[1][1];

	for ( i = 2; i <= M; ++i )
		s[i][1] = s[i-1][1] + a[i][1];

	for ( j = 2; j <= N; ++j )
		s[1][j] = s[1][j-1] + a[1][j];

	for ( i = 2; i <= M; ++i )
		for ( j = 2; j <= N; ++j )
			s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j];
}

int main() {
	int i, j, x1, y1, x2, y2, max_area;
	for ( ;; ) {

		cin >> M >> N;
		if ( !M && !N ) break;

		max_area = 0;
		for ( i = 1; i <= M; ++i )
			for ( j = 1; j <= N; ++j )
				cin >> a[i][j];

		count_s();

		for ( x1 = 1; x1 <= M; ++x1 )
		for ( y1 = 1; y1 <= N; ++y1 )
			for ( x2 = x1; x2 <= M; ++x2 )
			for ( y2 = y1; y2 <= N; ++y2 )
				if ( (s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]) == 0 ) {
					max_area = max( (x2-x1+1)*(y2-y1+1), max_area );
				}

		cout << max_area << endl;
	}

	return 0;
}

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 Jul 07, 2014 10:54 pm

jishnu1, change line 24 to:
if (i > 0) { A[j] += A[j] ; B[j] += B[i-1][j]; }
And line 30 to:
if (j > 0) { A[j] += A[j-1] ; B[j] += B[j-1]; }
And line 36 to:
if (i > 0 && j > 0) { A[j] = A[j] - A[i-1][j-1] ; B[j] = B[i][j] - B[i-1][j-1]; }
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 Jul 09, 2014 9:20 pm

@brianfry713
Thankx, I finally got Accepted :D , but i did not quite understand the logic behind this :-? , in a conditional statement like if isnt it true that u can put the assignment operations on one line if possible ?

if this is not the case isn't the judge supposed to report compilation error, and if my algorithm was coded the wrong way how was it able to pass several test cases?

My question is :

why:

Code: Select all

 if (i > 0) {A[i][j] += A[i - 1][j] ; B[i][j] += B[i-1][j];}
instead of this :

Code: Select all

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

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 » Thu Jul 10, 2014 5:19 pm

No those code blocks are not equivalent. C is flexible with whitespace, it doesn't matter if the statements are on one line or not.

Code: Select all

if(cond)
  statement1; statement2;
is the same as:

Code: Select all

if(cond)
  statement1;
statement2;
You could use a , instead of ; if you wanted to write them without braces.

Code: Select all

if(cond)
  statement1, statement2;
is the same as:

Code: Select all

if(cond) {
  statement1;
  statement2;
}
You should change your coding style with whitespace, as it makes it more clear.
Check input and AC output for thousands of problems on uDebug!

asrajmane193
New poster
Posts: 5
Joined: Tue May 26, 2015 9:55 am

Re: 10074 - Take the Land

Post by asrajmane193 » Fri Jul 03, 2015 3:39 pm

hello. i keep getting wrong answer. I tried many random testcases and compared my outputs with the ones on udebug. they are equal. my code is here - http://ideone.com/dOLTFy

I have applied 1D maximum sum on a matrix. For every window of rows I try to find the starting and ending column.

For finding the window of columns, I save the starting and ending column indices which give me the maximum sum on the temporary array.

This runs is O(n^3)

Post Reply

Return to “Volume 100 (10000-10099)”