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

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:

Let's look at example 2, where A=B=C=5 and S = 2. And let's look at the first call: Let's look at the first recursive call: 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 {
    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) {
    for (i = 0; i < Cache.size(); i++) {
      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. */

  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;