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