108  Maximum Sum
Moderator: Board moderators

 New poster
 Posts: 3
 Joined: Thu Mar 22, 2007 6:21 am
 Location: Bangladesh
presentation error in Maximum Sum108
Dear all,
I was facing this problem many days ago. I was getting presentation error in 108 (Maximum Sum). I was printing the output without any space and new line.
I also got a reply stating
"not including space is ok, but why don't you print new lines. In every problem, there is at least one new line after every case of output".
I am very happy to get the reply. But from the very begiening I too know that in every problem there should be a new line after every case of output. This is
indeed very true if there are many cases of output. But what if there should be only one case of input and output.
Let's have a look to the input and the output of this problem.
Sample Input
4
0 2 7 0 9 2 6 2
4 1 4 1 1
8 0 2
Sample Output
15
The question is whether there should be provition of taking inputs before end of file i.e. there will be many cases of input or there will be only one case of input. if there is only one case of input then there will be only one case of output and how to print that output. I printed the output straight forward without space and new lines considering there will be just one case of input and output. Considering just one case of input and output I also tried with new lines and space later if I am not wrong. Well, it is more acceptable that there will be only one case of input as the problem states :
"Input and Output
The input consists of an array of integers. The input begins with a single positive integer N on a line by itself indicating the size of the square two dimensional array. This is followed by integers separated by whitespace (newlines and spaces). These integers make up the array in rowmajor order (i.e., all numbers on the first row, lefttoright, then all numbers on the second row, lefttoright, etc.). N may be as large as 100. The numbers in the array will be in the range [127, 127].
The output is the sum of the maximal subrectangle"
"The input consists of an array of integers" by this statement I think there should be only one array i.e. only one case of input.
Moreover, I just got presentation error instead of Wrong Answer. And if there is only one case of input, naturally there will be only one output for the input which I printed straight. My question is why I got presentation error in this problem. Can there be any other form of printing the output if there should be only
one output.
I am trying to solve this problem again after a long time. So,if anyone has knowledge about this please help.
Regards,
Fauhat
I was facing this problem many days ago. I was getting presentation error in 108 (Maximum Sum). I was printing the output without any space and new line.
I also got a reply stating
"not including space is ok, but why don't you print new lines. In every problem, there is at least one new line after every case of output".
I am very happy to get the reply. But from the very begiening I too know that in every problem there should be a new line after every case of output. This is
indeed very true if there are many cases of output. But what if there should be only one case of input and output.
Let's have a look to the input and the output of this problem.
Sample Input
4
0 2 7 0 9 2 6 2
4 1 4 1 1
8 0 2
Sample Output
15
The question is whether there should be provition of taking inputs before end of file i.e. there will be many cases of input or there will be only one case of input. if there is only one case of input then there will be only one case of output and how to print that output. I printed the output straight forward without space and new lines considering there will be just one case of input and output. Considering just one case of input and output I also tried with new lines and space later if I am not wrong. Well, it is more acceptable that there will be only one case of input as the problem states :
"Input and Output
The input consists of an array of integers. The input begins with a single positive integer N on a line by itself indicating the size of the square two dimensional array. This is followed by integers separated by whitespace (newlines and spaces). These integers make up the array in rowmajor order (i.e., all numbers on the first row, lefttoright, then all numbers on the second row, lefttoright, etc.). N may be as large as 100. The numbers in the array will be in the range [127, 127].
The output is the sum of the maximal subrectangle"
"The input consists of an array of integers" by this statement I think there should be only one array i.e. only one case of input.
Moreover, I just got presentation error instead of Wrong Answer. And if there is only one case of input, naturally there will be only one output for the input which I printed straight. My question is why I got presentation error in this problem. Can there be any other form of printing the output if there should be only
one output.
I am trying to solve this problem again after a long time. So,if anyone has knowledge about this please help.
Regards,
Fauhat
*fauhat A.K. panni*

 New poster
 Posts: 3
 Joined: Thu Mar 22, 2007 6:21 am
 Location: Bangladesh
108problem again
Dear All,
In my previous post I already mentioned that I was facing trouble with problem 108 (Maximum Sum). A long time ago I was getting presentation error in
this problem. To know detail about this please read my previous post "presentation error in Maximum Sum108". Now, after quite a long time I intended to
solve the problem again. I just submiited the previous code out of Inquisitiveness. But this time it is not presentation error I got. If I am not wrong I got Wrong Answer with the same code I got presentation error.
Please help.
In my previous post I already mentioned that I was facing trouble with problem 108 (Maximum Sum). A long time ago I was getting presentation error in
this problem. To know detail about this please read my previous post "presentation error in Maximum Sum108". Now, after quite a long time I intended to
solve the problem again. I just submiited the previous code out of Inquisitiveness. But this time it is not presentation error I got. If I am not wrong I got Wrong Answer with the same code I got presentation error.
Please help.
*fauhat A.K. panni*
Re: 108problem again
Perhaps it'd have been a better idea if you had made your query in the other post so that everyone can view the code and make comments.
WA in 108
/*What is the problem in this solution of problem 108......plz help...*/
#include<stdio.h>
int i,j,p,q,n,ar[101][101],ar1[101][101];
int sum,max=999999999;
int main ()
{
int s;
while(scanf("%d",&n) != EOF){
for(i=0;i<n;i++)
{
s=0;
for(j=0;j<n;j++)
{
scanf("%d",&ar[j]);
}
}
sum=0;
for(i=0;i<n;i++)
{
sum=sum+ar[0];
ar1[0]=sum;
}
sum=0;
for(i=1;i<n;i++)
{
sum=sum+ar[0];
ar1[0]=sum;
}
for(i=1;i<n;i++)
{
for(j=1;j<n;j++)
{
ar1[j]=ar[j]+ar1[j1]ar1[i1][j1]+ar1[i1][j]ar1[i1][j1]+ar1[i1][j1];
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
for(p=i;p<n;p++)
{
for(q=j;q<n;q++)
{
sum=0;
if (i >0 && j> 0)
sum=ar1[p][q]ar1[i1][q]ar1[p][j1]+ar1[i1][j1];
else
{
if(i==0 && j==0)
sum=ar1[p][q];
if(i==0 && j !=0)
{
sum=ar1[p][q]ar1[p][j1];
}
if(j==0 && i != 0)
{
sum=ar1[p][q]ar1[i1][q];
}
}
if(sum>max)
{
max=sum;
}
}
}
}
}
printf("%d",max);
}
return 0;
}
#include<stdio.h>
int i,j,p,q,n,ar[101][101],ar1[101][101];
int sum,max=999999999;
int main ()
{
int s;
while(scanf("%d",&n) != EOF){
for(i=0;i<n;i++)
{
s=0;
for(j=0;j<n;j++)
{
scanf("%d",&ar[j]);
}
}
sum=0;
for(i=0;i<n;i++)
{
sum=sum+ar[0];
ar1[0]=sum;
}
sum=0;
for(i=1;i<n;i++)
{
sum=sum+ar[0];
ar1[0]=sum;
}
for(i=1;i<n;i++)
{
for(j=1;j<n;j++)
{
ar1[j]=ar[j]+ar1[j1]ar1[i1][j1]+ar1[i1][j]ar1[i1][j1]+ar1[i1][j1];
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
for(p=i;p<n;p++)
{
for(q=j;q<n;q++)
{
sum=0;
if (i >0 && j> 0)
sum=ar1[p][q]ar1[i1][q]ar1[p][j1]+ar1[i1][j1];
else
{
if(i==0 && j==0)
sum=ar1[p][q];
if(i==0 && j !=0)
{
sum=ar1[p][q]ar1[p][j1];
}
if(j==0 && i != 0)
{
sum=ar1[p][q]ar1[i1][q];
}
}
if(sum>max)
{
max=sum;
}
}
}
}
}
printf("%d",max);
}
return 0;
}
Re: 108, am I on wrong way ?
Hi everybody!
I tried out with this not more efficient algorithm [ O(n^4) ],perhaps can run on time, but I got WA!, someone could give me a hand?
Thanks in advance for your answers!
I tried out with this not more efficient algorithm [ O(n^4) ],perhaps can run on time, but I got WA!, someone could give me a hand?
Code: Select all
done!
Last edited by Javo on Thu Jan 15, 2009 4:41 am, edited 1 time in total.
Re: 108, am I on wrong way ?
You should terminate the output line with a newline character ("\n" or std::endl)Javo wrote:cout<<FindMax();
You can use LONG_MIN constant defined in limits.h to initialize a variable with the most negative value representable by a 'long' type.Javo wrote:long maxSum=1270000,sum;
Re: 108, am I on wrong way ?
Thanks my friend! I should be more concentrated!
108  slow or waiting code?
Hi to everybody, I did the following code for the problem 108:
I tried it with my computer and takes about a half o second solving a 15x15 matrix, however the judge says that it's too slow, I want to know if my code is really slow, or it is waiting a inputcode when the judge is waiting an answer. I also want to know the sample size used by the judge, and the resources the judge has to run the programs.
Thank you.
Code: Select all
#include <iostream>
using namespace std;
int datos[100][100],cantidadLados,maximoActual;
struct Precalculo
{
int valor;
int x1;
int y1;
int x2;
int y2;
Precalculo *siguiente;
};
Precalculo *cabeza;
void agregarPrecalculo(Precalculo*);
bool hallarValorPrecalculado(Precalculo*,int&);
void liberarMemoria();
int hallarMaximo(int,int,int,int);
int main()
{
int maximo,sumatoria,cantidadElementosMatriz,x,y,i,nuevoDato;
bool soloPositivos,soloNegativos;
while(cin>>cantidadLados)
{
x=y=sumatoria=0;
soloNegativos=soloPositivos=true;
cantidadElementosMatriz = cantidadLados*cantidadLados;
for (i=0;i<cantidadElementosMatriz;i++)
{
cin>>nuevoDato;
datos[y][x] = nuevoDato;
x++;
if (x >= cantidadLados)
{
x=0;
y++;
}
if (i==0) maximo = maximoActual = datos[0][0];
if (nuevoDato > 0)
{
soloNegativos=false;
sumatoria+=nuevoDato;
}
else if (nuevoDato <= 0)
{
if (nuevoDato < 0)
soloPositivos = false;
if (nuevoDato > maximo) maximo = nuevoDato;
}
}
if (soloPositivos)
cout <<sumatoria<<endl;
else if (soloNegativos)
cout <<maximo<<endl;
else
{
cout <<hallarMaximo(0,0,0,0)<<endl;
liberarMemoria();
}
}
return EXIT_SUCCESS;
}
void agregarPrecalculo(Precalculo *nuevoPrecalculo)
{
nuevoPrecalculo>siguiente = cabeza;
cabeza = nuevoPrecalculo;
}
bool hallarValorPrecalculado(Precalculo *referenciaPrecalculo, int &respuesta)
{
bool valorDevuelto = false;
Precalculo *nodoActual = cabeza;
while (nodoActual!=NULL)
{
if (referenciaPrecalculo>x1 == nodoActual>x1 &&
referenciaPrecalculo>y1 == nodoActual>y1 &&
referenciaPrecalculo>x2 == nodoActual>x2 &&
referenciaPrecalculo>y2 == nodoActual>y2)
{
respuesta = nodoActual>valor;
valorDevuelto = true;
break;
}
nodoActual=nodoActual>siguiente;
}
return valorDevuelto;
}
void liberarMemoria()
{
Precalculo *nodoActual = cabeza, *nodoSiguiente;
while (nodoActual != NULL)
{
nodoSiguiente = nodoActual>siguiente;
delete nodoActual;
nodoActual = nodoSiguiente;
}
cabeza = NULL;
}
int hallarMaximo(int x1,int y1,int x2,int y2)
{
if (x1 >= cantidadLados  x2 >= cantidadLados  y1 >= cantidadLados  y2 >= cantidadLados) return datos[0][0];
int valorPrecalculado, &referenciaValorPrecalculado = valorPrecalculado,
sumatoriaSubMatriz = 0,
x,y,
conDer,conAba,soloDer,soloAba,conAmbos;
;
Precalculo *precalculoReferencia = new Precalculo;
precalculoReferencia>x1 = x1;
precalculoReferencia>y1 = y1;
precalculoReferencia>x2 = x2;
precalculoReferencia>y2 = y2;
if (hallarValorPrecalculado(precalculoReferencia,referenciaValorPrecalculado))
{
delete precalculoReferencia;
return valorPrecalculado;
}
for (y=y1;y<=y2;y++) for (x=x1;x<=x2;x++) sumatoriaSubMatriz += datos[y][x];
if (sumatoriaSubMatriz > maximoActual) maximoActual = sumatoriaSubMatriz;
conDer = hallarMaximo(x1,y1,x2+1,y2);
conAba = hallarMaximo(x1,y1,x2,y2+1);
soloDer = hallarMaximo(x1+1,y1,x2+1,y2);
soloAba = hallarMaximo(x1,y1+1,x2,y2+1);
conAmbos = hallarMaximo(x1,y1,x2+1,y2+1);
if (conDer > maximoActual) maximoActual = conDer;
if (conAba > maximoActual) maximoActual = conAba;
if (soloDer > maximoActual) maximoActual = soloDer;
if (soloAba > maximoActual) maximoActual = soloAba;
if (conAmbos > maximoActual) maximoActual = conAmbos;
precalculoReferencia>valor = maximoActual;
agregarPrecalculo(precalculoReferencia);
return maximoActual;
}
Thank you.
Last edited by camilop25 on Sat Mar 07, 2009 12:13 am, edited 1 time in total.
Re: 108  slow or waiting code?
You should try a 100x100 matrix. The input description clearly says "N may be as large as 100", so it's very likely that it's about that big in the judge's test.I tried it with my computer and takes about a half o second solving a 15x15 matrix
Re: 108  slow or waiting code?
I solved several problems in the uva, and many times it says the maximiun value, but it's clear that this value is not tried by the judge due to the excesive processing effort, read the problem and note that a 15x15 matrix requires a lot of processing, at least two million of comparisons, because the program has to compare each submatrix in a whole matrix, and select the biggest sum.mf wrote:You should try a 100x100 matrix. The input description clearly says "N may be as large as 100", so it's very likely that it's about that big in the judge's test.I tried it with my computer and takes about a half o second solving a 15x15 matrix
An example of this is the 3n+1 problem, if you choose a excesive large numer, such as 999 999 (1 less than the maximiun value) , any accepted code (as mine) must take several hours.
Re: 108  slow or waiting code?
Your algorithm is very inefficient, that's why it takes so long even on small matrices. I think it's complexity is about O(n^8)!
There's a very straightforward O(n^4) solution, and it's good enough to get accepted.
And then there's an even better O(n^3) algorithm.
There's a very straightforward O(n^4) solution, and it's good enough to get accepted.
And then there's an even better O(n^3) algorithm.
My accepted code for that problem takes only about a second to check all 1000000 numbers. And it's a very simple code.An example of this is the 3n+1 problem, if you choose a excesive large numer, such as 999 999 (1 less than the maximiun value) , any accepted code (as mine) must take several hours.
Re: 108  slow or waiting code?
When you use dynamic programming, the order is less important, because the storage of precalculated data helps to avoid repeated calculations, for that I use a linked list, I also tried it but avoiding consulting the linked list, the program takes several minutes and about 500 mbytes of ram, for the same matrix consulting the linked list, the answer is instant, for that reason sometimes orders about a O(n^n) is more efficient than a O(n) if the first one saves the calculated data (that is repeated several times) and then just visit them.mf wrote:Your algorithm is very inefficient, that's why it takes so long even on small matrices. I think it's complexity is about O(n^8)!
There's a very straightforward O(n^4) solution, and it's good enough to get accepted.
And then there's an even better O(n^3) algorithm.
My accepted code for that problem takes only about a second to check all 1000000 numbers. And it's a very simple code.An example of this is the 3n+1 problem, if you choose a excesive large numer, such as 999 999 (1 less than the maximiun value) , any accepted code (as mine) must take several hours.
For the above reason, I thought some people will advise me to improve the precalculate data system, such as implementing an AVL tree or something like that, if you know a better algorithm of a lower order, please say how it is.
Re: 108  slow or waiting code?
You don't need dynamic programming in this problem. Brute force works very well here, and needs very little memory.
But speaking of DP, you should never use linked list for memo tables in DP. Use hash tables, binary search trees (such as STL's std::map), or simple arrays if possible. Linked list with m elements needs O(m) time to search for an element, but arrays, hash tables and BSTs do it a lot faster  in O(1) and O(log m) time.
For example, your algorithm's complexity is O(n^8) because you have O(n^4) states in your DP, and for each state you do an O(n^4) search in linked list and O(1) additional work to compute answer. If you replace linked list with std::map, its complexity would drop to O(n^4 log n). That's already quite fast, but probably wouldn't get accepted because of its huge memory requirements.
But speaking of DP, you should never use linked list for memo tables in DP. Use hash tables, binary search trees (such as STL's std::map), or simple arrays if possible. Linked list with m elements needs O(m) time to search for an element, but arrays, hash tables and BSTs do it a lot faster  in O(1) and O(log m) time.
For example, your algorithm's complexity is O(n^8) because you have O(n^4) states in your DP, and for each state you do an O(n^4) search in linked list and O(1) additional work to compute answer. If you replace linked list with std::map, its complexity would drop to O(n^4 log n). That's already quite fast, but probably wouldn't get accepted because of its huge memory requirements.
Without memoization your program's complexity is exponential (I think it's Omega(5^n) or something like that, because you have 5 recursive calls), but once you added memoization (with a linked list), it became polynomial  of order O(n^8). See? Now, how can you claim such things:I also tried it but avoiding consulting the linked list, the program takes several minutes and about 500 mbytes of ram, for the same matrix consulting the linked list, the answer is instant,
That's simply now true (not for any large enough n, at least), and you've already observed that  an exponentialtime algorithm took minutes, but a polynomialtime algorithm takes only an instant...sometimes orders about a O(n^n) is more efficient than a O(n)
Re: 108 Maximum sum WA
I faced problem when I started this .But now I got accepted .
there is no need to use EOF and at last print only one '\n' and the output for all negetive numbers will be the lowest negetive number
i.e for
2
1 2
3 4
my accepted code give [1]
and for
3
12 13 4
2 3 5 6 4 6
gives 2
there is no need to use EOF and at last print only one '\n' and the output for all negetive numbers will be the lowest negetive number
i.e for
2
1 2
3 4
my accepted code give [1]
and for
3
12 13 4
2 3 5 6 4 6
gives 2
108Maximum Sum WA
Hi,
This is my code. I tried the test cases from the algorithmist site which seems to give me correct answer.But i am getting WA after submission:
Thanks in Advance.
This is my code. I tried the test cases from the algorithmist site which seems to give me correct answer.But i am getting WA after submission:
Code: Select all
#include<iostream>
using namespace std;
void Get_Max_Sum(int **array_2d,int row_sum[],int row2_sum[],int col_sum[],int col2_sum[],int size);
int main(void)
{
int **array_2d, i , j , size;
int max_sum(0);
int *row_sum,*col_sum,*row2_sum,*col2_sum;
while(cin >> size)
{
array_2d = new int*[size];
row_sum = new int[size];
col_sum = new int[size];
row2_sum = new int[size];
col2_sum = new int[size];
for(i = 0 ; i < size; ++i)
{
*(array_2d + i) = new int[size];
row_sum[i] = 0;
for(j = 0 ; j < size ; ++j)
{
cin >> *(*(array_2d + i) + j);
row_sum[i] += *(*(array_2d + i) + j);
}
row2_sum[i] = row_sum[i];
}
for(int i = 0 ; i < size ; ++i)
{
col_sum[i] = 0;
for(int j = 0 ; j < size ; ++j)
{
col_sum[i] += *(*(array_2d + j) + i);
}
col2_sum[i] = col_sum[i];
}
Get_Max_Sum(array_2d , row_sum ,row2_sum , col_sum , col2_sum, size);
delete(*array_2d);
delete(row_sum);
delete(col_sum);
delete(row2_sum);
delete(col2_sum);
}
return 0;
}
void Get_Max_Sum(int **array_2d,int row_sum[],int row2_sum[],int col_sum[],int col2_sum[],int size)
{
int row(0),col1(0),col2(0);
int real_sum(array_2d[0][0]);
int sum(0);
col2 = col1 + 1;
while(row < size && col1 < size  1)
{
if(col2 == 1)
sum = array_2d[row][col1] + array_2d[row][col2] ;
else
sum += array_2d[row][col2];
if(real_sum < sum)
real_sum = sum;
if(col2 < size  1)
{
++col2;
}
else
{
for(int i = row + 1 ; i < size ; ++i)
{
sum += row_sum[i];
if(real_sum < sum)
real_sum = sum;
}
++col1;
col2 = col1 + 1;
for(int i = 0 ; i < size ; ++i)
row_sum[i] = row2_sum[i]  array_2d[i][col1  1];
sum = 0;
}
if(col1 >= size  1)
{
++row;
col1 = 0;
col2 = col1 + 1;
for(int i = 0 ; i < size ; ++i)
row2_sum[i] = row_sum[i];
}
}
int col(0),row1(0),row2(0);
sum = 0;
row2 = row1 + 1;
while(col < size && row1 < size  1)
{
if(row2 == (row1 + 1) )
sum = array_2d[row1][col] + array_2d[row2][col] ;
else
sum += array_2d[row2][col];
if(real_sum < sum)
real_sum = sum;
if(row2 < size  1)
{
++row2;
}
else
{
for(int i = col + 1 ; i < size ; ++i)
{
sum += col2_sum[i];
if(real_sum < sum)
real_sum = sum;
}
++row1;
row2 = row1 + 1;
for(int i = 0 ; i < size ; ++i)
col2_sum[i] = col2_sum[i]  array_2d[row1  1][i];
sum = 0;
}
if(row1 >= size  1)
{
++col;
row1 = 0;
row2 = row1 + 1;
for(int i = 0 ; i < size ; ++i)
col2_sum[i] = col_sum[i];
}
}
cout << real_sum << endl;
}