10755  Garbage Heap
Moderator: Board moderators
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.
 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.
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.
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.

 Experienced poster
 Posts: 123
 Joined: Thu Feb 10, 2005 4:46 am
Who can explain, why a stupid solution have WA:
choosing a lower left point, then, upperright of our rectangular subparallelepiped.
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...
choosing a lower left point, then, upperright of our rectangular subparallelepiped.
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...

 Experienced poster
 Posts: 123
 Joined: Thu Feb 10, 2005 4:46 am
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 a1 do
for j := 0 to b1 do
for k := 0 to c1 do
readint64(d[i, j, k]);
max2 := MAX_POSSIBLE;
for x := 0 to a1 do
for y := 0 to b1 do
for z := 0 to c1 do
for x2 := x to a1 do
for y2 := y to b1 do
for z2 := z to c1 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...

 New poster
 Posts: 2
 Joined: Sun Feb 02, 2003 9:56 pm
 Location: Ukraine, Kyiv
 Contact:
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=21474836471
then it got AC.
though i used long long but why the value is becoming unsigned if i write like that?
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=21474836471
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^311), 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.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=21474836471
then it got AC.
though i used long long but why the value is becoming unsigned if i write like that?
On the other hand, 21474836471 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;
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
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
Re: 10755  Garbage Heap
Can someone help with providing additional test cases for this problem?
I'm getting WA
For the following input
I get the following results
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
Code: Select all
5
6
54
40

 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!