### James S. Plank

Fri Apr 7 14:59:06 EDT 2017
This is a pretty classic dynamic program, and with nearly all dynamic programs, the challenge lies in spotting the recursion. Here, you need to make an assumption. When you're solving it in Topcoder, you don't have time to prove the assumption, but it is very helpful for your programming. The assumption is this:

 You can solve this problem by solely making cuts of size S.

I'm not sure that I can convince you that this assumption is true, but it's the assumption I made, and it was very good at limiting the scope of my recursion. The recursion works as follows:

• Base case: If any size is less than S, then return 0, because the slice not a good slice.

• Otherwise, calculate the surface area of the slice (I sorted the three values to figure out which one was the shortest, so that I could calculate the surface area). This is our starting point for calculating the "best" value.

• Then, for each side, see if you can make a cut of size S that results in two good slices. Suppose the side is A. Then you'll make recursive calls to A = A-S and A=S. If the result of making the cut is better than the "best" value, update the "best" value.

• At the end, return the "best" value.
Let's look at example 2, where A=B=C=5 and S = 2. And let's look at the first call:
CS(A = 5, B = 5, C = 5). This is going to be the maximum of :
• 25 (the surface area).
• Cutting A: CS(A = 3, B = 5, C = 5) + CS(A = 2, B = 5, C = 5).
• Cutting B: CS(A = 5, B = 3, C = 5) + CS(A = 5, B = 2, C = 5).
• Cutting C: CS(A = 5, B = 5, C = 3) + CS(A = 5, B = 5, C = 2).
Let's look at the first recursive call:
CS(A = 3, B = 5, C = 5). This is going to be the maximum of :
• 25 (the surface area)
• Cutting B: CS(A = 3, B = 3, C = 5) + CS(A = 3, B = 2, C = 5).
• Cutting B: CS(A = 3, B = 5, C = 3) + CS(A = 3, B = 5, C = 2).
And so on and so on. You can memoize this by using a three-dimensional vector -- from the constraints, you'll note that the maximum size of this vector will be 100x100x100, which fits into Topcoder's time/space constraints very nicely.
My commented solution is below (in Solution.cpp):

 ```/* Topcoder TCO 2017, Q1A 500-Pointer - CheeseSlicing James S. Plank Fri Apr 7 16:05:47 EDT 2017 */ #include #include #include #include #include #include #include #include #include #include using namespace std; class CheeseSlicing { public: int totalArea(int A, int B, int C, int S); vector < vector < vector > >Cache; }; int CheeseSlicing::totalArea(int A, int B, int C, int S) { int i, j, best; vector Sorted; /* Initialize the cache if this is the very first call. */ if (Cache.size() == 0) { Cache.resize(A+1); for (i = 0; i < Cache.size(); i++) { Cache[i].resize(B+1); for (j = 0; j < Cache[i].size(); j++) Cache[i][j].resize(C+1, -1); } } /* Memoization. */ if (Cache[A][B][C] != -1) return Cache[A][B][C]; /* Sort the slices -- this makes it easier to find the "shortest" slice. */ Sorted.push_back(A); Sorted.push_back(B); Sorted.push_back(C); sort(Sorted.begin(), Sorted.end()); /* Base case: If the smallest side is less than S, then you have a bad slice -- return 0. It's up to you whether you want to put this answer into the cache. It's actually more efficient if you do, but it's still constant time if you dont, so I don't. */ if (Sorted[0] < S) return 0; /* Otherwise, first calculate the surface area if you make no cuts. */ best = Sorted[1] * Sorted[2]; /* Then, for each side, if slicing along that side yields two "good" pieces, go ahead and make the recursive call for each of these, and sum up the results. Use the maximum of these. */ if (A-S >= S) { i = totalArea(A-S, B, C, S) + totalArea(S, B, C, S); if (i > best) best = i; } if (B-S >= S) { i = totalArea(A, B-S, C, S) + totalArea(A, S, C, S); if (i > best) best = i; } if (C-S >= S) { i = totalArea(A, B, C-S, S) + totalArea(A, B, S, S); if (i > best) best = i; } Cache[A][B][C] = best; return best; } ```