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:
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(NM2 log M), space complexity is O(NM).