 MTRXMOD - Editorial

#1

Author: Yuri Shilyaev
Editorialist: Daniil Melnichenka

Simple

PREREQUISITES:

Absolute value equations.

PROBLEM:

Given a matrix B of size N imes 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 eq 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.

#2

#3

#4

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.

#5

Optimised brute force passes the test cases.

Well, I should learn to give it a go despite penalty sometimes XD