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

Fauhat(AUST)
New poster
Posts: 3
Joined: Thu Mar 22, 2007 6:21 am
Location: Bangladesh

presentation error in Maximum Sum-108

Post by Fauhat(AUST) » Tue Sep 23, 2008 3:12 pm

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 white-space (newlines and spaces). These integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on the second row, left-to-right, 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 sub-rectangle"


"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*

Fauhat(AUST)
New poster
Posts: 3
Joined: Thu Mar 22, 2007 6:21 am
Location: Bangladesh

108-problem again

Post by Fauhat(AUST) » Fri Sep 26, 2008 7:24 pm

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 Sum-108". 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*

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 108-problem again

Post by sohel » Sun Sep 28, 2008 9:05 am

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.

shafin5
New poster
Posts: 1
Joined: Sun Nov 02, 2008 12:55 pm

WA in 108

Post by shafin5 » Sun Nov 02, 2008 1:13 pm

/*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[j-1]-ar1[i-1][j-1]+ar1[i-1][j]-ar1[i-1][j-1]+ar1[i-1][j-1];
}
}

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[i-1][q]-ar1[p][j-1]+ar1[i-1][j-1];
else
{
if(i==0 && j==0)
sum=ar1[p][q];
if(i==0 && j !=0)
{
sum=ar1[p][q]-ar1[p][j-1];
}
if(j==0 && i != 0)
{
sum=ar1[p][q]-ar1[i-1][q];
}
}
if(sum>max)
{
max=sum;
}
}
}
}
}

printf("%d",max);
}
return 0;
}

Javo
New poster
Posts: 3
Joined: Thu Jan 10, 2008 10:36 pm
Location: Mexico

Re: 108, am I on wrong way ?

Post by Javo » Wed Jan 14, 2009 5:12 am

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?

Code: Select all

done!
Thanks in advance for your answers!
Last edited by Javo on Thu Jan 15, 2009 4:41 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 108, am I on wrong way ?

Post by mf » Wed Jan 14, 2009 5:52 am

Javo wrote:cout<<FindMax();
You should terminate the output line with a newline character ("\n" or std::endl)
Javo wrote:long maxSum=-1270000,sum;
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
New poster
Posts: 3
Joined: Thu Jan 10, 2008 10:36 pm
Location: Mexico

Re: 108, am I on wrong way ?

Post by Javo » Thu Jan 15, 2009 4:40 am

Thanks my friend! I should be more concentrated!

camilop25
New poster
Posts: 3
Joined: Fri Mar 06, 2009 4:04 am

108 - slow or waiting code?

Post by camilop25 » Fri Mar 06, 2009 4:21 am

Hi to everybody, I did the following code for the problem 108:

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;
}
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.
Last edited by camilop25 on Sat Mar 07, 2009 12:13 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 108 - slow or waiting code?

Post by mf » Fri Mar 06, 2009 5:16 am

I tried it with my computer and takes about a half o second solving a 15x15 matrix
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.

camilop25
New poster
Posts: 3
Joined: Fri Mar 06, 2009 4:04 am

Re: 108 - slow or waiting code?

Post by camilop25 » Fri Mar 06, 2009 5:03 pm

mf wrote:
I tried it with my computer and takes about a half o second solving a 15x15 matrix
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 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.

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.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 108 - slow or waiting code?

Post by mf » Fri Mar 06, 2009 6:37 pm

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.
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.
My accepted code for that problem takes only about a second to check all 1000000 numbers. And it's a very simple code.

camilop25
New poster
Posts: 3
Joined: Fri Mar 06, 2009 4:04 am

Re: 108 - slow or waiting code?

Post by camilop25 » Sat Mar 07, 2009 12:05 am

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.
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.
My accepted code for that problem takes only about a second to check all 1000000 numbers. And it's a very simple code.
When you use dynamic programming, the order is less important, because the storage of pre-calculated 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.

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.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 108 - slow or waiting code?

Post by mf » Sat Mar 07, 2009 2:38 am

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.


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,
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:
sometimes orders about a O(n^n) is more efficient than a O(n)
That's simply now true (not for any large enough n, at least), and you've already observed that - an exponential-time algorithm took minutes, but a polynomial-time algorithm takes only an instant...

anjanpstu
New poster
Posts: 7
Joined: Thu Apr 07, 2011 8:40 am

Re: 108 Maximum sum WA

Post by anjanpstu » Sun May 01, 2011 10:45 pm

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

aaa111
New poster
Posts: 14
Joined: Sat Nov 21, 2009 2:55 pm

108-Maximum Sum WA

Post by aaa111 » Sun Jun 17, 2012 12:59 am

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:

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;
}
Thanks in Advance.

Post Reply

Return to “Volume 1 (100-199)”