10755 - Garbage Heap

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10755 - Garbage Heap

Post by sohel » Sat Oct 30, 2004 10:19 am

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. :wink:

Dyatlov
New poster
Posts: 6
Joined: Thu Sep 02, 2004 10:40 am
Location: Novosibirsk, Russia
Contact:

Post by Dyatlov » Sun Oct 31, 2004 4:12 am

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

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » Sun Oct 31, 2004 7:43 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:

Post by rotoZOOM » Sun Oct 31, 2004 8:02 am

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.

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

AC..

Post by sohel » Sun Oct 31, 2004 2:24 pm

Just got AC.. 8)
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

Post by Destination Goa » Tue Feb 15, 2005 7:02 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

Post by galkovsk » Fri Apr 08, 2005 9:26 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?

Please! Explain...

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Fri Apr 08, 2005 10:25 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

Post by galkovsk » Fri Apr 08, 2005 9:48 pm


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
New poster
Posts: 2
Joined: Sun Feb 02, 2003 9:56 pm
Location: Ukraine, Kyiv
Contact:

Post by shitty_Mishka » Sun Apr 10, 2005 9:41 pm

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

Post by sunny » Sun Sep 17, 2006 10:44 pm

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Oct 11, 2006 2:51 am

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

Post by suneast » Mon Jul 19, 2010 11:06 am

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 :wink:

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

Re: 10755 - Garbage Heap

Post by cutenemo » Mon Feb 10, 2014 7:19 pm

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

Post by brianfry713 » Mon Feb 10, 2014 10:47 pm

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

Post Reply

Return to “Volume 107 (10700-10799)”