|Codeforces Round #607 (Div. 1)|
You are an intergalactic surgeon and you have an alien patient. For the purposes of this problem, we can and we will model this patient's body using a $$$2 \times (2k + 1)$$$ rectangular grid. The alien has $$$4k + 1$$$ distinct organs, numbered $$$1$$$ to $$$4k + 1$$$.
In healthy such aliens, the organs are arranged in a particular way. For example, here is how the organs of a healthy such alien would be positioned, when viewed from the top, for $$$k = 4$$$:
Here, the E represents empty space.
In general, the first row contains organs $$$1$$$ to $$$2k + 1$$$ (in that order from left to right), and the second row contains organs $$$2k + 2$$$ to $$$4k + 1$$$ (in that order from left to right) and then empty space right after.
Your patient's organs are complete, and inside their body, but they somehow got shuffled around! Your job, as an intergalactic surgeon, is to put everything back in its correct position. All organs of the alien must be in its body during the entire procedure. This means that at any point during the procedure, there is exactly one cell (in the grid) that is empty. In addition, you can only move organs around by doing one of the following things:
Your job is to figure out a sequence of moves you must do during the surgical procedure in order to place back all $$$4k + 1$$$ internal organs of your patient in the correct cells. If it is impossible to do so, you must say so.
The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 4$$$) denoting the number of test cases. The next lines contain descriptions of the test cases.
Each test case consists of three lines. The first line contains a single integer $$$k$$$ ($$$1 \le k \le 15$$$) which determines the size of the grid. Then two lines follow. Each of them contains $$$2k + 1$$$ space-separated integers or the letter E. They describe the first and second rows of organs, respectively. It is guaranteed that all $$$4k + 1$$$ organs are present and there is exactly one E.
For each test case, first, print a single line containing either:
If it is impossible, then this is the only line of output for the test case. However, if it is possible, output a few more lines describing the sequence of moves to place the organs in the correct locations.
The sequence of moves will be a (possibly empty) string of letters u, d, l or r, representing sliding the organ that's directly above, below, to the left or to the right of the empty space, respectively, into the empty space. Print the sequence of moves in the following line, as such a string.
For convenience, you may use shortcuts to reduce the size of your output. You may use uppercase letters as shortcuts for sequences of moves. For example, you could choose T to represent the string lddrr. These shortcuts may also include other shortcuts on their own! For example, you could choose E to represent TruT, etc.
You may use any number of uppercase letters (including none) as shortcuts. The only requirements are the following:
As an example, if T = lddrr, E = TruT and R = rrr, then TurTlER expands to:
To use shortcuts, print each one of them in a single line as the uppercase letter, then space, and then the string that this shortcut represents. They may be printed in any order. At the end of all of those, print a single line containing DONE.
Note: You still need to print DONE even if you don't plan on using shortcuts.
Your sequence does not need to be the shortest. Any valid sequence of moves (satisfying the requirements above) will be accepted.
2 3 1 2 3 5 6 E 7 8 9 10 4 11 12 13 11 34 45 6 22 16 43 38 44 5 4 41 14 7 29 28 19 9 18 42 8 17 33 1 E 15 40 36 31 24 10 2 21 11 32 23 30 27 35 25 13 12 39 37 26 20 3
SURGERY COMPLETE IR R SrS S rr I lldll DONE SURGERY FAILED
There are three shortcuts defined in the first sample output:
The sequence of moves is IR and it expands to: