PROBLEM LINK:
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.