- Prepare
- Algorithms
- NP Complete
- Sam's Puzzle (Approximate)

# Sam's Puzzle (Approximate)

# Sam's Puzzle (Approximate)

Sam invented a new puzzle game played on an matrix named , where each cell contains a unique integer in the inclusive range between and . The coordinate of the top-left cell is .

**The Moves**

A move consists of two steps:

- Choose a sub-square of .
- Rotate the sub-square in the
*clockwise*direction.

For example:

We describe a move as the clockwise rotation of a sub-square whose top-left corner is located at coordinate . In the example above, , , and .

**Good Pairs of Cells**

A pair of cell is *good* if one of the following is true:

- They're located in the same row and the number in the left cell is less than the number in the right cell.
- They're located in the same column and the number in the upper cell is less than the number in the lower cell.

The diagram below depicts all the *good* pairs of cells located in the same row:

The diagram below depicts all the *good* pairs of cells located in the same column:

**Goodness of a Square**

We define the *goodness* of a sub-square to be the total number of good pairs of cells in the sub-square.

**The Goal**

Given the initial value of , maximize its goodness as much as is possible by performing a sequence of *at most* moves. Then print the necessary moves according to the *Output Format* specified below.

**Input Format**

The first line contains an integer denoting . Each of the subsequent lines contains space-separated integers. The integer in the line denotes the cell located in coordinate .

**Constraints**

- Each cell contains a unique number in the inclusive range between and .

**Scoring**

- We define as the goodness in the beginning, as the goodness after your moves, and as the maximum possible goodness.
- A valid answer earns of a test case's available points (it's guaranteed that ). The total score will be rounded up to the next .

**Test Case Generation**

- Consider all the cells in to be initially empty. Sam sorts the numbers in ascending order and then picks them one by one and places them in some random cell which has no empty cell to its left and no empty cell above it. This generates a square with goodness .
- After generating , Sam makes some random rotations. During each step, he chooses three random numbers, , , and , and rotates a sub-square with the top-left corner at coordinate in the
*counterclockwise*direction. Here and . - Sam makes
*at most*such random counterclockwise rotations. This means that it's possible to achieve maximum goodness in as little as moves.

**Output Format**

Print the following lines of output:

- On the first line, print an integer, , denoting the number of moves necessary to maximize the goodness of . Recall that this number must be .
- For each move, print three space-separated integers describing its respective , , and values on a new line. Recall that a move is described as the clockwise rotation of a sub-square whose top-left corner is located at coordinate .

**Sample Input 0**

```
3
8 6 9
7 2 5
1 4 3
```

**Sample Output 0**

```
3
1 1 2
2 2 2
1 1 3
```

**Explanation 0**

- After the first move:

- After the second move:

- After the third move:

The goodness after this sequence of moves is , and the maximum possible goodness is .

Because the initial goodness was , this solution will get of the test case's available points.