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

×

FINDA - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sidhant Bansal
Testers: Hasan Jaddouh
Editorialist: Sidhant Bansal

DIFFICULTY:

medium-hard

PREREQUISITES:

Constructive Algorithm, bipartite graph, basic math

PROBLEM:

We will be trying to fill the $A$ matrix row - wise and concentrate on the diagonal elements of $B$ first.

Important Reduction - $A * A^T = B$, basically means that $B_{i, j} = \sum\limits_{k=1}^n(A_{i, k} * A_{j, k})$. Therefore $B_{i, i} = \sum\limits_{k = 1}^n A_{i, k}^2$. This means that if $B_{i, i} = -1$ for any i, then the answer is impossible, since the sum of squares of a given number of integers CANNOT be negative. Similarly if $B_{i, i} = 0$ for any i, then the $i^{th}$ row of $A$ will have all the elements as 0, otherwise the sum of the squares will exceed $0$.

So we are only left with the cases when $B_{i, i} = 1$, in this case, there should be exactly one entry in the $i^{th}$ row of $A$ which is either $1$ or $-1$. For these rows we need to find which column / entry has the non-zero element. This is found using the other entries of $B$ (i.e non-diagonal entries).

Inference till now - Each of the row of $A$ has at most $1$ non-zero entry.

So if $B_{i, j} \neq 0$, for a given $i, j$, where $i \neq j$, it means that the $i^{th}$ and $j^{th}$ row of $A$ have the non-zero entry at the same column, whereas if this $B_{i, j} = 0$, it means that the non-zero entries of the both the rows are in different column. So for all $i, j$ where $B_{i, j} \neq 0$ we add an edge between $i^{th}$ and $j^{th}$ node in a graph $G$. This edge denotes that the $i^{th}$ and $j^{th}$ row should have the non-zero entry in the same column. So we add all these edges by iterating over all the non-diagonal, non-zero entries of $B$.

The resultant graph will now have some connected components. Each of these components will be allocated a single column.

Beware - You need to make a lot of checks for invalid cases. First check if $B$ is symmetric or not, i.e $B_{i, j}$ should be equal to $B_{j, i}$ for all $i, j$. Secondly, check that there should be no $B_{i, j} \neq 0$ where $B_{i, i} = 0$ or $B_{j, j} = 0$. Thirdly check that all the components are complete, i.e all the nodes in a component must have a pair-wise edge.

We now see the focus on wether $B_{i, j} = 1$ or $B_{i, j} = -1$ whenever $B_{i, j} \neq 0$. If $B_{i, j} = 1$ it means that non-zero entry in the $i^{th}$ row and the $j^{th}$ row will have the same integer, i.e either both are $1$ or both are $-1$. Incase, $B_{i, j} = -1$ it means that the entries are of opposite sign. Now you can notice that if $B_{a, b} = -1, B_{b, c} = -1, B_{a, c} = -1$, then the graph is invalid, this is because there is no way to assign values to the $a, b$ and $c$ row in such a way that all the products are -1 (i.e they all have different signs pairwise). More formally, if we make a new graph, $H$ where we add an edge between $x$ and $y$ if $B_{x, y} = -1$, then this graph should be bipartite (i.e should not have any odd length cycle). So if any of the components is NOT bipartite then the matrix is impossible.

Therefore, we have reduced that all the components need to be bipartite. Now you will divide this bipartite graph into 2 sides (i.e left and the right) where all the nodes on one side will get $+1$ and the nodes on the other side will get $-1$.

Since we have to make the lexicographically smallest A, we will start from row $1$ assign its entire component in $G$ to column $1$ and assign $-1$ to the side to which node $1$ belongs to in $H$ and assign $+1$ to the opposite side $H$. Now we will move on to the next smallest row unassigned column. Example - Let the next unassigned row be $5^{th}$ row, then we would assign its entire component in $G$ to column $2$ and assign $-1$ to the side to which $5$ belongs in $H$ and assign $+1$ to the opposite side in $H$.

The entire solution requires $O(N^2)$ time and space complexity, which should pass easily under the given constraints.

SOLUTIONS

Setter's solution.
Tester's solution.

This question is marked "community wiki".

asked 21 Jan '18, 21:48

sidhant007's gravatar image

6★sidhant007
179819
accept rate: 12%

edited 22 Jan '18, 15:35

admin's gravatar image

0★admin ♦♦
19.8k350498541


@admin

Links to setter's and tester's solutions are redirecting me to their profile pages. Please update this.

link

answered 22 Jan '18, 12:30

hruday968's gravatar image

4★hruday968
1.7k210
accept rate: 14%

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,680
×1,250
×1,186
×202
×97
×82
×4

question asked: 21 Jan '18, 21:48

question was seen: 904 times

last updated: 22 Jan '18, 15:35