what will be the approach for this question

codechef easy

https://www.codechef.com/problems/MINIMAX/v

vibrant
Deepak kumar Shaw
vibrant

Please Log in to answer

Note: Your answer should not be too short. Please wait a few seconds for the editor to load



Please make sure the answer is not too short

1 Answer

preda2or
preda2or 16:29, Dec 06
Shubham Kumar Gupta

  • 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.
     

  •  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.




Please make sure the answer is not too short
0 Upvotes
Comments
No Comments yet