×

# MTRNSFRM - Editorial

Author: Alexey Zayakin
Editorialist: Alexey Zayakin

Easy

# 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:

This question is marked "community wiki".

3841612
accept rate: 28%

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)

@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)

 1 Has anyone used binary search to solve the problem , can you please explain ? answered 23 Jan '17, 21:29 4★bhishma 297●7 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)
 0 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 . answered 25 Jan '17, 10:58 4★vivace 46●1 accept rate: 10% 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) thank you very much . I got my mistake . (01 Feb '17, 20:05) vivace4★
 0 @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! :) answered 25 Jan '17, 11:38 15.4k●1●20●66 accept rate: 18%
 0 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. answered 24 Jun '17, 11:03 4★icyfire 1 accept rate: 0%
 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." answered 26 Oct '17, 03:31 1★pri_1234 21●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,678
×3,763
×947
×877
×39
×36
×5

question asked: 21 Jan '17, 20:58

question was seen: 3,538 times

last updated: 26 Oct '17, 03:31