Median Rearrangement solution codechef
You have anmatrix . You can rearrange the elements of the matrix in any way. Let be the medians of each row in after the rearrangement. The goodness of the matrix is defined as the minimum median among the medians of all rows i.e . Naturally, rearranging values also comes with a cost. The cost of rearrangement is defined as .
Find the maximum goodness you can achieve after rearranging a matrixsuch that the cost of rearrangement doesn’t exceed or if the answer doesn’t exist.
The median of an arrayconsisting of elements is the smallest element of . The median of is and the median of is .
- The first line of the input contains a single integer denoting the number of test cases. The description of test cases follows.
- The first line of each test case consists of two space-separated integers and .
- lines follow, each consisting of space-separated integers denoting the matrix
For each test case, print a single line containing one integer – the maximum goodness you can achieve such that the rearrangement cost does not exceed
-1 if the answer doesn’t exist.
Subtask 1 (20 points):
Subtask 2 (40 points):
Subtask 3 (40 points): Original constraints
Sample Input 1
3 4 100 13 2 1 16 15 24 3 3 5 17 9 8 9 6 11 32 4 40 13 2 1 16 15 24 3 3 5 17 9 8 9 6 11 32 3 1 3 4 2 5 7 9 2 1 1
Sample Output 1
9 6 -1
Test case: We rearrange the matrix as follows: . The medians of each row are respectively. The goodness is and the cost is . There are other rearrangements that may yield the same goodness but is the maximum goodness we can get.
Test case: The rearranged matrix is: . The medians of each row are respectively. The goodness is and the cost is . There are other rearrangements that may yield the same goodness but is the maximum goodness we can get.
Test case: No matter how we rearrange the elements, the cost is always greater than .