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(n⁶) 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!

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.

Hi all, this is my first post so please be polite :-)

It's been around 3 weeks I'm actively solving problems. I'm able to solve around 5 problems a day (Level C and D) ( I spend around 1-2 hours for every problem [is it too slow? Eventually will it get better?] ). Most of the time I'm able to come up with rough idea/brute force to solve the question then nearly every time I miss some edge cases then again come back, make changes and submit, then get AC. I was wondering how I could possibly get better, since I'm able to only solve A and B problems in contest.

And also, I was wondering how many problems are others able to solve in one day? How do I improve the rate of solving problems?