Page 1 of 16
Posted: 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

Posted: 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).

Posted: 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>.

### Why do I get Wrong Answer?

Posted: 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, work={0};

scanf("%d",&n);
for (x1=1;x1<=n;x1++)
for (y1=1;y1<=n;y1++)

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

Posted: 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 ### ACM 108

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

Posted: 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  to [n][n], but declare them as size , 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
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
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.......

### O(n^3) algorithm

Posted: 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.

Posted: 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...

### Prob 108

Posted: 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;

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

Posted: Wed Jun 26, 2002 8:36 am
Could you please use the bbtags to format the code?

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