Hex Dyslexia
Contest: MemSQL Start[c]UP 3.0 - Round 2 (onsite finalists)
Difficulty rating: 3300
Tags: bitmasks, brute force, dp, graphs

Copying large hexadecimal (base 16) strings by hand can be error prone, but that doesn't stop people from doing it. You've discovered a bug in the code that was likely caused by someone making a mistake when copying such a string. You suspect that whoever copied the string did not change any of the digits in the string, nor the length of the string, but may have permuted the digits arbitrarily. For example, if the original string was 0abc they may have changed it to a0cb or 0bca, but not abc or 0abb.

Unfortunately you don't have access to the original string nor the copied string, but you do know the length of the strings and their numerical absolute difference. You will be given this difference as a hexadecimal string S, which has been zero-extended to be equal in length to the original and copied strings. Determine the smallest possible numerical value of the original string.

Input format:
Input will contain a hexadecimal string S consisting only of digits 0 to 9 and lowercase English letters from a to f, with length at most 14. At least one of the characters is non-zero.

Output format:
If it is not possible, print "NO" (without quotes).

Otherwise, print the lowercase hexadecimal string corresponding to the smallest possible numerical value, including any necessary leading zeros for the length to be correct.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
The numerical value of a hexadecimal string is computed by multiplying each digit by successive powers of 16, starting with the rightmost digit, which is multiplied by 160. Hexadecimal digits representing values greater than 9 are represented by letters: a = 10, b = 11, c = 12, d = 13, e = 14, f = 15.

For example, the numerical value of 0f1e is 0·163 + 15·162 + 1·161 + 14·160 = 3870, the numerical value of 00f1 is 0·163 + 0·162 + 15·161 + 1·160 = 241, and the numerical value of 100f is 1·163 + 0·162 + 0·161 + 15·160 = 4111. Since 3870 + 241 = 4111 and 00f1 is a permutation of 100f, 00f1 is a valid answer to the second test case.

Example input:
f1e

Example output:
NO

Example input:
0f1e

Example output:
00f1

Editorial:
First, observe that for a solution to exist, the sum of the digits in the input must be divisible by 15. This is because of the Casting out Nines rule, but applied in base 16. Furthermore, the sum of digits, when divided by 15, tells us how many carries must be performed when adding the answer to the input. We can try every possible set of positions for the carries, of which there are at most $${ \binom { 13 } { 6 } } = 1 7 1 6$$ ways. Once the carries are fixed, for each position we know the exact difference between the original digit in that position and the permuted digit in that position.
Now let's consider the permutation itself. Any permutation can be decomposed into cycles. Because we're looking for the minimum solution, it must be the case that every cycle in the permutation contains a zero. If there were a cycle without a zero, we could reduce every number in the cycle by the minimum value and produce a smaller solution. Furthermore, because every cycle contains a common element, that means the permutation can be written as a single cycle, since two cycles with a common element can be merged into one cycle using that element.
To build such a cycle, we can start at a zero, and when we add a digit to the path we know based on its position what the difference must be between it and the previous digit. For each of the 2|S| subsets of positions we can compute the minimum value that corresponds to a path through those positions. This step is O(|S|·2|S|).
Side note: the answer, if it exists, always begins with 0. There are 2 cases to consider. If S begins with an 'f', then the only possible solutions begin with a 0. Otherwise, the value given by $$\frac{s}{15}$$ is a valid solution, and starts with 0.