×

# MTRXMOD - Editorial

Author: Yuri Shilyaev
Editorialist: Daniil Melnichenka

Simple

# PREREQUISITES:

Absolute value equations.

# PROBLEM:

Given a matrix $B$ of size $N \times N$, made by following rule: $B_{i, j} = |A_{i}-A_{j}|$. Find a lexicographically minimal sequence $A$ of $N$ numbers that could have been used to build matrix $B$ with $A_1 = 0$. Also answer $Q$ queries of changing a row and corresponding column of matrix to the new one.

# QUICK EXPLANATION:

Let's restore the sequence in $O(N)$. Find a first non-zero element (let it be element number $i$) and assign it to $-B_{1, i}$. Now restore all the other elements using equations with $A_1$ and $A_i$.

The total complexity would be $O(N^2+NQ)$.

# EXPLANATION:

Firstly let's maintain matrix $B$. Besides it's easy to see the following fact. Suppose we have some array $A$ that is suitable for current matrix $B$. Let's replace all elements in $A$ with the additive inverses. Obviously, the new array fits matrix $B$.

Let's do the following after every query. We know that $A_1$ is equal to 0. Let's find the smallest $i$ that $B_{1, i}$ is not zero with a simple loop. Evidently all $A_j$ ($j$ < $i$) are equal to 0. Now we should take advantage of a fact that was mentioned above and assign $A_i = -B_{1, i}$ as we want to get the lexicographically smallest answer. After that let's make a loop for all $j$ ($i$ < $j$ $\le$ $N$). Easy to note that we have a system of equations:

$|A_i - A_j| = B_{i, j}$
$|A_1 - A_j| = B_{1, j}$

where $A_1 \neq A_i$ and all the values are known except $A_j$. Now we should just solve this system of equations and find out $A_j$.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

119
accept rate: 0%

19.8k350498541

 0 Still access denied for both codes. Why? answered 02 Sep '17, 10:20 11●2 accept rate: 0%
 0 It is not necessary that initial array will always fit for matrix B. So we need to process that also. As for example :  0 4 3 B = 4 0 7 3 7 0  and then A will be : A = 0 -4 3 P.S. I managed to make Java program for this question in a easy to understand way https://www.codechef.com/viewsolution/15219379 but it gives runtime error. But the interesting thing is that before this I submitted answer that printed answer correctly but in wrong format { 0 -1 -2 --> [0, -1, -2] } but still it gives runtime error instead of wrong answer. answered 02 Sep '17, 15:32 0●1 accept rate: 0%
 0 Optimised brute force passes the test cases. Well, I should learn to give it a go despite penalty sometimes XD answered 13 Sep '17, 21:33 15.5k●1●20●66 accept rate: 18%
 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,852
×1,191
×890
×31
×9

question asked: 20 Aug '17, 14:53

question was seen: 2,059 times

last updated: 30 Dec '17, 02:14