Sorting device

All submissions for this problem are available.
You work for a large company, and your job is to design sorting devices. Devices are built from:
 n inputs,
 n outputs,
 gates which have two inputs and send to output the minimum ("min gates") or maximum ("max gates") of the two numbers given at their input,
 connecting wires.
You are competing in a bid for a Bytelandian Ministry of Information contract to design the smallest possible device (in terms of the number of gates) which sorts any input. Each device will go through a rigorous test process on a number of data sets. However, through some Good Friends in High Places you have managed to acquire some additional information concerning the exact data sets (permutations) your device will be tested on. Make use of this, and of course your superior programming skills, to win the bid!
Input
First, two numbers, 2≤n≤20, 1≤k≤1000, the number of inputs and the number of different permutations for which your device will be tested. The next k lines contain permutations of the numbers 1 .. n.
Output
First, output p, the number of gates in your device (0≤p≤10^{6}). The next p lines should contain definitions of the gates used, in the form of a pair of integers, x_{i},y_{i}, and exactly one of the strings "min" or "max". To be able to use the output of a gate as the input of a subsequent gate, we use the following convention. First of all, the range for inputs x_{i} and y_{i} is as follows: 1 ≤ x_{i},y_{i} < n+p. The output of the ith gate is assumed to be input n+i.
Finally, a sequence of exactly n integers in the range 1..n+p should follow, describing which of the "inputs" should be hardwired to successive outputs of the device.
Scoring
If your program does not produce a sorting machine which works for every input (sorting it in ascending order), it will be deemed incorrect. Otherwise, you will score p penalty points for each test case solved.
Example
Input:
3 2
1 2 3
1 3 2
Output:
2
2 3 min
2 3 max
1 4 5
Score:
0.5
Author:  admin 
Tags  admin 
Date Added:  15012010 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, kotlin, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 