The desired equality isn’t true only if max(ri) < min(Cj), and then we must increase max(ri) or decrease min(Ci), or do both. In order to increase max(ri), it’s enough to change elements in one row only (increase ri for one i). Similarly, to decrease min(Ci), it’s enough to change elements in one column.

Let’s say we know the value X = max(ri) = min(Cj) in the optimal solution. Then we should choose one row and change to X all numbers smaller than X, and similarly choose one column and change to X all numbers
greater than X.

Slow approach: iterate over each pair of row and column. For each value X occurring in the row or the column, count the cost of the row as the number of elements smaller than X, and the cost of the column as the number of elements greater than X. Consider the sum of those two costs as the answer.

O(n^2 log(n)) solution: sort all n^2 values and process them in the increasing order. In each moment, for the current value X, we should know costs of all rows and costs of all columns. The possible answer is the sum of costs of the best row and the best column.

preda2or16:29, Dec 06Shubham Kumar Guptamax(ri) ≤ min(Cj) because ri ≤ t[i][j] ≤ Cj

The desired equality isn’t true only if max(ri) < min(Cj), and then we must increase max(ri) or decrease min(Ci), or do both. In order to increase max(ri), it’s enough to change elements in one row only (increase ri for one i). Similarly, to decrease min(Ci), it’s enough to change elements in one column.

Let’s say we know the value X = max(ri) = min(Cj) in the optimal solution. Then we should choose one row and change to X all numbers smaller than X, and similarly choose one column and change to X all numbers

greater than X.

Slow approach: iterate over each pair of row and column. For each value X occurring in the row or the column, count the cost of the row as the number of elements smaller than X, and the cost of the column as the number of elements greater than X. Consider the sum of those two costs as the answer.

Please make sure the answer is not too short