One Billion Shades of Grey
Contest: Codeforces Global Round 11
Difficulty rating: 3300
Tags: flows, graphs

You have to paint with shades of grey the tiles of an $$$n\times n$$$ wall. The wall has $$$n$$$ rows of tiles, each with $$$n$$$ tiles.

The tiles on the boundary of the wall (i.e., on the first row, last row, first column and last column) are already painted and you shall not change their color. All the other tiles are not painted. Some of the tiles are broken, you shall not paint those tiles. It is guaranteed that the tiles on the boundary are not broken.

You shall paint all the non-broken tiles that are not already painted. When you paint a tile you can choose from $$$10^9$$$ shades of grey, indexed from $$$1$$$ to $$$10^9$$$. You can paint multiple tiles with the same shade. Formally, painting the wall is equivalent to assigning a shade (an integer between $$$1$$$ and $$$10^9$$$) to each non-broken tile that is not already painted.

The contrast between two tiles is the absolute value of the difference between the shades of the two tiles. The total contrast of the wall is the sum of the contrast of all the pairs of adjacent non-broken tiles (two tiles are adjacent if they share a side).

Compute the minimum possible total contrast of the wall.

Input format:
The first line contains $$$n$$$ ($$$3\le n\le 200$$$) – the number of rows and columns.

Then $$$n$$$ lines, each containing $$$n$$$ integers, follow. The $$$i$$$-th of these lines describe the $$$i$$$-th row of tiles. It contains the $$$n$$$ integers $$$a_{ij}$$$ ($$$-1\le a_{ij} \le 10^9)$$$. The value of $$$a_{ij}$$$ described the tile on the $$$i$$$-th row and $$$j$$$-th column:

- If $$$a_{ij}=0$$$, then the tile is not painted and shall be painted.
- If $$$a_{ij}=-1$$$, then the tile is broken and shall not be painted.
- If $$$1\le a_{ij}\le 10^9$$$, then the tile is already painted with the shade $$$a_{ij}$$$.

Output format:
Print a single integer – the minimum possible total contrast of the wall.

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

Note:
Explanation of the first testcase: The initial configuration of the tiles is (tiles to paint are denoted by ?):

1 7 64 ? 61 1 1

1 7 64 5 61 1 1

Explanation of the second testcase: Since all tiles are either painted or broken, there is nothing to do. The total contrast is $$$396$$$.

Explanation of the third testcase: The initial configuration of the tiles is (tiles to paint are denoted by ?):

6 6 5 4 46 ? ? ? 47 ? ? ? 38 ? ? ? 28 8 1 2 2

6 6 5 4 46 6 5 4 47 7 5 3 38 8 2 2 28 8 1 2 2

Example input:
3
1 7 6
4 0 6
1 1 1

Example output:
26

Example input:
3
10 100 1
1 -1 100
10 10 10

Example output:
396

Editorial:
We present two solutions: the first solution is mine, the second is by dacin21.
• The first solution reduces the problem to the computation of $$$O(n)$$$ min-cuts and then computes the min-cuts with total complexity $$$O(n^3)$$$. This solution requires no advanced knowledge and it fits easily in the time-limit.
• The second solution solves the dual of the problem, which happens to be a min-cost flow. This shall be implemented with complexity $$$O(n^3)$$$ (or $$$O(n^3\log(n))$$$ and some optimizations) to fit in the time-limit.
We will solve the problem on a general graph (tiles = vertices, two tiles are adjacent if there is an edge between them).
Solution via many min-cuts
The solution is naturally split in two parts:
• Reduce the problem to the computation of $$$O(n)$$$ min-cuts in the grid-graph (here $$$O(n)$$$ represents the number of already painted tiles).
• Compute all the min-cuts with overall complexity $$$O(n^3)$$$.
Reducing to many min-cuts
A natural way to come up with this solution is to consider the special case in which the painted tiles have only two colors. In such a case the problems is clearly equivalent to the min-cut. We show that something similar holds true in general.
Given a graph $$$(V, E)$$$, let $$$B$$$ be the set of vertices that are already painted (in our problem, $$$B$$$ contains the tiles on the boundary). Let us fix a choice of all the shades, that is a function $$$s:V\to\mathbb N$$$ such that $$$s(v)$$$ is the shade assigned to vertex $$$v$$$. Let TC be the total contrast. We have (using that, for $$$x\le y$$$, it holds $$$|x-y|=\sum_{k\ge 1}[x\le k\text{ and } y > k]$$$) $$$$$$\texttt{TC} = \sum_{(u,v)\in E} |s(u)-s(v)| = \sum_{k\ge 1} \#\{(u,v)\in E:\ s(u)\le k,\, s(v)>k\} \,.$$$$$$ Given two disjoint subsets $$$U_1, U_2$$$ of vertices, let $$$mc(U_1, U_2)$$$ be the minimum-cut between these two set of vertices. Using the formula above, we have $$$$$$\texttt{TC} = \sum_{k\ge 1} mc(\{v\in V: s(v)\le k\}, \{v\in V: s(v)>k\}) \ge \sum_{k\ge 1} mc(\{v\in B: s(v)\le k\}, \{v\in B: s(v)>k\})\,.$$$$$$ Therefore, we have proven a lowerbound for the minimum total contrast. Let us show that this lowerbound can be achieved.
Given two disjoint subsets $$$U_1,U_2$$$, let $$$\mathcal{MC}(U_1,U_2)$$$ be the family of all the subsets $$$U_1\subseteq W\subseteq V\setminus U_2$$$ such that $$$mc(U_1, U_2)=mc(W,V\setminus W)$$$, i.e. the family of subsets achieving the minimum-cut. We are going to need the following lemma. Even though the proof is unilluminating, the statement is very intuitive.
Lemma: Take $$$U_1,U_2$$$ disjoint and $$$\tilde U_1,\tilde U_2$$$ disjoint, such that $$$U_1\subseteq \tilde U_1$$$ and $$$\tilde U_2\subseteq U_2$$$ (that is, $$$U_1$$$ grows and $$$U_2$$$ shrinks). If $$$W\in \mathcal{MC}(U_1,U_2)$$$ and $$$\tilde W\in \mathcal{MC}(\tilde U_1, \tilde U_2)$$$, then $$$W\cup \tilde W\in \mathcal{MC}(\tilde U_1, \tilde U_2)$$$.
proof. Given two disjoint sets $$$A,B\subseteq V$$$, let $$$c(A,B):=|(A\times B)\cap E|$$$ be the number of cross-edges. It holds (without using any assumption on $$$W$$$ or $$$\tilde W$$$) $$$$$$ c(W\cup \tilde W, (W\cup \tilde W)^c) - c(\tilde W, \tilde W^c) = c(W\setminus \tilde W, (W\cup \tilde W)^c) - c(\tilde W, W\setminus\tilde W) \\ \quad\quad\quad\le c(W\setminus \tilde W,W^c) - c(W\cap \tilde W, W\setminus \tilde W) = c(W,W^c) - c(W\cap \tilde W, (W\cap \tilde W)^c)\,. $$$$$$ Since $$$W\in\mathcal MC(U_1,U_2)$$$ and $$$U_1\subseteq W\cap\tilde W\subseteq U_2^c$$$, the right-hand side is nonpositive. Hence also the left-hand side is nonpositive; thus we deduce $$$c(W\cup \tilde W, (W\cup \tilde W)^c) \le c(\tilde W, \tilde W^c)$$$ and therefore $$$W\cup\tilde W\in\mathcal{MC}(\tilde U_1, \tilde U_2)$$$.
Applying the lemma, we may find an increasing family of subsets $$$W_1\subseteq W_2\subseteq W_3\subseteq \cdots$$$ such that for all $$$k\ge 1$$$ it holds $$$$$$ W_k\in \mathcal{MC}(\{v\in B: s(v)\le k\}, \{v\in B: s(v)>k\}) \,.$$$$$$ It is easy to check that $$$s(v):=\min\{k: v\in W_k\}$$$ is a valid assignment of shades that achieves the minimum possible contrast (that is, it achieves equality in the formula above).
Hence, we may solve the problem running many maximum-flow algorithms. Running $$$O(n)$$$ times a max-flow algorithm should get time-limit-exceeded independently on how good your implementation of the maximum-flow is.
Remark. For those interested, the relation between min-cuts and the minimization of the contrast is very similar to the relation between the isoperimetric problem and the 1-Sobolev inequality (see this wiki page). In the continuous setting, the strategy employed in this solution corresponds to the coarea formula.
Computing quickly many min-cuts
Our goal is computing $$$mc(\{v\in B: s(v)\le k\}, \{v\in B: s(v)>k\})$$$ for all values of $$$k$$$. The number of interesting values of $$$k$$$ is clearly $$$O(n)$$$. For simplicity, we assume that the interesting values of $$$k$$$ are contiguous and that all the tiles on the boundary have different shades.
Let us assume that we have computed, via a simple augmenting-path algorithm, a max-flow between $$$\{v\in B: s(v)\le k\}$$$ and $$$\{v\in B: s(v)> k\}$$$. In particular we are keeping the flow as a union of disjoint paths. We show how to update it to a max-flow between $$$\{v\in B: s(v)\le k+1\}$$$ and $$$\{v\in B: s(v)> k+1\}$$$ in $$$O(n^2)$$$ time (thus the overall complexity will be $$$O(n^3)$$$).
Passing from $$$k$$$ to $$$k+1$$$ we only need to transform a sink into a source (in particular the vertex such that $$$s(v)=k+1$$$ becomes a source). How shall we do that?. First of all we remove all the paths that ends in $$$v$$$ (there are at most $$$3$$$, which is the degree of $$$v$$$). Then we look for augmenting paths. Due to the optimality of the flow before the update, it is not hard to prove that there can be at most $$$6$$$ augmenting paths. The overall complexity of the update is $$$3n^2 + 6n^2 = O(n^2)$$$.
Solution via min-cost flow
The crucial point is formulating the problem as a linear programming problem and computing its dual, which somewhat magically turns out to be a min-cost flow. Then a very careful implementation of the min-cost flow algorithm is necessary to get accepted (with some optimizations, it is possible to get accepted with execution time below $$$1$$$ second).
Let $$$x_v$$$ be the shade of vertex $$$v$$$. For any edge $$$u\sim v$$$, let $$$c_{uv}$$$ be the contrast between $$$u$$$ and $$$v$$$. Then we have $$$$$$ c_{uv} \ge x_u-x_v \quad \text{ and }\quad c_{uv}\ge x_v-x_u \,, $$$$$$ and the total contrast is $$$ \sum c_{uv}$$$.
Hence, we have formulated the minimization of the total contrast as a linear programming problem. In this form, it's not clear how to solve it efficiently (the simplex algorithm would be way to slow).
Computing the dual problem is straight-forward (using well-known formulas) but a bit heavy on notation. In the end, the dual problem turns out to be the min-cost flow with the following parameters:
• There is a source, connected to all the vertices $$$v$$$ already painted via an edge (from the source to $$$v$$$) with capacity $$$1$$$ and cost $$$x_v$$$.
• There is a sink, connected to all the vertices $$$v$$$ already painted via an edge (from $$$v$$$ to the sink) with capacity $$$1$$$ and cost $$$-x_v$$$.
• All the edges of the graph have capacity $$$1$$$ and cost $$$0$$$.
• Remove the edges between already painted vertices (taking care of the contrast generated by adjacent painted vertices).
• Use a radix-heap instead of a standard heap for Dijkstra.