Double Matrix
Contest: Codeforces Round 557 (Div. 2) [based on Forethought Future Cup - Final Round]
Difficulty rating: 1400
Tags: brute force, greedy

You are given two $$$n \times m$$$ matrices containing integers. A sequence of integers is strictly increasing if each next number is greater than the previous one. A row is strictly increasing if all numbers from left to right are strictly increasing. A column is strictly increasing if all numbers from top to bottom are strictly increasing. A matrix is increasing if all rows are strictly increasing and all columns are strictly increasing.

For example, the matrix $$$\begin{bmatrix} 9&10&11\\ 11&12&14\\ \end{bmatrix}$$$ is increasing because each individual row and column is strictly increasing. On the other hand, the matrix $$$\begin{bmatrix} 1&1\\ 2&3\\ \end{bmatrix}$$$ is not increasing because the first row is not strictly increasing.

Let a position in the $$$i$$$-th row (from top) and $$$j$$$-th column (from left) in a matrix be denoted as $$$(i, j)$$$.

In one operation, you can choose any two numbers $$$i$$$ and $$$j$$$ and swap the number located in $$$(i, j)$$$ in the first matrix with the number in $$$(i, j)$$$ in the second matrix. In other words, you can swap two numbers in different matrices if they are located in the corresponding positions.

You would like to make both matrices increasing by performing some number of operations (possibly none). Determine if it is possible to do this. If it is, print "Possible", otherwise, print "Impossible".

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n,m \leq 50$$$) — the dimensions of each matrix.

Each of the next $$$n$$$ lines contains $$$m$$$ integers $$$a_{i1}, a_{i2}, \ldots, a_{im}$$$ ($$$1 \leq a_{ij} \leq 10^9$$$) — the number located in position $$$(i, j)$$$ in the first matrix.

Each of the next $$$n$$$ lines contains $$$m$$$ integers $$$b_{i1}, b_{i2}, \ldots, b_{im}$$$ ($$$1 \leq b_{ij} \leq 10^9$$$) — the number located in position $$$(i, j)$$$ in the second matrix.

Output format:
Print a string "Impossible" or "Possible".

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

Note:
The first example, we can do an operation on the top left and bottom right cells of the matrices. The resulting matrices will be $$$\begin{bmatrix} 9&10\\ 11&12\\ \end{bmatrix}$$$ and $$$\begin{bmatrix} 2&4\\ 3&5\\ \end{bmatrix}$$$.

In the second example, we don't need to do any operations.

In the third example, no matter what we swap, we can't fix the first row to be strictly increasing in both matrices.

Example input:
2 2
2 10
11 5
9 4
3 12

Example output:
Possible

Example input:
2 3
2 4 5
4 5 6
3 6 7
8 10 11

Example output:
Possible

Editorial:
There are too many possibilities to try a brute force, and a dp solution also might be too slow (e.g. some bitmask dp). There is a solution that uses 2sat but that is a bit hard to code so I won't go into details in this tutorial. Let's instead look at a greedy solution.
First, let's swap $$$a_{i,j}$$$ with $$$b_{i,j}$$$ if $$$a_{i,j} > b_{i,j}$$$. At the end, for every $$$i$$$ and $$$j$$$, we have $$$a_{i,j} \leq b_{i,j}$$$. We now claim that there is a solution if and only if this configuration is valid. We can guess this intuitively and by trying a few examples, or we can do the proof below.
<start of formal proof for why this works>
If this configuration is valid, then obviously this solution works, so we're done with this side of the implication.
The other way is to show if there exists a solution, then this configuration is also valid. We do this by contradiction. We show if this configuration is not valid, then there is no solution. If this configuration is not valid, without loss of generality, let $$$b_{i,j} \geq b_{i,j+1}$$$. $$$b_{i,j}$$$ must go somewhere in the matrix and it needs to be before either $$$b_{i,j+1}$$$ or $$$a_{i,j+1}$$$, but we have $$$a_{i,j+1} \leq b_{i, j+1} \leq b_{i,j}$$$, so we have nowhere that we can put $$$b_{i,j}$$$, thus this shows there is no solution. We can also extend this argument to the other cases.
<end of proof for why this works>
So, given the above claim, the solution is simple. Do the swaps so $$$a_{ij} \leq b_{ij}$$$. Then, check if the two matrices are increasing, and print "Possible" if so and "Impossible" otherwise. The runtime is $$$O(n^2)$$$ to read in the input, do the swaps, then do the checks that the matrices are valid.