PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
There is a linear-time solution to the problem. The details can get quite technical, so I’ll just explain the high-level ideas. As a warm-up, consider the following problem. Say we just want to find the least integer C’ using the digits of C such that C’ > A and C’ > B (don’t worry about the reversed part yet). Assume A >= B so we just need to worry about C’ > A. The basic idea is the following. For any such arrangement C’ of C such that C’ > A, we can break C’ into three parts. First is the common prefix of C’ and A. Next is the single digit following this prefix which must be greater than the corresponding digit of A. Finally, we have the remaining digits. A key observation is that if C’_ 1 and C’_ 2 are both greater than A and C’_ 1 < C’_ 2, then then length of the common prefix of C’_ 1 and A is at least the length of the common prefix of C’_ 2 and A.
A linear-time algorithm for solving this simpler problem is as follows. Create the longest possible string out of the digits of C that is a prefix of A. Call this prefix P and say it’s length is |P|. Now, if all remaining digits of C are less than the (|P|+1)st digit (from the left) of A, then iteratively delete the last digit of P until there is a digit of C not used in P that exceeds the (|P|+1)st digit of A. Once we have found such a digit, append it to P. Finally, now that P exceeds the length |P| prefix of A, we are free to assign the remaining digits in any way. The least such way is to first append the remaining 0s to P, then the remaining 1s, and so on.
For the more general problem, finding the longest common prefix of a solution is still a good guiding principle. For a string S such that S > (both length |S| prefixes of A and B), we can append the remaining n-|S| digits of C in any order to have the resulting string exceed A and B. Let S’ be obtained by appending the remaining 9s to S, then the remaining 8s, and so on. Then there exists a C’ that extends S with C’ > A, C’ > B, C’^R < A^R, and C’^R < B^R if and only if this string S’ is such a solution. An algorithm proceeds as in the previous paragraph, except we iteratively delete digits of the prefix P until both the condition in the preceding paragraph is satisfied and appending the remaining digits to P in decreasing order results in a valid solution. This is possible to do in linear time (i.e. constant time per deletion of the last digit of P) with the right bookkeeping.
Now, we are left with a string P such that P > (both length |S| prefixes of A and B) and such that there is a way to append the remaining digits to P to satisfy the conditions on the reversed numbers. A similar algorithm can be employed to append these digits in such a way as to form the least possible C’ that satisfies both the original and reversed inequalities.