Hidden Word
Contest: Canada Cup 2016
Difficulty rating: 1600
Tags: brute force, constructive algorithms, implementation, strings

Let’s define a grid to be a set of tiles with 2 rows and 13 columns. Each tile has an English letter written in it. The letters don't have to be unique: there might be two or more tiles with the same letter written on them. Here is an example of a grid:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

We say that two tiles are adjacent if they share a side or a corner. In the example grid above, the tile with the letter 'A' is adjacent only to the tiles with letters 'B', 'N', and 'O'. A tile is not adjacent to itself.

A sequence of tiles is called a path if each tile in the sequence is adjacent to the tile which follows it (except for the last tile in the sequence, which of course has no successor). In this example, "ABC" is a path, and so is "KXWIHIJK". "MAB" is not a path because 'M' is not adjacent to 'A'. A single tile can be used more than once by a path (though the tile cannot occupy two consecutive places in the path because no tile is adjacent to itself).

You’re given a string s which consists of 27 upper-case English letters. Each English letter occurs at least once in s. Find a grid that contains a path whose tiles, viewed in the order that the path visits them, form the string s. If there’s no solution, print "Impossible" (without the quotes).

Input format:
The only line of the input contains the string s, consisting of 27 upper-case English letters. Each English letter occurs at least once in s.

Output format:
Output two lines, each consisting of 13 upper-case English characters, representing the rows of the grid. If there are multiple solutions, print any of them. If there is no solution print "Impossible".

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

Example input:
ABCDEFGHIJKLMNOPQRSGTUVWXYZ

Example output:
YXWVUTGHIJKLM
ZABCDEFSRQPON

Example input:
BUVTYZFQSNRIWOXXGJLKACPEMDH

Example output:
Impossible

Editorial:
1. The input string s contains 27 letters and it contains every letter in the English alphabet. The English alphabet has 26 letters, so there is exactly one repeated letter.
2. If the instances of the repeated letter are adjacent in the string, there can be no solution. That's because every English letter occurs in s and the solution grid contains exactly 26 tiles, so any solution must have all letters distinct. Consider the tile containing the repeated letter. None of the tiles adjacent to it can contain the repeated letter because the letters of the grid are distinct, so the grid doesn't contain s.
3. Otherwise, there is a solution. Delete the second occurrence of the repeated letter and write the resulting string in circular order. For example, if the string with the repeated letter deleted is ABCDEFGHIJKLMNOPQRSTUVWXYZ, we write this to the grid:
Then we rotate the grid, one step at a time, until it contains s. For example, if the above grid isn't a valid solution, we next try this:
And then this:
This will eventually give us a solution. Suppose the repeated letter lies between G and H in the original string. In each rotation, there are 2 letters adjacent to both G and H in the grid (in the above examples these letters are S and T, then Q and R, then O and P). When we rotate the string by a step, the adjacent letters advance by 1 or 2 steps. Eventually the repeated letter will be adjacent to both G and H, and this will yield a solution.