https://www.codechef.com/problems/MINIMAX/v
Asked by: Deepak_kumar_Shaw on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.
max(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.