You are not logged in. Please login at www.codechef.com to post your questions!

×

MTRNSFRM - Editorial

3
2

PROBLEM LINK:

Contest
Practice

Author: Alexey Zayakin
Testers: Hasan Jaddouh
Editorialist: Alexey Zayakin

DIFFICULTY:

Easy

PREREQUISITES:

Ad-hoc, math, median

PROBLEM:

Your are given two $n \times m$ matrices $A$ and $B$ and you are allowed to perform the following actions:

  • Choose one of the matrices
  • Choose either one row or one column of the selected matrix
  • Increment all the numbers in the selected row or column by $1$

What is the minimal number of actions required in order to make the two given matrices equal?

QUICK EXPLANATION:

We can reduce the problem to: given matrix $C = A - B$ and allowed operations are increase or decrease one row or column of the matrix $C$ by $1$, the goal it to make matrix $C$ contain only zeroes.

The order of operations doesn't matter, so we can just think of "balance" on every row and column. If we fix the "balance" of the first row, all the other balances can be uniquely determined. To find the optimal value for the first row, either use binary search or take a median of some values :)

EXPLANATION:

First of all, let's define a matrix $C = A - B$, i.e. $C_{ij} = A_{ij} - B_{ij}$. Every operation with matrix $A$ will increment an appropriate row or column in matrix $C$, and every operation with matrix $B$ will decrement an appropriate row or column in matrix $C$. Our goal of making matrices $A$ and $B$ equal can be reformulated to make matrix $C$ contain only zeroes. From now on we will work only with matrix $C$ assuming allowed operations are both increment and decrement.

It is easy to notice that the order of operations doesn't matter, thus for every row we can just calculate its balance, i.e. (how many times we will increment it) minus (how many times we will decrement it). Let's denote the balance of row $i$ with $row_i$ and similarly ― the balance of column $j$ with $col_j$.

After applying all the operations matrix $C$ should contain only zeroes, which can be reformulated as:
For every pair $(i, j)$: $C_{ij} + row_i + col_j = 0 \;\;\;\;\; (*)$.

If we fix the value of $row_1 = x$, then using the above equations with $i = 1$, we can get:
$C_{1j} + x + col_j = 0 \Leftrightarrow col_j = -C_{1j} - x$

For $j = 1$ we have $col_1 = -C_{11} - x$ and plugging $j = 1$ into $(*)$ we get:
$C_{i1} + row_i - C_{11} - x = 0 \Leftrightarrow row_i = C_{11} + x - C_{i1}$

So far we have used only the first row and the first column of the matrix $C$. To answer the question whether there exists a solution at all, we should check that the above balances make the whole matrix $C$ to contain zeroes only, i.e. rewriting $(*)$:
For every pair (i, j): $C_{ij} + (C_{11} + x - C_{i1}) + (-C_{1j} - x) = C_{ij} - C_{i1} - C_{1j} + C_{11} = 0$

If at least one of the above equalities fails, there is no solution at all, otherwise we should find the optimal values of $row_1 = x$.

The values we want to minimize (i.e. the total number of actions) is just:
$|row_1| + |row_2| + \dots + |row_n| + |col_1| + |col_2| + \dots + |col_m|$

Or rewriting it using the fixed value of $row_1 = x$:
$\displaystyle \sum_{i=1}^{n} |C_{11} - C_{i1} + x| + \sum_{j=1}^{m} |-C_{1j} - x| = \sum_{i=1}^{n} |C_{i1} - C_{11} - x| + \sum_{j=1}^{m} |-C_{1j} - x|$

Now the problem reduces to "Given $(n + m)$ points on line, find a point $x$ that minimizes the total distance from $x$ to all the given points". The $(n + m)$ points are $n$ points for rows: $(C_{i1} - C_{11})$ and $m$ points for columns: $-C_{1j}$. This problem has a well-known solution which is just the median of the given points.

The logic behind the median idea is: if we move the point $x$ to the left, then distance to all the points that were located before $x$ decreases, and distance to all the points that were located after $x$ increases. For the optimal position of $x$ moving it to the left will not reduce the total distance, which means that (count of points before $x$) $\le$ (count of points after $x$). By a similar argument, moving $x$ to the right will not reduce the total distance as well, which means that (count of points before $x$) $\ge$ (count of points after $x$). The only solution to the two inequalities above is (count of points before $x$) $=$ (count of points after $x$), which in turn means that $x$ is the median.

Time Complexity:

$\mathcal{O}(n \cdot m + (n + m) \cdot \log{(n + m)})$ per test case.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter
Tester

This question is marked "community wiki".

asked 21 Jan '17, 20:58

alex_2oo8's gravatar image

7★alex_2oo8
3841612
accept rate: 28%

edited 23 Jan '17, 00:02

admin's gravatar image

0★admin ♦♦
19.8k350498541

Can anyone please tell how do you jump to conclusion that for every (i,j): Cij + rowi + colj = 0

(23 Jan '17, 07:05) rishabh19063★

@rishabh1906: There are only two different ways to change the value of Cij, either increasing/decreasing i-th row, or j-th column. So, after all the operations are applied cell (i, j) of the matrix will contain value Cij + rowi + colj.

(23 Jan '17, 13:02) alex_2oo87★

Has anyone used binary search to solve the problem , can you please explain ?

link

answered 23 Jan '17, 21:29

bhishma's gravatar image

4★bhishma
2977
accept rate: 11%

3

$\displaystyle f(x) = \sum_{i=1}^{n} |C_{i1} - C_{11} - x| + \sum_{j=1}^{m} |-C_{1j} - x|$ is a function that is strictly decreasing before it reaches its minimum, than it has a segment where it is equal to the minimum and after it is strictly increasing, so one can use a binary search to find, for example minimal $x$, such that $f(x + 1) > f(x)$ (this will be the right border of the minimum segment). You can think of it as about a binary search on the derivative of $f$.

(23 Jan '17, 23:14) alex_2oo87★

The constraints allow you to even go for linear search . I tried submitting using linear search . Here's my code in which I am getting wrong answer . http://ideone.com/qFtK2x

Somebody help please .

link

answered 25 Jan '17, 10:58

vivace's gravatar image

4★vivace
461
accept rate: 10%

edited 25 Jan '17, 11:02

Your array $arr$ contains the points, not the values of the function we want to minimize. In your "binary search" you should use $\displaystyle \sum_{i=1}^{n + m}|arr[i] - x|$ instead of just $arr[x]$.

(27 Jan '17, 03:26) alex_2oo87★

thank you very much . I got my mistake .

(01 Feb '17, 20:05) vivace4★

@vivace

I tried running the code in codechef complier.

Did you just copy paste the code from ideone? If yes, then I strongly suggest running it once in codechef's "Code Compile and Run" and check if it runs smoothly. Cause compilers differ and it gave me errors when I tried to run it.

Hope it helps! :)

link

answered 25 Jan '17, 11:38

vijju123's gravatar image

4★vijju123 ♦♦
15.4k12066
accept rate: 18%

What if we gave decrementing a row by 1 the weight of X and decrementing a column by 1 a weight of Y, would the problem change? and how to optimally approach it in this case.

link

answered 24 Jun '17, 11:03

icyfire's gravatar image

4★icyfire
1
accept rate: 0%

please help me with this part in the explanation " The (n+m)(n+m) points are nn points for rows: (Ci1−C11)(Ci1−C11) and mm points for columns: −C1j−C1j."

link

answered 26 Oct '17, 03:31

pri_1234's gravatar image

1★pri_1234
211
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,639
×3,746
×935
×877
×39
×36
×5

question asked: 21 Jan '17, 20:58

question was seen: 3,534 times

last updated: 26 Oct '17, 03:31