2017 Canadian Computing Olympiad

Day 2, Problem 3 - Shifty Grid

You are given a rectangular grid of numbered tiles, with no empty spaces. This grid can only be manipulated using a sequence of shift operations. A shift involves either moving an entire row left or right by some number of units, or moving an entire column up or down by some number of units. Tiles which move outside of the rectangular boundaries wrap around to the opposite side of the grid. For example, in the grid

a vertical shift downwards by one applied to the second column has the following result:

Notice that a left shift by K units is the same as a right shift by N − K units. Similarly, an upward shift by K units is a downward shift by M − K units. Thus, without loss of generality, we will restrict the shift directions to be only right or down.

In a grid with N rows and M columns, there are NM tiles in total. You may assume that the tiles are numbered with distinct integers from 0 to NM − 1.

You may have noticed that in the first example given above, the tiles are in a very organized formation. We call such arrangements solved. That is, a grid of tiles is solved when the first row contains the numbers from 0 to M − 1 in order, the second row has the numbers from M to 2M − 1 in order, and so on, with the last row having the number (N − 1)M to NM − 1 in order.

Find a sequence of shift operations that restores a scrambled grid to a solved state.

Input Format

The first line will contain two space-separated integers N and M (2 ≤ N, M ≤ 100). The next N lines will contain M space-separated integers, representing the grid.

Note that both N and M will always be even, and there will be a solution requiring at most 10⁵ shift operations.

For 5 of the available 25 marks, N · M ≤ 8.
For an additional 10 of the available 25 marks, the puzzle is solvable in at most 2 moves.

Output Format

Output any sequence of moves that solves the puzzle, in the following format:

• The first line of output should contain a single integer K (0 ≤ K ≤ 10⁵), representing the number of moves in the sequence.
• The next K lines should be either of the form 1 i r (1 ≤ i ≤ N, 0 ≤ r < M), representing a right shift of the i-th row by r, or of the form 2 j d (1 ≤ j ≤ M, 0 ≤ d < N), representing a down shift of the j-th column by d.

Sample Input 1

2 4
4 2 3 0
1 5 6 7

Sample Output 1

2
2 1 1
1 1 1

Explanation 1

We shift the first column down by one to obtain

1 2 3 0
4 5 6 7

then shift the first row right by one to reach the state

0 1 2 3
4 5 6 7

which is solved.

Sample Input 2

4 2
2 3
5 0
4 1
6 7

Sample Output 2

7
1 1 1
2 1 1
1 2 1
1 3 1
2 1 2
1 1 1
2 1 1

Explanation 2

The sequence of shifts, starting from the input is:

2 3    3 2    6 2    6 2    6 2    1 2    2 1    0 1
5 0 -> 5 0 -> 3 0 -> 0 3 -> 0 3 -> 4 3 -> 4 3 -> 2 3
4 1    4 1    5 1    5 1    1 5    6 5    6 5    4 5
6 7    6 7    4 7    4 7    4 7    0 7    0 7    6 7

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Aug 09, 2017

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)