- Problem Statement.
- A
**main()**with the examples compiled in. - A skeleton that compiles with
**main.cpp**. -
**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.

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

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