10755 - Garbage Heap

[sohel]

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]

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

[abishek]

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]

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]

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]

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

[galkovsk]

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?

Please! Explain...

[Destination Goa]

This should be TL, but not WA... Check your loops. Is it O(N^9)?

[galkovsk]

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

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]

HINT: Each number does not exceed 2^31 by absolute value

[sunny]

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]

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]

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]

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]

http://www.uvatoolkit.com/problemssolve.php