SRM 604, D2, 500-Pointer (PowerOfThreeEasy)

James S. Plank

Thu Sep 15 15:51:35 EDT 2016
While there are more efficient ways of solving this problem, you can view it as a power set enumeration problem. Your set consists of the numbers { 1, 3, 9, 27, ..., 3z }, such that the sum of all of the numbers in the set equals x+y. These are all of the horizontal and vertical moves that the robot can make. If there is no set of this form whose sum equals x+y, then you can't solve the problem, and you return "Impossible" instantly.

Otherwise, once you determine this set, you enumerate its subsets. For each subset S, you add up the elements in S to see if you get x. If so, you know that the sum of the elements not in S equals y, and you can return "Possible."

If, after enumerating each subset, you don't get a "Possible" answer, then it's "Impossible."


So, let's break your answer into parts. The first part is calculating the set of numbers. In my code that was a vector of ints, which I called TheSet. To calculate TheSet, start with one, and keep generating successive powers of three. Add them to TheSet, so long as the sum of the elements of TheSet is less than x+y.

At the end of this process, either the sum of the elements of TheSet equals x+y, meaning that you can start your power set enumeration, or the sum is greater than x+y, meaning that you can return "Impossible."

Here's the code for this part (the whole solution is in Solution.cpp).

string PowerOfThreeEasy::ableToGet(int x, int y)
{
  vector <int> TheSet;  /* This will hold the elements of the set. */
  long long d, sum;
  int i, j;

  if (x == 0 && y == 0) return "Possible";

  /* First, calculate TheSet.  The elements here are successive powers 
     of three such that their sum equals x+y. */

  d = 1;
  sum = 0;

  do {
    TheSet.push_back(d);
    sum += d;
    d *= 3;
  } while (sum < x + y);
  
  /* When we get to this point, either sum > x+y, which means that 
     it's impossible, or sum = x+y, and we can move onto the enumeration. */

  if (sum != x + y) return "Impossible";

We now perform the power set enumeration, which follows the lecture notes on enumeration exactly. Each subset is held in the integer i, and element j is in subset i if the j-th bit of i is set.

For each subset, we add up the elements, and if they equal x, then the answer is "Possible." If we can't find an answer, then it is "Impossible."

Here is the remainder of the code:

  /* Do the power set enumeration.  For each subset of TheSet, add up the
     elements of the subset.  If they equal x, then it's "Possible" and
     you can return.  Otherwise, try the next subset. */

  for (i = 0; i < (1 << TheSet.size()); i++) {
    sum = 0;
    for (j = 0; j < TheSet.size(); j++) {
      if (i & (1 << j)) sum += TheSet[j];
    }
    if (sum == x) return "Possible";
  }

  /* If we couldn't find a subset, then return "Impossible". */

  return "Impossible";
}