PROBLEM LINK:Author: Yuri Shilyaev 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 nonzero 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}$ 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.
This question is marked "community wiki".
asked 20 Aug '17, 14:53

It is not necessary that initial array will always fit for matrix B. So we need to process that also. As for example :
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

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 answered 13 Sep '17, 21:33
