Toy Machine
Contest: Codeforces Round 869 (Div. 1)
Difficulty rating: 2700
Tags: constructive algorithms, games, implementation

There is a toy machine with toys arranged in two rows of $$$n$$$ cells each ($$$n$$$ is odd).

Initial state for $$$n=9$$$.

Initially, $$$n-2$$$ toys are placed in the non-corner cells of the top row. The bottom row is initially empty, and its leftmost, rightmost, and central cells are blocked. There are $$$4$$$ buttons to control the toy machine: left, right, up, and down marked by the letters L, R, U, and D correspondingly.

When pressing L, R, U, or D, all the toys will be moved simultaneously in the corresponding direction and will only stop if they push into another toy, the wall or a blocked cell. Your goal is to move the $$$k$$$-th toy into the leftmost cell of the top row. The toys are numbered from $$$1$$$ to $$$n-2$$$ from left to right. Given $$$n$$$ and $$$k$$$, find a solution that uses at most $$$1\,000\,000$$$ button presses.

To test out the toy machine, a web page is available that lets you play the game in real time.

Input format:
The first and only line contains two integers, $$$n$$$ and $$$k$$$ ($$$5 \le n \le 100\,000$$$, $$$n$$$ is odd, $$$1 \le k \le n-2$$$) — the number of cells in a row, and the index of the toy that has to be moved to the leftmost cell of the top row.

Output format:
On a single line, output a description of the button presses as a string of at most $$$1\,000\,000$$$ characters. The string should only contain the characters L, R, U, and D. The $$$i$$$-th character in the string is the $$$i$$$-th button that is pressed. After all the button presses are performed, the $$$k$$$-th toy should be in the leftmost cell of the top row.

If there are multiple solutions, print any. The number of button presses does not have to be minimized.

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

Note:
In the first example, there will be $$$5-2 = 3$$$ toys. The first toy needs to end up in the leftmost cell of the top row. The moves RDL will achieve this, see the picture for a better understanding. Another possible solution would be to do one button press L.

Visualization of the moves for the first example.

Example input:
5 1

Example output:
RDL

Example input:
7 2

Example output:
RDL

Editorial:
Instead of caring about the positions of all the toys, we only need to care about the position of the special toy with index $$$k$$$. The other toys can be treated as undistinguishable.
The intended way of solving this problem is playing the game in the webpage, trying to come up with some simple combinations of operations that make the special toy move to another position in a predictable way. Using these building blocks in a smart way, finding a way to move the special toy to the topleft.
As the size of the grid can be up to $$$100\,000$$$ and we can make $$$1\,000\,000$$$ moves, we will be aiming for a solution which does a linear number of moves.
There are lots of potential solutions which use a linear number of moves, here is a relatively painless one:
Do casework on $$$k$$$:
- Case $$$1$$$: If $$$1 \leq k < \frac{n-1}{2}$$$, we initally make one R button press to align the toys with the right boundary. After this, there is an easy pattern to expose all the toys in the left halve, one by one: DRURDRUR... repeated. When the special toy is exposed, the repeating pattern is stopped, and DL are pressed. Toy $$$k$$$ will be moved to the topleft corner.
<spoiler summary="Visualization"><img class="tex-graphics" src="https://espresso.codeforces.com/0a9dc10afb5234f521c1c84c118804df6b8cb4be.png" style="max-width: 100.0 - Case $$$2$$$: If $$$k = \frac{n-1}{2}$$$, the puzzle can be solved in two moves: DL.
<spoiler summary="Visualization"><p><img class="tex-graphics" src="https://espresso.codeforces.com/a947b0f6f44e8ef1f44c0e9be4212155650bfdd8.png" style="max-width: 100.0 - Case $$$3$$$: If $$$\frac{n-1}{2} < k \leq n-2$$$, we try to reduce back to case $$$1$$$, by moving the special toy to the left halve, and ensuring that all other toys are in the top row. Using symmetry, we can apply case $$$1$$$ to $$$k^\prime = n-1 - k$$$, but mirror all horizontal moves, to move the toy to the topright corner. The other toys are no longer all in the top row. To fix this, the last pattern we need is again DRURDRUR... repeated. After a while of repeating this, all toys will be in the right halve of the board, occupying the top and bottom row. To finish moving the special toy (which stayed in the topright corner), we do the buttons presses LDRU. All toys end up in the top row, and the special toy will be at position $$$k_\text{new} = \frac{n-1}{2} - 1$$$, so this successfully reduces to case $$$1$$$.
<spoiler summary="Visualization"><img class="tex-graphics" src="https://espresso.codeforces.com/c138e7d0a3ca6d44b54f47331647da2b9b42766c.png" style="max-width: 100.0 How many moves does this take? In case $$$1$$$ the pattern DRUR needs to be repeated at most $$$\approx \frac{n}{2}$$$ times. In case $$$3$$$, we need to use the first pattern $$$\frac{n}{2}$$$ times, and we use the second pattern $$$\frac{n}{2}$$$ times. We reduce down to case $$$1$$$, but luckily the special toy is already close to the correct position, so only a constant number of extra moves are done.
So in total, this solution uses $$$O(1) + \max \left( 4\frac{n}{2}, 4 \cdot 2 \frac{n}{2} \right) = 4n + O(1)$$$ moves. SO this solution fits well within the constraints, although it is pretty wasteful.
Bonus: Can you prove that the optimal number of moves needed in the worstcase (over all $$$k$$$) for a width of $$$n$$$ is $$$\Omega(n)$$$? We only did some testing of small cases, with a bruteforce BFS solution, and found that the worstcase is around $$$n/2$$$ button presses.