Elongated Matrix
Contest: Codeforces Round 531 (Div. 3)
Difficulty rating: 2000
Tags: binary search, bitmasks, brute force, dp, graphs

You are given a matrix $$$a$$$, consisting of $$$n$$$ rows and $$$m$$$ columns. Each cell contains an integer in it.

You can change the order of rows arbitrarily (including leaving the initial order), but you can't change the order of cells in a row. After you pick some order of rows, you traverse the whole matrix the following way: firstly visit all cells of the first column from the top row to the bottom one, then the same for the second column and so on. During the traversal you write down the sequence of the numbers on the cells in the same order you visited them. Let that sequence be $$$s_1, s_2, \dots, s_{nm}$$$.

The traversal is $$$k$$$-acceptable if for all $$$i$$$ ($$$1 \le i \le nm - 1$$$) $$$|s_i - s_{i + 1}| \ge k$$$.

Find the maximum integer $$$k$$$ such that there exists some order of rows of matrix $$$a$$$ that it produces a $$$k$$$-acceptable traversal.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 16$$$, $$$1 \le m \le 10^4$$$, $$$2 \le nm$$$) — the number of rows and the number of columns, respectively.

Each of the next $$$n$$$ lines contains $$$m$$$ integers ($$$1 \le a_{i, j} \le 10^9$$$) — the description of the matrix.

Output format:
Print a single integer $$$k$$$ — the maximum number such that there exists some order of rows of matrix $$$a$$$ that it produces an $$$k$$$-acceptable traversal.

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

Note:
In the first example you can rearrange rows as following to get the $$$5$$$-acceptable traversal:

Then the sequence $$$s$$$ will be $$$[5, 10, 4, 9, 3, 8, 3, 9]$$$. Each pair of neighbouring elements have at least $$$k = 5$$$ difference between them.

In the second example the maximum $$$k = 0$$$, any order is $$$0$$$-acceptable.

In the third example the given order is already $$$3$$$-acceptable, you can leave it as it is.

Example input:
4 2
9 9
10 8
5 3
4 3

Example output:
5

Example input:
2 4
1 2 3 4
10 3 7 3

Example output:
0

Editorial:
Really low constraints, choosing some permutation... Surely, this will be some dp on subsets!
At first, let's get rid of $$$m$$$. For each two rows calculate the minimum difference between the elements of the same columns — let's call this $$$mn1_{i, j}$$$ for some rows $$$i$$$, $$$j$$$. This will be used to put row $$$j$$$ right after row $$$i$$$. Let's also calculate $$$mn2_{i, j}$$$ — the minimum difference between the elements of the column $$$k$$$ of row $$$i$$$ and column $$$k + 1$$$ of row $$$j$$$. This will be used to put row $$$i$$$ as the last row and row $$$j$$$ as the first one.
Now let's think of choosing the permutation as choosing the traversal of the following graph. Vertices are rows and the weights of edges between the vertices are stored in $$$mn1$$$. However, you can't straight up do minimum weight Hamiltonian cycle search as the edge between the first vertex and the last one should be of weight from $$$mn2$$$ and not $$$mn1$$$.
Let's fix some starting vertex and find minimum weight Hamiltonian paths from it to all vertices. Finally, update the answer with $$$min(mn2_{u, v}, path_{v, u})$$$. That will lead to $$$2^n \cdot n^3$$$ approach (minimum weight Hamiltonian path is a well-known problem solved by $$$dp[mask of used vertices][last visited vertex]$$$).
That's completely fine and it's the most intended solution.
However, there exist another solution that would have worked better if the edge weight were a bit smaller.
Let's do binary search, each time checking if the answer is greater or equal to $$$mid$$$. The check is simple enough. Now the graph is binary (edge exists if its weight is greater or equal to $$$mid$$$), thus you should check for existence of Hamiltonian path, not for the minimum weight one. That can be done in $$$O(2^n \cdot n^2)$$$, leading to $$$O(2^n \cdot n^2 \log MAXN)$$$ solution. The key idea of that dp is storing the vertices where the path of the current mask could have ended as a mask itself. Then it becomes $$$dp[mask]$$$ with $$$n$$$ transitions.
Overall complexity: $$$O(2^n \cdot n^3)$$$ or $$$O(2^n \cdot n^2 \log MAXN)$$$.