Inverse of Rows and Columns
Contest: Codeforces Round 555 (Div. 3)
Difficulty rating: 2200
Tags: brute force, constructive algorithms

You are given a binary matrix $$$a$$$ of size $$$n \times m$$$. A binary matrix is a matrix where each element is either $$$0$$$ or $$$1$$$.

You may perform some (possibly zero) operations with this matrix. During each operation you can inverse the row of this matrix or a column of this matrix. Formally, inverting a row is changing all values in this row to the opposite ($$$0$$$ to $$$1$$$, $$$1$$$ to $$$0$$$). Inverting a column is changing all values in this column to the opposite.

Your task is to sort the initial matrix by some sequence of such operations. The matrix is considered sorted if the array $$$[a_{1, 1}, a_{1, 2}, \dots, a_{1, m}, a_{2, 1}, a_{2, 2}, \dots, a_{2, m}, \dots, a_{n, m - 1}, a_{n, m}]$$$ is sorted in non-descending order.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 200$$$) — the number of rows and the number of columns in the matrix.

The next $$$n$$$ lines contain $$$m$$$ integers each. The $$$j$$$-th element in the $$$i$$$-th line is $$$a_{i, j}$$$ ($$$0 \le a_{i, j} \le 1$$$) — the element of $$$a$$$ at position $$$(i, j)$$$.

Output format:
If it is impossible to obtain a sorted matrix, print "NO" in the first line.

Otherwise print "YES" in the first line. In the second line print a string $$$r$$$ of length $$$n$$$. The $$$i$$$-th character $$$r_i$$$ of this string should be '1' if the $$$i$$$-th row of the matrix is inverted and '0' otherwise. In the third line print a string $$$c$$$ of length $$$m$$$. The $$$j$$$-th character $$$c_j$$$ of this string should be '1' if the $$$j$$$-th column of the matrix is inverted and '0' otherwise. If there are multiple answers, you can print any.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2 2
1 1
0 1

Example output:
YES
00
10

Example input:
3 4
0 0 0 1
0 0 0 0
1 1 1 1

Example output:
YES
010
0000

Editorial:
The first observation: if we have an answer where the first row is inverted, we can inverse all rows and columns, then the matrix will remain the same, and the first row is not inverted in the new answer. So we can suppose that the first row is never inverted. Note that this will be true only for slow solution.
The second observation: if we consider a sorted matrix, its first row either consists only of '0's, or has at least one '1' and then all other rows consist only of '1's. This observation can be extended to the following (one user wrote a comment about it and I pinned the link to it above) which can improve time complexity of the solution a lot: in the sorted matrix either the first row consists only of '0's, or the last row consists only of '1's (the corner case is $$$n = 1$$$, but for $$$n=1$$$ we can obtain both answers).
So what should we do with these observations? I will explain a slow solution, a faster solution can be obtained by mirroring one of cases of this one. Let's iterate over the number of '0's in the first row. Let it be $$$cnt$$$. Then the first $$$cnt$$$ elements of the first string should be '0's, and all others should be '1's. We can do it by inverting the columns with elements '1' among first $$$cnt$$$ elements of the first row and columns with elements '0' among remaining elements. So, it's case handling time!
The first case (when $$$cnt < m$$$) is pretty easy. We have to check if all rows from $$$2$$$ to $$$n$$$ that they consist only of '0's or only of '1's (and if some row consists of '0's then we should invert it). If it is true then we found the answer. Otherwise the first row consists only of '0's. So we have to find the "transitional" row (the row with some '0's on the prefix and '1's on the suffix or vice versa). If the number of such rows among all rows from $$$2$$$ to $$$n$$$ is greater than $$$1$$$ then this configuration is bad. If the number of such rows is $$$1$$$ then let $$$idx$$$ be the index of this row. Then we should inverse all rows above it consisting only of '1's and all rows consisting only of '0's below it. And we have to check if the current row is really transitional. We know that its sum is neither $$$0$$$ nor $$$m$$$ so there is at least one '1' and at least '0' in it. If the first element is '1' then let's inverse it. Then we just should check if this row is sorted, and if it is then we found the answer. And the last case is if there are no transitional rows in the matrix. Then we should invert all rows from $$$2$$$ to $$$n$$$ consisting only of '0's (or only of '1's, it does not matter).
So, we have a solution with time complexity $$$O(n^3)$$$. Each number of '0's in the first row is processed in $$$O(n^2)$$$ and there are $$$O(n)$$$ such numbers. But we can see that if we apply the last case (when the number of '0' is $$$m$$$) to the first row and then do the same, but with the last row consisting of $$$m$$$ '1', we can get a solution in $$$O(n^2)$$$.