Social Cluster

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
This problem deals with the effective formation of a cluster among K individuals living in a society. A society can be represented as a N × N grid. Individuals are located at certain points on the grid. Each individual's social interaction is measured by a positive integer, called interaction power denoted by I_{i}. The dissimilarity between two individuals is defined as the absolute difference between their interaction powers. Less the absolute difference between interaction powers of two individuals, more the probability that they will interact with each other.
Now your task is to form a single cluster of individuals by displacing some individuals from their original positions. Formally, a cluster means a connected component. An individual at point (x_{i}, y_{i}) is said to be adjacent to another individual at point (x_{j}, y_{j}) if and only if x_{i} − x_{j} ≤ 1 and y_{i} − y_{j} ≤ 1.
What needs to be optimized ?
The cost of clustering is defined as Score = 1000×A + 10×B , where A and B are two variables. The task is to minimize this cost.
We define A first. Suppose P be the set of individuals on the grid and P = K. In order to create the cluster, we may need to displace some individuals from their original positions on the grid. Let the individual p_{i} be displaced by a Manhattan distance d_{i} in order to become a part of the cluster.
Now d_{i} = x_{i(final)} − x_{i(initial)} + y_{i(final)} − y_{i(initial)}.
Here (x_{i(initial)}, y_{i(initial)}) is the initial position of individual p_{i} and (x_{i(final)}, y_{i(final)}) is the position of the same individual after becoming a part of the cluster.
Now A = Σ (d_{i} / I_{i}) where i = 1 to K.
Here I_{i} = Interaction power of individual p_{i}.
The variable B is defined after the cluster is formed.
B = Σ ( s_{i} / n_{i} ) , where i = 1 to K.
s_{i} = Σ (I_{j} − I_{i} ), where { p_{j} ∈ P  p_{j} is adjacent to p_{i} }.
n_{i} = Number of individuals adjacent to p_{i}.
Input
The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow.
The first line of each test case contains two space separated integers N and K, denoting the grid size and the number of individuals, respectively. Then N lines follow. The i^{th} of these lines contains N space separated integers, denoting the information regarding the i^{th} row. The j^{th} value of i^{th} row contains the index value of an individual at (i, j) cell. The index value, of course, ranges from 1 to K. Empty cells have zero value.
Then K lines follow. The i^{th} of these lines contains the value of I_{i}, the interaction power of i^{th} individual.
Output
For each test case, print N lines, each line containing N space separated integers. It represents the N × N grid containing the cluster.
Constraints
 1 ≤ T ≤ 60
 2 ≤ N ≤ 60
 2 ≤ K ≤ 2000
 1 ≤ I_{i} ≤ 25
Example
Input: 1 5 5 0 0 0 1 0 0 0 0 0 0 2 0 5 0 4 0 0 0 0 0 0 3 0 0 0 2 3 2 3 3 Output: 0 0 0 0 0 0 0 1 0 0 0 2 5 4 0 0 0 3 0 0 0 0 0 0 0
Explanation
Calculation of value A : d_{1} = 2 I_{1} = 2 d_{2} = 1 I_{2} = 3 d_{3} = 2 I_{3} = 2 d_{4} = 1 I_{4} = 3 d_{5} = 0 I_{5} = 3 A = d_{1}/ I_{1} + d_{2}/I_{2} + d_{3}/I_{3} + d_{4}/I_{4} + d_{5}/I_{5} = 1 + 0.333... + 1 + 0.333... + 0 = 2.666...
Calculation of value B : (Number of individuals adjacent to 1) = n_{1} = 3 ( 2 , 5 , 4 ) s_{1} = I_{1} − I_{2} + I_{1} − I_{5} + I_{1} − I_{4} = 1 + 1 + 1 = 3 (Number of individuals adjacent to 2) = n_{2} = 3 ( 1 , 5 , 3 ) s_{2} = I_{2} − I_{1} + I_{2} − I_{5} + I_{2} − I_{3} = 1 + 0 + 1 = 2 In a similar fashion , n_{3} = 3, n_{4} = 3, n_{5} = 4, s_{3} = 3, s_{4} = 2, s_{5} = 2, B = s_{1}/n_{1} + s_{2}/n_{2} + s_{3}/n_{3} + s_{4}/n_{4} + s_{5}/n_{5} = 1 + 0.666... + 1 + 0.666... + 0.5 = 3.833... Now Cost = 1000×A + 10×B = 2666.66... + 38.33... = 2705 A different configuration of the cluster may result in a different cost. The task is to minimize this clustering cost.
Test generation method and scoring
All test file has T = 60. Then each test case is generated as follows.
An integer x is chosen from [2, 60] uniformly and randomly at first. Then N is chosen from [x, 60] uniformly and randomly. Next, an integer y is chosen from [2, min(2000, N×N)], and K is chosen from [2, y] uniformly and randomly. Starting at empty grid, choose an empty cell uniformly and randomly, then put one individual put the cell one by one. Lastly, I_{i} are chosen from [1, 25] uniformly and randomly and independently for i=1,2,...,K.
There are 20 test files in the judge. The score for each test case is calculated as described in the statements. Then the score for each test file is defined by the sum of the score of test cases in the test file. Finally, the final score is defined by the average of the score for each test file. During the contest, only the first 12 test cases in each test case affect the score, and the scores of the rest 48 test cases are treated as 0.
Note
You are allowed maximum of 200 submissions in this problem. Also, no memory and time limit information will be provided for the test cases which are meant to be judged after the contest (i.e. 80% of the test cases). Though, you will be told AC/WA for that too.Author:  nssprogrammer 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/SCLUSTER 
Tags  annealing, aug15, challenge, facilityloc, heuristic, nssprogrammer, steinertree, stimulated 
Date Added:  17032015 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, 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. 