SRM 604, D2, 500-Pointer (PowerOfThreeEasy)

James S. Plank

• Problem Statement.
• A main() with the examples compiled in.
• A skeleton that compiles with main.cpp.
• tests.sh. MD5 hash: d70381773ec6e2f9a70eed36dcb738f1
• answers.txt. MD5 hash: 2285379487690949cb599295f1a20d0d

• Problem Given in Topcoder: January, 2014
• Competitors who opened the problem: 1302
• Competitors who submitted a solution: 975
• Number of correct solutions: 560
• Accuracy (percentage correct vs those who opened): 43.01%
• Average Correct Time: 23 minutes, 47 seconds.

In case Topcoder's Servers are Down

• You have designed a robot, which starts at point (0,0) on a two-dimensional coordinate grid.
• The robot can either go up or right.
• The robot will take Z steps, numbered 0 to (Z-1).
• At step i, the robot will go 3ⁱ units, either up or right.
• You are given an (x,y) point, where x and y are between 0 and 10⁹.
• Return "Possible" if it's possible for the robot to reach this point, and "Impossible" if it's not possible.

Examples

#          X          Y  Return Value
- ---------- ----------  ------------
0          1          3  "Possible": Right at step 0, up at step 1.
1          1          1  "Impossible"
2          3          0  "Impossible"
3          1          9  "Impossible"
4          3         10  "Possible"
5       1093       2187  "Possible"
6          0          0  "Possible"

Testing yourself

Hints

You can view this as a power set enumeration problem. Your set consists of the numbers { 1, 3, 9, 27, ..., 3^z }, 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."

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";
}

What's the faster solution?

It's in Solution-Elegant.cpp:

string PowerOfThreeEasy::ableToGet(int x, int y)
{
  while (x != 0 || y != 0) {
    if ((x % 3) + (y % 3) != 1) return "Impossible";
    x /= 3;
    y /= 3;
  }
  return "Possible";
}