Grid Sort
Contest: Lyft Level 5 Challenge 2018 - Final Round
Difficulty rating: 3100
Tags: implementation

You are given an $$$n \times m$$$ grid. Each grid cell is filled with a unique integer from $$$1$$$ to $$$nm$$$ so that each integer appears exactly once.

In one operation, you can choose an arbitrary cycle of the grid and move all integers along that cycle one space over. Here, a cycle is any sequence that satisfies the following conditions:

- There are at least four squares.
- Each square appears at most once.
- Every pair of adjacent squares, and also the first and last squares, share an edge.

For example, if we had the following grid:

We can choose an arbitrary cycle like this one:

To get the following grid:

In this particular case, the chosen cycle can be represented as the sequence $$$[1, 2, 3, 6, 5, 8, 7, 4]$$$, the numbers are in the direction that we want to rotate them in.

Find any sequence of operations to sort the grid so that the array created by concatenating the rows from the highest to the lowest is sorted (look at the first picture above).

Note you do not need to minimize number of operations or sum of cycle lengths. The only constraint is that the sum of all cycles lengths must not be greater than $$$10^5$$$. We can show that an answer always exists under the given constraints. Output any valid sequence of moves that will sort the grid.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$3 \leq n,m \leq 20$$$) — the dimensions of the grid.

Each of the next $$$n$$$ lines contains $$$m$$$ integers $$$x_{i,1}, x_{i,2}, \ldots, x_{i, m}$$$ ($$$1 \leq x_{i,j} \leq nm$$$), denoting the values of the block in row $$$i$$$ and column $$$j$$$.

It is guaranteed that all $$$x_{i,j}$$$ are distinct.

Output format:
First, print a single integer $$$k$$$, the number of operations ($$$k \geq 0$$$).

On each of the next $$$k$$$ lines, print a cycle as follows:

$$$$$$s\ y_1\ y_2\ \ldots\ y_s$$$$$$

Here, $$$s$$$ is the number of blocks to move ($$$s \geq 4$$$). Here we have block $$$y_1$$$ moving to where block $$$y_2$$$ is, block $$$y_2$$$ moving to where block $$$y_3$$$ is, and so on with block $$$y_s$$$ moving to where block $$$y_1$$$ is.

The sum of $$$s$$$ over all operations must be at most $$$10^5$$$.

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

Note:
The first sample is the case in the statement. Here, we can use the cycle in reverse order to sort the grid.

Example input:
3 3
4 1 2
7 6 3
8 5 9

Example output:
1
8 1 4 7 8 5 6 3 2

Example input:
3 5
1 2 3 5 10
11 6 4 14 9
12 7 8 13 15

Example output:
3
4 4 14 13 8
4 5 10 9 4
4 12 7 6 11

Editorial:
The solution is more of a coding one than an algorithmic one. There are many different approaches, and it's important to be careful in how it is implemented. I'll explain one of the implementations.
First, we can always move a particular block left, up, down, or right with an appropriate 2x2 square around it. Let's code some functions that let us do that for each direction.
Next is to make sure that these moves don't mess up previous block spaces as we move blocks to the correct place. We can almost place blocks correctly in their spaces one by one in row major order, but there are some special cases.
- We can do all blocks except the last two rows, which we'll handle separately (in paragraph below) - For each row, we can correctly place all blocks except the last one. The last one requires a bit more careful work, but is easy to handle if we have at least two free rows.
For the last two rows, we can fill it in column by column from left to right. This is a similar startegy to fitting in the last column of the previous rows. We can almost do this except for the last 2x2 square.
For the last 2x2 square, we can use the following sequence of moves to swap two blocks:
Thus, we can shift the last block into the right position, then do at most three swaps (using the above sequence of moves) to fix the remaining blocks.
The number of moves for this strategy can be computed and estimated to be about 50k in the worst case.