## 10755 - Garbage Heap

Moderator: Board moderators

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

### 10755 - Garbage Heap

I am getting WA in this problem.. http://acm.uva.es/p/v107/10755.html

- This looks to be a 3 dimensional maximum sum.
- I used long long as the result might exceed the integer limit.
- I get WA in 0.55 seconds which is significantly less then the lowest AC time(0.826) - may be I'm using the wrong algorithm.
- my algorithm takes O(n^4) time.

Is there anything wrong with my approach or am I missing something here.

Some hints will not be swept under the carpet.

Dyatlov
New poster
Posts: 6
Joined: Thu Sep 02, 2004 10:40 am
Location: Novosibirsk, Russia
Contact:
It is a 3 dimensional maximum sum.
I guess there is a mistake somewhere in your code.
And, to be honest, I do not know how to solve it in O(N^4) .
Semyon Dyatlov

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am
my algorithm to solve this problem is O(n^5) only. The approach is to reduce this to O(n^2) two dimensional problems and solve it in O(n^3).

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:
abishek wrote:my algorithm to solve this problem is O(n^5) only. The approach is to reduce this to O(n^2) two dimensional problems and solve it in O(n^3).
As well mine.

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

### AC..

Just got AC..
I made two small( well major ) mistakes.
- I overlooked the part about nonempty rectangular grid.
- I defined inf to be 1000000000 which is incorrect because the problem specifically tells us that the range is 2^31.

And my algo is O(n^5) too... I don't know why I wrote n^4 before.

Sample input for those who is getting WA..

1

1 1 1
-5

The output is -5 and not 0.

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
It might be simpler to move towards linear problem at O(N^4) since it's easier to put small code into big one than combine two average pieces. P.S: My IMHO
To be the best you must become the best!

galkovsk
New poster
Posts: 3
Joined: Fri Apr 08, 2005 9:15 am
Who can explain, why a stupid solution have WA:

choosing a lower left point, then, upper-right of our rectangular sub-parallelepiped.

Then, we counting a total sum of elements in it, and comparing it to the best achieved before.

My program gets WA in 0.000.

May be i don't understand the problem? Something about harmfull elements?

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
This should be TL, but not WA... Check your loops. Is it O(N^9)?
To be the best you must become the best!

galkovsk
New poster
Posts: 3
Joined: Fri Apr 08, 2005 9:15 am

procedure readint64(var x : int64); var t : longint; begin read(t); x := t; end;
MAX_POSSIBLE := int64(20*20*20*5)*int64(maxlongint);
for i := 0 to a-1 do
for j := 0 to b-1 do
for k := 0 to c-1 do

max2 := -MAX_POSSIBLE;
for x := 0 to a-1 do
for y := 0 to b-1 do
for z := 0 to c-1 do

for x2 := x to a-1 do
for y2 := y to b-1 do
for z2 := z to c-1 do begin

sum2 := 0;
for i := x to x2 do
for j := y to y2 do
for k := z to z2 do
sum2 := sum2 + d[i,j,k];

if sum2 > max2 then max2 := sum2;
end;
writeln(max2);

Of course, i'm read all tests, that are in input.

Who can explain, why THIS solution is wrong? (my fast solution also fails...)

Every array is int64. No place to overflow. Even reading is ok...

shitty_Mishka
New poster
Posts: 2
Joined: Sun Feb 02, 2003 9:56 pm
Location: Ukraine, Kyiv
Contact:
HINT: Each number does not exceed 2^31 by absolute value

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
when i wrote that inf =-2147483648

it showed a warning msg & made the value positve.

warning:
"unary minus operator applied to unsigned type, result still unsigned"

but when i modified it like inf=-2147483647-1
then it got AC.

though i used long long but why the value is becoming unsigned if i write like that?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
sunny wrote:when i wrote that inf =-2147483648

it showed a warning msg & made the value positve.

warning:
"unary minus operator applied to unsigned type, result still unsigned"

but when i modified it like inf=-2147483647-1
then it got AC.

though i used long long but why the value is becoming unsigned if i write like that?
That has to do with how the compiler parses the code. The parser treats it as 2147483648 and then applied unary minus to it. It looks at 2147483648 and figures out that it can't be a signed int (it exceeds 2^31-1), so it assumes that it is unsigned int, and then apply unary minus to it. But unary minus doesn't do what you would expect if the operand is unsigned, namely, it will still return a unsigned value. The fact that inf is declared to be long long, it doesn' matter, because the compiler will always look at right side of assignment first, implicitly determine type using only right hand side, then typecast it to match the type of left side if necessary.

On the other hand, -2147483647-1 is good, since the parser will first read 2147483647, then apply unary minus, then subtract 1 from it. In this case 2147483647 can be a signed int, so it assumes it is from the start.

The common fix to it is to append LL after the integer constant to make the value long long like this:

Code: Select all

``````long long inf = -2147483648LL;
``````

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

### Re: 10755 - Garbage Heap

If you are keep getting WA...
and dont't know why...
but really want to got AC...

then you may just change the "int" to "long long"...
and submit it...

Hope I am help

cutenemo
New poster
Posts: 7
Joined: Fri Dec 13, 2013 9:52 pm
Location: California

### Re: 10755 - Garbage Heap

Can someone help with providing additional test cases for this problem?

I'm getting WA

For the following input

Code: Select all

``````Sample Input
4
1 1 1
-5
2 2 2
-1 2 0 -3 -2 -1 1 5
2 3 3
21 -39 4 -39 4 -44 1 -32 -25 -35 2 17 6 10 2 -12 -22 35
1 2 2
-38 40 21 -34
``````
I get the following results

Code: Select all

``````-5
6
54
40
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10755 - Garbage Heap

Check input and AC output for thousands of problems on uDebug!