DIGROT - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

One way to perform a digit rotation is to convert the number to a string, perform a rotation on the string, then convert back to an integer. Another method is to use divisions and multiplications by 10. Although it was possible solve using a depth first search or breadth first search, the maximum value always occurs after one of the following:

Left rotations only (at most 6)
Right rotations only (at most 6)
A single left rotation followed by a single right rotation
A single right rotation followed by a single left rotation

To see why this is so, consider the similar problem where we have to perform 0 or more rotations. In this case, the answer will always have the same number of digits as the original number. Since the number of digits cannot increase as the result of a rotation, each rotation must leave the number of digits unchanged. Suppose we have some sequence of rotations that produces the maximal answer. Any consecutive rotations in different diretions must have no net effect. Thus we can remove such pairs until all rotations are in the same direction. Additionally, any D rotations in the same direction have no net effect, where D is the number of digits in N. We can remove sets of D rotations until fewer than D rotations remain. Now if there are exactly D-1 rotations, we can replace them with 1 rotation in the opposite direction. Thus at most D-2 rotations are needed, all in the same direction.

Now the original problem is equivalent to performing one rotation followed by 0 or more additional rotations. Therefore the solution will involve performing one rotation in one direction, followed by 0 or more rotations in another direction (which may be the same as the first direction). We can show that each of the 4 possible cases can be simplified to one of the 4 cases above.

To solve using a breadth first search, use a set and a queue (or, for a depth first search, use a stack). Initially, insert N into the queue. Then as long as the queue is non-empty, remove a number from it, and rotate that number in each direction. For each of the 2 resulting numbers, check if it exists in the set. If not, insert it into both the set and the queue, otherwise do nothing. When the queue is empty, the largest element in the set is the answer.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.