MTRXMOD - Editorial

PROBLEM LINK:

Practice
Contest

Author: Yuri Shilyaev
Tester: Hasan Jaddouh
Editorialist: Daniil Melnichenka

DIFFICULTY:

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.

Access Denied for both codes.

1 Like

Still access denied for both codes. Why?

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.

Optimised brute force passes the test cases.

Solution- https://www.codechef.com/viewsolution/15418296

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