TCO 2017, Round 1A, 500-Pointer (CheeseSlicing)

James S. Plank

Fri Apr 7 14:59:06 EDT 2017

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: April, 2017
Competitors who opened the problem: 802
Competitors who submitted a solution: 593
Number of correct solutions: 506
Accuracy (percentage correct vs those who opened): 63.1%
Average Correct Time: 22 minutes, 28 seconds.

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)

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)

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 <string>
#include <vector>
#include <list>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class CheeseSlicing {
  public:
    int totalArea(int A, int B, int C, int S);
    vector < vector < vector <int> > >Cache;
};

int CheeseSlicing::totalArea(int A, int B, int C, int S)
{
  int i, j, best;
  vector <int> 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;
}