LawlietYagami's blog

By LawlietYagami, history, 8 years ago, In English

I was solving UVa 10755 — Garbage Heap abridged statement : Given values in 3D space, compute a 3D rectangle with maximum sum. The 2D version is given a matrix, find a submatrix with maximum sum which can be easily done by using 2D Kadane algorithm. But the 3D version of it seems quite difficult, I solved it using a rather different approach:

First storing the 3D rectangle sums starting from (0, 0, 0) to (i, j, k):

    for (int i=0;i<A;++i) for (int j=0;j<B;++j) for (int k=0;k<C;++k) {
      long long g; cin>>g;
      if (i>0) g+=m[i-1][j][k];
      if (j>0) g+=m[i][j-1][k];
      if (k>0) g+=m[i][j][k-1];
      if (i>0 && j>0) g-=m[i-1][j-1][k];
      if (j>0 && k>0) g-=m[i][j-1][k-1];
      if (i>0 && k>0) g-=m[i-1][j][k-1];
      if (i>0 && j>0 && k>0) g+=m[i-1][j-1][k-1];
      m[i][j][k]=g;
    }

Then, iterating over all the values in the array and updating max:

for (int i=0;i<A;++i) for (int j=0;j<B;++j) for (int k=0;k<C;++k) 
    for (int i1=i;i1<A;++i1) for (int j1=j;j1<B;++j1) for (int k1=k;k1<C;++k1)  {
      long long s = m[i1][j1][k1];
      if (i>0) s-=m[i-1][j1][k1];
      if (j>0) s-=m[i1][j-1][k1];
      if (k>0) s-=m[i1][j1][k-1];
      if (i>0 && j>0) s+=m[i-1][j-1][k1];
      if (j>0 && k>0) s+=m[i1][j-1][k-1];
      if (i>0 && k>0) s+=m[i-1][j1][k-1];
      if (i>0 && j>0 && k>0) s-=m[i-1][j-1][k-1];
      if (s>max_sum) max_sum = s;
    }

max_sum will be the answer, but the time complexity is O(n6) which I believe could be reduced by first applying 2D Kadane over the 2D space and 1D kadane for the remaining dimension, but I'm not sure on how to do that, if anyone's solved this problem, could you hint me on the right direction Thanks!

  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know what you mean by "I believe could be reduced by first applying 2D Kadane over the 2D space and 1D kadane for the remaining dimension" ,but you can reduce the complexity to O(n^5) by specifying a window (x_low,x_high) , (y_low,y_high) then use the normal kadane over z where the value of a particular z is the sum of all numbers in the rectangle (x_low,y_low,z) , (x_high,y_high,z)

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Here is my AC solution — works in 0.01 secs on uVA : you can fix 2-dimensions and apply kadane's over 3rd to reduce complexity to n^5.