108 - Maximum Sum

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

Moderator: Board moderators

Post Reply
jrydh
New poster
Posts: 1
Joined: Sun Nov 18, 2001 2:00 am
Location: Sweden
Contact:

Post by jrydh » Sun Nov 18, 2001 9:28 pm

Hello!

1) Why doesn't the judge find <limits>!?? It's standard.

2) With std::numeric_limits replaced by a large negative integer, it gives "Time Limit Exceeded". Why? The response is instant for me.

Code: Select all

// 108.cpp

#include <iostream>
#include <limits>
#include <exception>
#include <stdexcept>

template< class T >
class Matrix {
	public:
		Matrix( unsigned );
		~Matrix();

		T& operator() ( unsigned, unsigned );
		const T& operator() ( unsigned, unsigned ) const;
		
		T maximum( void ) const;

	private:
		T *data;
		unsigned size;
		
		T sum( unsigned, unsigned, unsigned, unsigned ) const;
};

template< class T >
Matrix< T >::Matrix( unsigned s )
	: size( s ), data( new T[ s * s ] )
{
	if( s == 0 )
		throw std::range_error( "bad matrix size" );
}

template< class T >
Matrix< T >::~Matrix() { delete [] data; }


template< class T >
inline T& Matrix< T >::operator() ( unsigned r, unsigned c ) {
	if( r >= size || c >= size )
		throw std::out_of_range( "invalid Matrix<T> subscript" );
	return data[ r * size + c ];
}

template< class T >
inline const T& Matrix< T >::operator() ( unsigned r, unsigned c ) const {
	if( r >= size || c >= size )
		throw std::out_of_range( "invalid Matrix<T> subscript" );
	return data[ r * size + c ];
}


template< class T >
T Matrix< T >::maximum( void ) const {
	T s, maximum = std::numeric_limits< T >::min();

	for( int y1 = 0; y1 < size; y1++ ) {
		for( int x1 = 0; x1 < size; x1++ ) {
			for( int y2 = 0; y2 < size; y2++ ) {
				for( int x2 = 0; x2 < size; x2++ ) {
					if( y2 >= y1 && x2 >= x1 ) {
						s = sum( x1, x2, y1, y2 );
						if( s > maximum )
							maximum = s;
					}
				}
			}
		}
	}

	return maximum;
}


template< class T >
T Matrix< T >::sum( unsigned x1, unsigned x2, unsigned y1, unsigned y2 ) const {
	T s = 0;

	for( int x = x1; x <= x2; x++ )
		for( int y = y1; y <= y2; y++ )
			s += operator() ( x, y );

	return s;
}


int main( void ) {
	int n;
	
	std::cin >> n;
	Matrix< int > matrix( n );
	
	try {
		for( int x = 0; x < n; x++ )
			for( int y = 0; y < n; y++ )
				std::cin >> matrix( x, y );

		std::cout << matrix.maximum() << std::endl;
	} catch( ... ) {
		std::cout << "Error!" << std::endl;
	}

	return 0;
}
/Johannes

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Mon Nov 19, 2001 11:28 am

I don't use C++, so I don't understand your code. However, I *think* I know why the limits library is not found. For my codes, if a library is needed, I usually put a ".h" after it like this:

#include <limits.h>

So I think the problem is that you need to add the ".h" extension for your program fto compile properly.

As for the TLE, try with a 100 * 100 test case and see if the response is still fast enough (From the way I understand your program, I think your time complexity is O(n^6), which is too slow for this problem).

Wedson
New poster
Posts: 3
Joined: Sun Nov 25, 2001 2:00 am
Location: Brazil

Post by Wedson » Sun Nov 25, 2001 8:51 pm

The #include is OK. Appending ".h" to the header filename is a C convention, not C++. The C++ header that defines numeric_limits is <limits>, if someone wants to include C's <limits.h> in C++ should include <climits>.

User avatar
Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

Why do I get Wrong Answer?

Post by Ming Han » Mon Jun 10, 2002 6:08 am

I got WA from the online judge.

Please take a look at my code.

[cpp]// Maximum Sum
// Done by Teh Ming Han

#include <stdio.h>

int main(){
int x1,y1,x2,y2,n,c,max=0;
int sum[100][100], work[100][100]={0};

scanf("%d",&n);
for (x1=1;x1<=n;x1++)
for (y1=1;y1<=n;y1++)
scanf("%d",&sum[x1][y1]); //read data

for (x1=1;x1<=n;x1++)
for (y1=1;y1<=n;y1++)
for (x2=1;x2<=x1;x2++)
for (y2=1;y2<=y1;y2++)
work[x1][y1] += sum[x2][y2];

for (x1=1;x1<=n;x1++)
for (y1=1;y1<=n;y1++)
for (x2=x1;x2<=n;x2++)
for (y2=y1;y2<=n;y2++){
c = work[x2][y2] - work[x1-1][y2] - work[x2][y1-1] + work[x1-1][y1-1];
if (c>max) max=c;
}

printf("%d",max);
return 0;
}[/cpp]

Is there anything wrong?
Thanks You

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Mon Jun 10, 2002 10:15 am

LOL! jrydh, I hope you realize that you have an O(n^6) algorithm there, and that n can get as large as 100. No wonder you time out :-)

User avatar
Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

ACM 108

Post by Ming Han » Mon Jun 10, 2002 10:26 am

I got Wrong Answer, not time out. I thought it is O(n^4), not O(n^6)??

My algo:

AxxxBxxxxCxxxxx
DxxxExxxxFxxxxx
xxxxxxxxxxxxxxx
GxxxHxxxxJxxxxx
xxxxxxxxxxxxxxx

To calculate area of EFHJ,
I calcaulate area of ACGJ - ACDF - ABGH + ABDF = ans
if (max<ans) max=ans

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Mon Jun 10, 2002 12:21 pm

Ming Han: "jrydh" is a name, which means I addressed the other guy, not you.

Your own mistake might be that you index the arrays from [1][1] to [n][n], but declare them as size [100][100], so you grab data out of bounds, which is a bad bad technique in general and in particular with 2-dimensional arrays.

skylander
New poster
Posts: 13
Joined: Mon Jun 10, 2002 3:24 pm
Contact:

Post by skylander » Mon Jun 10, 2002 3:34 pm

there is an O(n^3) algorithmn for finding the maximum sum....can anybody explain how it works?

i remembered someone saying that it is related to the largest subsequence problem

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Mon Jun 10, 2002 6:43 pm

I can explain how I got accepted for this. Given something like

abcd
efgh
ijkl
mnop

consider all rectangles starting with a in the top left, and compute them in this order (hope this looks ok):

a,ab,abc,abcd,

a, ab, abc, abcd
e ef efg efgh

a, ab
e ef
i ij

etc, now at each stage you keep partial sums in an array, and so to get
a
e
i
you use the partial sum
a
e
and just add the i, and so on for the whole row.

This is fairly simple to implement and I believe it is O(n^4). I'm sure that by keeping more partial sums you could probably reduce this to something better though.......

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

O(n^3) algorithm

Post by arnsfelt » Mon Jun 10, 2002 8:35 pm

To find an O(n^3) algorithm, first find an O(n) algorithm for the one dimentsional case.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Mon Jun 10, 2002 10:49 pm

A history of the problem and the one-dimensional case of this problem are also discussed in "Programming Pearls" of Jon Bentley, just in case anybody's interested. I believe it's chapter 8 or 9...

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

Prob 108

Post by taj79 » Tue Jun 25, 2002 7:29 pm

My prog is unable to work.Could u plz help me out.
Let me explain my method:
if the input is
0 9 -4 -1
-2 2 1 8
-7 -6 -4 0
0 2 1 -2
Let us take element of iTH row and jTh column.
first it tries to check row i
then it checks all rctangles containing that element of row i and the elemnts of row i &(i+1) then i & (i+1)&(i+2) then ..till nTH row is reached

this procedure is done for all elements.


#include<stdio.h>
#include<stdlib.h>
#define MAX 100

int sumcol(int A[][MAX],int i,int p,int q);
main()
{ int sum,temp_sum,*u,z,i,j,q,p,t,s,n;
int A[MAX][MAX];

scanf("%d",&n);/* dimension of square matrix */
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
scanf("%d",&A[j]);
}
for(i=1;i<=n;i++)
{ printf("\n");
for(j=1;j<=n;j++)
printf(" %d",A[j]);
}

sum = A[1][1];

for(i=1;i<=n;i++)
for(j=1;j<=n;j++) /* This 2 loops considers all the elements */
{printf("\n\n %d %d",i,j);

p=i;
while(p<= n)
{printf("\n Inside while");

if(p == i)
{printf("\np= %d p==i\n",p);
temp_sum = A[j];
if(sum < temp_sum)
sum = temp_sum;
for(q=j+1;q<=n;q++)
{ temp_sum += A[p][q];
if(sum < temp_sum)
sum = temp_sum;
}
printf("\n Max Sum for p = %d is %d\n",p,sum);
++p;
continue;/* Check if this takes back to while IT WORKS*/
}/* END of p==i */

printf("\np= %d p>i\n",p);
u = (int *)malloc(n-j+1 *sizeof(int) );
t=0;
for(q=j;q<=n;q++)
{++t;
*(u + t)= sumcol(A,i,p,q);
printf(" q= %d sumcol = %d\n",q,*(u + t) );
}
z=*(u+1);
if(z>sum)
sum = z;
for( s=2;s<=t;s++)
{ z += *(u+ s );
if(z>sum)
sum = z;
}
// printf("\np= %d",p);
printf("\n Max Sum for p = %d is %d\n",p,sum);
++p;

}/* END of while(p<= n) */
}/* END of FOR */
printf("The largest sum is %d \n",sum);
}

int sumcol(int A[][MAX],int i,int p,int q)
{
int t,ans =0;
printf("\n Inside sumcol()\n");
for(t=i;t<=p;t++)
{ printf(" %d",A[t][q]);
ans += A[t][q]; }
printf("\n ans = %d\n",ans);
return(ans);
}

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Wed Jun 26, 2002 8:36 am

What does the judge answer?
What is your runtime complexity?
Could you please use the bbtags to format the code?

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

Post by taj79 » Wed Jun 26, 2002 7:28 pm

my program doesn't for the given example in the computer itself.

After running for sometime it gives

Segmentation fault

Please help

i couldn't understand what do u mean by bbtags

did u mean to say that i should bolden the code using .

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN » Wed Jun 26, 2002 7:33 pm

Stefan Pochmann means that before you post codes here, press the *C* button or *C++* button above the text-field so as to give an indented version of your codes.

It's better to do so since the "plain-texted" codes are difficult to read, let alone to debug.

Post Reply

Return to “Volume 1 (100-199)”