Closest Ranking

All submissions for this problem are available.
You have just begun his job with Educated Guessing Pollsters. An election is only weeks away and the company would like to get a general idea of how the voters feel about
the candidates. They asked a (probably not) random subset of N voters to submit a ranking of the M candidates.
Say the candidates are numbered from 1 to M.
A ranking is then a permutation of the set {1,2,...,M} listed as:
c_1 c_2 ... c_M
The list is such that the voter prefers candidate c_i to candidate c_j if i > j. Your task is to determine a ranking R = r_1, r_2, ..., r_M such that the total number of disagreements with all voters who were polled is minimized.
More precisely, for a voter V we say the distance d(V,R) between voter V and ranking R is precisely the number of pairs (i,j) with 1 <= i < j <= M such that V actually prefers candidate r_i over candidate r_j. Say there are N voters labeled V_1, V_2, ..., V_n. The task is then to find a ranking R such that the sum
d(V_1, R) + d(V_2, R) + ... + d(V_n, R)
is minimized.
Input:
The first line of input consists of a single integer T ≤ 25 indicating the number of test cases to follow.
Each test case begins with two integers N and M on a single line where N represents the number of voters and M represents the number of candidates. The following N lines contain th
e rankings of the voters, one per line.
Each ranking is given as a permutation c_1, c_2, ..., c_M of the numbers 1,2,...,M where consecutive numbers are separated by a space. In this ranking, c_i is preferred over c_j by precisely when i > j.
A blank line appears between test cases (including a blank line just before the first test case).
The bounds are 1 <= N <= 1000 and 1 <= M <= 15.
Output:
Each test case has a single line of output of the following form:
D: r_1 r_2 ... r_M
Where D is the sum of the distances between the optimum ranking and the input rankings and r_1, r_2, ..., r_M is a ranking of the same form as the input rankings that achieves this
minimum distance. If there are multiple such orderings, then output the one that minimizes r_M. Among those that minimize r_M, you should output the one that minimizes r_{M1} and so on.
Example:
Input:
2 2 3 1 2 3 1 2 3 4 3 1 2 3 2 1 3 1 2 3 3 2 1
Output:
0: 1 2 3 4: 2 1 3
(note that in the second case that the ranking 1 2 3 also has total distance 4, but 2 1 3 is output based on the rules outlined in the output specification)
Author:  friggstad 
Tester:  anshuman_singh 
Editorial  http://discuss.codechef.com/problems/VOTING 
Tags  friggstad, july10, medium 
Date Added:  10042010 
Time Limit:  1.93545 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, 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. 