< Back to forum

what will be the approach for this question

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

codechef easy

Asked by: Deepak_kumar_Shaw on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.

Enter your answer details below:


Enter your comment details below:




1 Answer(s)

avatar

  • 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.
Shubham_Kumar_Gupta last updated on April 7, 2019, 6:34 p.m. 0    Reply    Upvote   

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.