PROBLEM LINK:
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.