Internet Problem Solving Contest

• Correct output – F1
• Correct output – F2
• Program solving both data sets

Let A be a boolean matrix of type N x M representing the initial arrangement of the colors, 0 stands for BLUE and 1 stands for RED. Similarly, let B be the matrix representing the final arrangement of the colors. Ann asks if it is possible to transform A to B using only these two kinds of operations: negation of a row, and swap of two columns. We shall construct the transformation. If our construction fails, A cannot be transformed to B.

The solution is based on these clear facts:

1. The order of the performed operations is not important. Therefore we shall assume that the negations are performed first.
2. If A can be transformed to B, each column in A has its corresponding unambiguous counterpart in B (with respect to the operations used in transformation), and vice versa.

Therefore if A and B can be transformed to each other without negating a row, it is sufficient to sort the columns of both matrices using the same sort function. The resulting matrices must be equal.

The author's solution first zeroes the first column of matrix A (it can be done by negating suitable rows). Then it sequentially tries to find a column in matrix B corresponding to A's first column. The B's column being examined is zeroed and columns of both matrices are sorted. If the results match, A and B can be transformed to each other. If none of B's columns corresponds to A's first column, A cannot be transformed to B.

The time complexity of this algorithm is O(NM² log M), space complexity is O(NM).