Editorial for A Farewell to Holds

Model every row and every column as a vertex. Cell $(i,j)$ becomes an edge between the row vertex $R_i$ and the column vertex $C_j$. This edge has color $c_{i,j}$ and value $a_{i,j}$.

So the task is equivalent to the following graph problem: choose a matching of edges to delete, so that after deleting those edges the remaining edge coloring is proper. That means no two edges with the same color are incident to the same vertex. Among all valid choices, minimize the maximum value of a deleted edge.

Let $E$ be the number of edges and $V$ be the number of vertices.

Checking a Fixed Answer

Binary search the answer. Suppose we want to check whether cost at most $w$ is possible.

For every edge $e$, create a Boolean variable $x_e$. Let $x_e = 1$ mean that edge $e$ is deleted, and $x_e = 0$ mean that it remains.

If $a_e > w$, then edge $e$ cannot be deleted, so add the 2-SAT clause:

Now consider the color constraint at one vertex. For each color, look at the incident edges with that color.

If there are at least three such edges, the answer is impossible. At least two of them would need to be deleted, but two deleted edges incident to the same vertex cannot both belong to a matching.

If there are exactly two such edges, say $g$ and $h$, at least one of them must be deleted:

It remains to enforce that the deleted edges form a matching. For every vertex $u$, let its incident edges be:

We need at most one of $x_{e_1}, x_{e_2}, \ldots, x_{e_k}$ to be true. Adding all pairwise clauses would be too slow, so use the standard linear 2-SAT encoding with auxiliary variables $y_1, y_2, \ldots, y_{k-1}$, where $y_i$ means that at least one of $e_1, e_2, \ldots, e_i$ has been deleted.

Add these clauses:

These clauses ensure that once one incident edge of $u$ is deleted, no later incident edge of $u$ can also be deleted.

All constraints are now 2-SAT clauses. Build the implication graph and find strongly connected components. The threshold $w$ is feasible if and only if no variable and its negation are in the same strongly connected component.

Complexity

For a fixed $w$, the number of variables and clauses is $O(E+V)$, because the matching constraints are encoded linearly over all incidences.

The 2-SAT check using SCC also takes $O(E+V)$ time. Binary searching the answer gives total complexity:

If even $w = 10^9$ is infeasible, print No. Otherwise, print Yes and the smallest feasible value of $w$.