LawlietYagami's blog

By LawlietYagami, history, 3 years ago, , 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! dp,
By LawlietYagami, history, 3 years ago, , I was going through this question which uses DP + Bitmask. But the editorial is too brief to understand and the author assumes everyone's familiarity with DP + Bitmask.

In my understanding,

for (int i = 1 ; i <= n ; i ++) {
for (int k = 1 ; k < 60 ; k ++) {
int x = (~fact[k]) & ((1 << 17) - 1);
for (int s = x ; ; s = (s - 1) & x) {
if (dp[i - 1][s] + abs(a[i] - k) < dp[i][s | fact[k]]){
dp[i][s | fact[k]] = dp[i-1][s] + abs(a[i]-k);
}
if (s == 0) break;
}
}
}

We iterate through all the possible values of k , ORing it every time which includes the prime factors in the answer. But why do we add abs(a[i] - k) in the dp, how does it help in identifying the answer? And once the dp matrix is set how do we retrieve the answer? Any help on the problem is appreciated. #dp,
By LawlietYagami, history, 3 years ago, , 