Two weeks ago, I introduced the concept of memoization for dynamic programming, using as an example UVa 787. That problem involves operations on a sequence of integers, a one-dimensional structure. UVa 10755: Garbage Heap increases the problem complexity by organizing its integer data into a three-dimensional shape, a rectangular parallelepiped. Nevertheless, we can use memoization in a similar way to solve this problem.
Cuboids
First, a note on terminology. A rectangular parallelepiped is a three-dimensional figure formed by six rectangles. In other words, it’s like a cube, but its faces are rectangles rather than squares. Another term that can be used for this figure is rectangular cuboid, or simply cuboid. For simplicity, I’m going to use the term cuboid.
UVa 10755 involves cuboids. Here’s a summary of the problem statement:
You are given a cuboid that is divided into $A \times B \times C$ equal-sized pieces. Each piece is assigned an integer value. By removing zero or more slices of the original cuboid, construct a non-empty second cuboid. Your goal is to maximize the sum of the pieces in the second cuboid.
In the problem scenario, the cuboid is a block of garbage made up of smaller garbage blocks. For example, it might be $A$ blocks wide, $B$ blocks high, and $C$ blocks deep. The integer value for each block may be positive, negative, or zero. I’ll define the sum of a cuboid as the sum of the values of its constituent pieces.
Memoization (Again)
For UVa 787, the goal was to maximize the product of consecutive integers in a sequence. The key to finding an efficient solution to that problem is to store products as they are calculated, so they can be used to calculate subsequent products.
The same idea can be applied to UVa 10755, but in this case instead of storing the values of smaller products to calculate a larger product, we’re storing the sums of smaller cuboids to calculate the sum of a larger cuboid. That leads to a bit more complexity in the solution.
Solution Idea
Imagine that the input cuboid is dropped into a 3D coordinate system. Place one corner of the cuboid at the origin, $(0, 0, 0)$. (The problem statement uses $1$-based numbering, but I’m going to switch to standard $0$-based coordinates). Then the opposite corner will then be at $(A-1, B-1, C-1)$.
To calculate the sum of an arbitrary input cuboid from scratch, we would have to sum $A \times B \times C$ integers. Since the problem states that $1 \leq A, B, C \leq 20$, this is only $20^3=8000$ operations at most. However, the problem asks us to evaluate the sums of all possible sub-cuboids to find the maximum sum. Since there are $20^3$ possible starting positions (one corner) and $20^3$ possible ending positions (the opposite corner), that means evaluating $20^6 = 64$ million cuboids. That will take more time than we have, so we need an optimization.
Every cuboid larger than $1 \times 1 \times 1$ is made up of sub-cuboids. If cuboid $X$ is composed of sub-cuboids $Y$ and $Z$, then the sum of $X$ can be calculated by summing the sums of $Y$ and $Z$. So if we can build a memo table containing the sums of smaller cuboids, we can more efficiently calculate the sums of larger cuboids. Figuring out the details of how to do that is the key to solving this problem.
Solution Details
As described in the problem statement, the values for the input cuboid are listed in order from (in $0$-based coordinates) $(0, 0, 0)$ to $(0, 0, C-1)$, then $(0, 1, 0)$ to $(0, B-1, C-1)$, and finally $(1, 0, 0)$ to $(A-1, B-1, C-1)$. So as we read each input integer, we know exactly where we are in the cuboid. We can use that information as an index into a three-dimensional memo table.
What should we store in that memo table? The data we need for the solution consists of sums, so that sounds like a good choice. As we read the input values, we can add each value to an existing sum, forming a new sum to store in the memo table. Once the memo table is complete, we’ll have a database of sums that we can use to calculate cuboid totals.
How do we get the correct sums into the memo table, and how do we use them to process all of the sub-cuboids? That’s where things start to get tricky. To help me understand the details, I relied on an excellent C++ solution that Eugene Dorfman posted on GitHub. I would recommend having it open as you read the following sections.
Building the memo table
The memo table for this Dynamic Programming solution is a three-dimensional array of int. An array element at $(i, j, k)$ stores the sum of the cuboid whose starting corner is $(0, 0, 0)$ and whose opposite corner is at $(i, j, k)$. Because one corner is fixed at the origin, we only need $A \cdot B \cdot C$ integers for the whole table. In the next section, we’ll process these results to find the sum of sub-cuboids that do not start at the origin.
Three nested loops over $i$, $j$, and $k$ are sufficient to cover all possible opposite-corner coordinates. Inside the innermost loop ($k$), our goal is to calculate the sum at the current memo location, $(i, j, k)$. That requires five steps:
- Initialize a sum with the next input value. This is the additional cuboid piece that we’re adding in this iteration.
- For each of the three dimensions ($i$, $j$, and $k$), if there is a previous memo value, add it to the total. This is where we’re using the power of memoization. Retrieving a sum from the memo table is just one operation, which replaces potentially hundreds of additions.
- For each of the three pairs of dimensions — $i$ and $j$, $j$ and $k$, and $i$ and $k$ — if both dimensions in the pair had a previous memo value, subtract the corresponding memo value from the total. This is to avoid double-counting a sum.
- If all three dimensions had a previous memo value, add the corresponding memo value to the total, since it hasn’t yet been counted.
- Store the total in the memo table at position $(i, j, k)$.
It may not be obvious why the addition and subtraction in those steps needs to happen the way it does. To help see why it works, imagine a simple example: a $2 \times 2 \times 2$ cube, where each of the $8$ pieces has a value of $1$.
In the $(i, j, k)$ coordinate system, building the memo table for this example looks like counting from $0$ to $7$ in binary: $000, 001, 010, 011, 100, 101, 110, 111$. Here are the 8 steps:
- $(i, j, k) = (0, 0, 0)$: Read the first $1$ value. There are no previous memo values to use, so store $1$ at $(0, 0, 0)$. This is the sum of a cuboid that consists of a single piece with a value of $1$.
- $(i, j, k) = (0, 0, 1)$: Read the second $1$ value. There is a previous memo value for $k$ at $(0, 0, 0)$, so add it to the total: $1 + 1 = 2$. There are no other previous memo values, so store $2$ at $(0, 0, 1)$. This is the sum of a cuboid that consists of two pieces, each with a value of $1$.
- $(i, j, k) = (0, 1, 0)$: Read the third $1$ value. There is a previous memo value for $j$ at $(0, 0, 0)$, so add it to the total: $1 + 1 = 2$. There are no other previous memo values, so store $2$ at $(0, 1, 0)$.
- $(i, j, k) = (0, 1, 1)$: Read the fourth $1$ value. There are previous memo values for $j$ and $k$ at $(0, 0, 1)$ and $(0, 1, 0)$ respectively, so add those to the total: $1 + 2 + 2 = 5$. But since both $j$ and $k$ had previous values, we have double-counted. We need to subtract the memo value at $(i, j-1, k-1)$, which is $(0, 0, 0)$. The value there is $1$. Subtracting: $5 – 1 = 4$, so that’s the total we store at $(0, 1, 1)$. Notice that this is the correct sum for our example sub-cuboid with four pieces.
- $(1, 0, 0)$ through $(1, 1, 0)$ are calculated using a similar process, except that $i=1$.
- For $(1, 1, 1)$, we have our first example of double-counting and needing to add an additional value. Since there’s a previous memo value for $i$, $j$, and $k$, the sum consists of the incoming value plus the values at $(0, 1, 1)$, $(1, 0, 1)$, and $(1, 1, 0)$. That’s $1 + 4 + 4 + 4 = 13$. But that’s three double-counts, so we have to subtract the values from $(i-1, j-1, k)$, $(i, j-1, k-1)$, and $(i-1, j, k-1)$. That’s $13 – 2 – 2 – 2 = 7$. Finally, we have to add the value at $(i-1, j-1, k-1)$, which is $(0, 0, 0)$. That’s $7 + 1 = 8$, which is the sum of our example $2 \times 2 \times 2$ cube.
Hopefully those steps provide some insight into why the code logic is the way it is. The idea is that for each incoming cuboid piece, we can calculate a total using previously-calculated totals in the memo table. But as we’re doing that, we have to make sure we’re using sums only from the component pieces that are necessary to construct the new cuboid.
Using the memo table
Now that we have a memo table that gives us the sum of every cuboid that begins at $(0, 0, 0)$, we need a way to translate that information into sums for cuboids that begin at every other position between $(0, 0, 0)$ and $(A-1, B-1, C-1)$. For that, we’ll need six nested loops: three for the starting coordinates (the first corner, at $(i, j, k)$) and three for the ending coordinates (the opposite corner, at $(i1, j1, k1)$).
The five steps used for this final calculation are like a mirror image of the five steps used to build the memo table, in that they use subtraction where the previous steps used addition. Here’s how they work:
- Initialize a sum with the memo table value for $(i1, j1, k1)$. This gives us the sum for a cuboid that starts at the origin and ends at our target point.
- In general, our sum is now too high, since not all cuboids start at the origin. So for each of the three dimensions ($i$, $j$, and $k$), if there is a previous memo value, subtract it from the total. In other words, subtract the memoized area that lies outside of the target sub-cuboid region.
- As before, we have potentially double-counted the memo values. In this case, we may be double-subtracting. So for each of the three pairs of dimensions — $i$ and $j$, $j$ and $k$, and $i$ and $k$ — if both dimensions in the pair had a previous memo value, add the corresponding memo value back to the total.
- Also as before, if all three dimensions had a previous memo value, we need to subtract the corresponding memo value from the total, since it hasn’t yet been excluded.
- If the total is larger than any previous total found, store it for later.
When we’re done with all of the looping, the test case solution is the largest total that we found.
Thoughts on UVa 10755
When you look at the code for this problem, it seems quite simple: mainly just loops, array operations, conditionals, addition, and subtraction. The trick is to visualize the 3D shapes that need to be manipulated, and come up with an efficient way to store and retrieve information about them. As with many contest puzzles, the challenge is more in solving the puzzle on paper than in coding the solution.
(Image credit: James Bowe)