PROBLEM LINK:Author: Sidhant Bansal DIFFICULTY:mediumhard 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 nonzero element. This is found using the other entries of $B$ (i.e nondiagonal entries). Inference till now  Each of the row of $A$ has at most $1$ nonzero 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 nonzero entry at the same column, whereas if this $B_{i, j} = 0$, it means that the nonzero 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 nonzero entry in the same column. So we add all these edges by iterating over all the nondiagonal, nonzero 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 pairwise 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 nonzero 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
This question is marked "community wiki".
asked 21 Jan '18, 21:48
