Page 1 of 16

Posted: Sun Nov 18, 2001 9:28 pm
by jrydh

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 {
		Matrix( unsigned );

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

		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;

Posted: Mon Nov 19, 2001 11:28 am
by junjieliang
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).

Posted: Sun Nov 25, 2001 8:51 pm
by Wedson
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>.

Why do I get Wrong Answer?

Posted: Mon Jun 10, 2002 6:08 am
by Ming Han
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};

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;

return 0;

Is there anything wrong?
Thanks You

Posted: Mon Jun 10, 2002 10:15 am
by Stefan Pochmann
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 :-)

ACM 108

Posted: Mon Jun 10, 2002 10:26 am
by Ming Han
I got Wrong Answer, not time out. I thought it is O(n^4), not O(n^6)??

My algo:


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

Posted: Mon Jun 10, 2002 12:21 pm
by Stefan Pochmann
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.

Posted: Mon Jun 10, 2002 3:34 pm
by skylander
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

Posted: Mon Jun 10, 2002 6:43 pm
by Caesum
I can explain how I got accepted for this. Given something like


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


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
you use the partial sum
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.......

O(n^3) algorithm

Posted: Mon Jun 10, 2002 8:35 pm
by arnsfelt
To find an O(n^3) algorithm, first find an O(n) algorithm for the one dimentsional case.

Posted: Mon Jun 10, 2002 10:49 pm
by Stefan Pochmann
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...

Prob 108

Posted: Tue Jun 25, 2002 7:29 pm
by taj79
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.

#define MAX 100

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

scanf("%d",&n);/* dimension of square matrix */
{ printf("\n");
printf(" %d",A[j]);

sum = A[1][1];

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

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;
{ temp_sum += A[p][q];
if(sum < temp_sum)
sum = temp_sum;
printf("\n Max Sum for p = %d is %d\n",p,sum);
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) );
*(u + t)= sumcol(A,i,p,q);
printf(" q= %d sumcol = %d\n",q,*(u + t) );
sum = z;
for( s=2;s<=t;s++)
{ z += *(u+ s );
sum = z;
// printf("\np= %d",p);
printf("\n Max Sum for p = %d is %d\n",p,sum);

}/* 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");
{ printf(" %d",A[t][q]);
ans += A[t][q]; }
printf("\n ans = %d\n",ans);

Posted: Wed Jun 26, 2002 8:36 am
by Stefan Pochmann
What does the judge answer?
What is your runtime complexity?
Could you please use the bbtags to format the code?

Posted: Wed Jun 26, 2002 7:28 pm
by taj79
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 .

Posted: Wed Jun 26, 2002 7:33 pm
by 10153EN
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.