CF Global Round 11 - One Billion Shades of Grey

Official Editorial

I assume that you've

• heard of linear programming duality
• read the parts of the editorial mentioning min-cost flow

This explanation is meant to clarify how the min-cost flow graph is derived.

Essentially, we want to find the best possible lower bound on the answer, which turns out to be equal to the answer by duality.

As the editorial mentions, you want to minimize $\sum c_{u,v}$ subject to some inequalities of the form

Each $c_{u,v}\ge 0$, and some $x_u$ are fixed (for tiles on the boundary) while the others are unbounded (if we ignore the constraint that each $x_i\in [1,10^9]$). Essentially, to find we want a linear combination of these equations

such that the following conditions are satisfied.

• Each $a_{u,v}$ corresponds to the flow on an edge of the min-cost flow graph, so these must be non-negative.
• On the LHS of $\text{Eq}$, no $c_{u,v}$ has coefficient greater than one. This corresponds to $a_{u,v}+a_{v,u}\le 1$, meaning that the flow on each edge of the min-cost flow graph is at most $1$.
• The coefficients of each non-constant $x_u$ on the RHS of $\text{Eq}$ are zero. This means that in the min-cost flow graph, each vertex (aside from the source and the sink) has the same in-flow as out-flow.
• The constant on the right side is maximized (we want the best possible lower bound).

Example: (should hopefully clarify the above)

Suppose that

and that $x_i=i$ for each $1\le i\le 4$ while $x_5$ is unbounded. What is the minimum possible value of

Solution: In this case, the answer is $4-1=3$. We can show that this is a lower bound by choosing

Then we get the linear combination

It follows that

This corresponds to a min cost flow graph with $5$ vertices plus a source and a sink where all edges have capacity $1$.

• Draw edges from $4$ to $5$, $2$ to $5$, $5$ to $1$, and $5$ to $3$ with cost $0$.
• Drawing edges from the source to vertex $4$ with cost $4$ and from the source to vertex $2$ with cost $2$.
• Drawing edges from vertex $3$ to the sink with cost $-3$ and from vertex $1$ to the sink with cost $-1$.
• Finding the maximum cost flow from the source to the sink. In this case, we just send one unit of flow from

In the original problem the edges go both ways (not just one way), but the idea is similar.