You are not logged in. Please login at www.codechef.com to post your questions!

×

MTRXMOD - Editorial

0
2

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.

This question is marked "community wiki".

asked 20 Aug '17, 14:53

hloya_ygrt's gravatar image

4★hloya_ygrt
119
accept rate: 0%

edited 21 Aug '17, 00:27

admin's gravatar image

0★admin ♦♦
19.8k350498541


Access Denied for both codes.

link

answered 21 Aug '17, 00:51

abdullah768's gravatar image

6★abdullah768
2.5k421
accept rate: 17%

Still access denied for both codes. Why?

link

answered 02 Sep '17, 10:20

bhagatdivesh21's gravatar image

3★bhagatdivesh21
112
accept rate: 0%

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.

link

answered 02 Sep '17, 15:32

ankurparihar's gravatar image

1★ankurparihar
01
accept rate: 0%

edited 02 Sep '17, 17:19

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

link

answered 13 Sep '17, 21:33

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,191
×890
×31
×9

question asked: 20 Aug '17, 14:53

question was seen: 2,059 times

last updated: 30 Dec '17, 02:14