Training Camp
Contest: SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Tags: flows, graphs

You are organizing a training camp to teach algorithms to young kids. There are $$$n^2$$$ kids, organized in an $$$n$$$ by $$$n$$$ grid. Each kid is between $$$1$$$ and $$$n$$$ years old (inclusive) and any two kids who are in the same row or in the same column have different ages.

You want to select exactly $$$n$$$ kids for a programming competition, with exactly one kid from each row and one kid from each column. Moreover, kids who are not selected must be either older than both kids selected in their row and column, or younger than both kids selected in their row and column (otherwise they will complain). Notice that it is always possible to select $$$n$$$ kids satisfying these requirements (for example by selecting $$$n$$$ kids who have the same age).

During the training camp, you observed that some kids are good at programming, and the others are not. What is the maximum number of kids good at programming that you can select while satisfying all the requirements?

Input format:
The first line contains $$$n$$$ ($$$1 \leq n \leq 128$$$) — the size of the grid.

The following $$$n$$$ lines describe the ages of the kids. Specifically, the $$$i$$$-th line contains $$$n$$$ integers $$$a_{i,1}, \, a_{i,2}, \, \dots, \, a_{i, n}$$$ ($$$1 \le a_{i,j} \le n$$$) — where $$$a_{i,j}$$$ is the age of the kid in the $$$i$$$-th row and $$$j$$$-th column. It is guaranteed that two kids on the same row or column have different ages, i.e., $$$a_{i,j} \ne a_{i,j'}$$$ for any $$$1\le i\le n$$$, $$$1\le j < j'\le n$$$, and $$$a_{i,j} \ne a_{i',j}$$$ for any $$$1\le i < i'\le n$$$, $$$1\le j\le n$$$.

The following $$$n$$$ lines describe the programming skills of the kids. Specifically, the $$$i$$$-th line contains $$$n$$$ integers $$$c_{i,1}, \, c_{i,2}, \, \dots, \, c_{i, n}$$$ ($$$c_{i,j} \in \{0, \, 1\}$$$) — where $$$c_{i,j}=1$$$ if the kid in the $$$i$$$-th row and $$$j$$$-th column is good at programming and $$$c_{i,j}=0$$$ otherwise.

Output format:
Print the maximum number of kids good at programming that you can select while satisfying all the requirements.

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

Note:
In the first sample, it is not possible to select the two kids good at programming (in row $$$1$$$ and column $$$1$$$, and in row $$$2$$$ and column $$$3$$$), because then you would have to select the kid in row $$$3$$$ and column $$$2$$$, and in that case two kids would complain (the one in row $$$1$$$ and column $$$2$$$, and the one in row $$$3$$$ and column $$$1$$$).

A valid selection which contains $$$1$$$ kid good at programming is achieved by choosing the $$$3$$$ kids who are $$$1$$$ year old.

In the second sample, there are $$$10$$$ valid choices of the $$$n$$$ kids that satisfy the requirements, and each of them selects exactly $$$2$$$ kids good at programming.

Example input:
3
1 2 3
3 1 2
2 3 1
1 0 0
0 0 1
0 0 0

Example output:
1

Example input:
4
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
1 1 1 0
0 0 1 0
1 1 0 1
0 0 0 1

Example output:
2

Editorial:
In this task, you are given the ages of $$$n^2$$$ kids as a Latin square $$$S$$$ ($$$n \times n$$$ grid such that each row and each column contains all the integers from $$$1$$$ to $$$n$$$), and you are asked to find a subset containing exactly one kid from each row/column, satisfying a certain "stability" constraint, and maximizing the number of kids who are good at programming.
Definitions
• A solution $$$\mu \subseteq \{1, \, \dots, \, n\}^2$$$ is a subset of kids containing exactly one kid from each row/column. For convenience, we will denote $$$\mu_i$$$ the unique $$$j$$$ such that $$$(i, \, j) \in \mu$$$, and $$$\mu^j$$$ the unique $$$i$$$ such that $$$(i, \, j) \in \mu$$$.
• We say that a kid $$$(i, \, j)$$$ is blocking a solution $$$\mu$$$ if the age of $$$(i, \, j)$$$ is between the ages of $$$(i, \, \mu_i)$$$ and $$$(\mu^j, \, j)$$$, that is if $$$(S_{i,j} - S_{i,\mu_i})(S_{i,j} - S_{\mu^j,j}) < 0$$$.
• We say that a solution is stable if there is no blocking kid.
To understand what stability means, we will have a closer look at the second sample. As a first attempt, we can try to draw the graph $$$G$$$ containing pairs of kids who cannot belong to the same solution, either because they are on the same row/column (black edges), or because they would create a blocking kid (gray edges). Kids who are good at programming are colored in gray.
Stable solutions correspond to maximum (cardinality $$$n$$$) independent sets in $$$G$$$, which (unfortunalely) are difficult to compute without additional structure, especially because $$$G$$$ may contain $$$\Theta(n^4)$$$ edges.
Reducing the problem to maximum-weight antichain
We came to the conclusion that we need to understand the structure of $$$G$$$. For that matter, define the directed acyclic graph $$$\vec G$$$, which has an edge from kid $$$a$$$ to kid $$$b$$$ iff they are on the same row/column and $$$a$$$ is younger that $$$b$$$. The graph $$$\vec G$$$ has $$$\Theta(n^3)$$$ edges, and an important observation is that edges of $$$G$$$ corresponds to paths of length $$$\leq 2$$$ in $$$\vec G$$$.
After looking at length-$$$2$$$ paths, we may try to look at longer paths. For that matter, denote $$$\vec G^{(k)}$$$ the $$$k$$$-th power of $$$\vec G$$$, that is the graph which contains an edge from kid $$$a$$$ to kid $$$b$$$ iff $$$\vec G$$$ contains a path of length $$$\leq k$$$ from $$$a$$$ to $$$b$$$. In particular, $$$\vec G^{(2)}$$$ is an orientation of the graph $$$G$$$ defined in the previous section.
Lemma 1. For all $$$k \geq 2$$$, the following properties are satisfied.
1. Any independent set of size $$$n$$$ in $$$\vec G^{(k)}$$$ is a stable solution.
2. Maximum independent sets of $$$\vec G^{(k)}$$$ have size $$$n$$$.
3. Stable solutions are independent sets in $$$\vec G^{(k)}$$$.
Proof. To prove (1), observe that $$$\vec G \subseteq \vec G^{(k)}$$$ (independent sets contain exactly one kid per row/column) and $$$\vec G^{(2)} \subseteq \vec G^{(k)}$$$ (independent sets are stable). To prove (2), observe that a choice of kids having the same age is an independent set, and no set of size $$$> n$$$ can be independent (by the pigeonhole principle, some row/column would contain $$$2$$$ kids). We prove (3) by induction on $$$k$$$. It is true when $$$k = 2$$$ by construction. Now choose the smallest $$$k > 2$$$ such that there is a path $$$a_1 \rightarrow a_2 \rightarrow \cdots \rightarrow a_k$$$ in $$$\vec G$$$ where $$$a_1 \in \mu$$$ and $$$a_k \in \mu$$$ for some stable solution $$$\mu$$$. By minimality of $$$k$$$, we may assume (without loss of generality) that $$$a_1 = (i, \, j') \in \mu$$$, $$$a_2 = (i, \, j) \notin \mu$$$ and $$$a_3 = (i', \, j) \notin \mu$$$. Let $$$a_1' = (\mu^j, \, j) \in \mu$$$ be the kid selected in row $$$j$$$. By stability of $$$\mu$$$, kid $$$a_2$$$ is older than both $$$a_1$$$ and $$$a_1'$$$, therefore there is an edge $$$a_1' \rightarrow a_3$$$, which contradicts the minimality of $$$k$$$. $$$\blacksquare$$$
An antichain of a partially ordered set is a subset of elements such that no pair of elements are comparable (using transitivity). As a corollary of Lemma 1, stable solutions are exactly the maximum antichains of the partial order induced by $$$\vec G$$$. Because antichains are defined using the transitive closure, we can simplify the definition of $$$\vec G$$$ while keeping the same transitive closure, so that there is an edge from kid $$$a$$$ to kid $$$b$$$ iff they are on the same row/column and $$$a$$$ is exactly $$$1$$$ year younger than $$$b$$$. This new definition of $$$\vec G$$$ has $$$\Theta(n^2)$$$ edges, while keeping the property that stable solutions correspond to maximum antichains.
Finally, remember that our goal was to find the "best" stable solution in terms of number of kids who are good at programming. Thus, we give each kid a weight between $$$0$$$ and $$$M=1$$$, and our goal is to find a maximum-weight antichain, under the constraint that it is a maximum-cardinality antichain. We deal with the cardinality constraint by adding a large weight $$$\omega > n\cdot M$$$ to each kid, which reduces our problem to finding the maximum-weight antichain.
Reducing maximum-weight antichain to maximum flow
Finally, we are going to reduce the maximum-weight antichain problem to the maximum flow problem. Define a flow graph $$$\vec F$$$, with two special nodes $$$s$$$ (source) and $$$t$$$ (target), and two copies $$$v_1\in V_1$$$ and $$$v_2\in V_2$$$ of each node $$$v$$$ from $$$\vec G$$$.
• For each node $$$v$$$ of weight $$$w(v)$$$ in $$$\vec G$$$, add two edges $$$s \rightarrow v_1$$$ and $$$v_2 \rightarrow t$$$ with capacity $$$w(v)$$$.
• For each edge $$$u \rightarrow v$$$ in $$$\vec G$$$, add three edges $$$u_1 \rightarrow v_1$$$, $$$u_2 \rightarrow v_2$$$ and $$$u_1 \rightarrow v_2$$$ with infinite capacity.
Using the max-flow min-cut theorem, the maximum $$$s$$$–$$$t$$$ flow is equal to the minimum $$$s$$$–$$$t$$$ cut. Our reduction is easier to understand when looking at cuts (see picture below). Recall that a cut is partition $$$(\mathcal S, \, \mathcal T)$$$ of the nodes, where $$$s\in \mathcal S$$$ and $$$t\in \mathcal T$$$.
• Given an antichain $$$A$$$ in $$$\vec G$$$, denote $$$X$$$ the set of vertices before $$$A$$$ and $$$Y$$$ the set of vertices after $$$A$$$. We define $$$\mathcal S := \{s\} \cup \{v_1 : v\in A\cup Y\} \cup \{v_2 : v\in Y\}$$$ and $$$\mathcal T := \{t\} \cup \{v_1 : v\in X\} \cup \{v_2 : v\in X\cup A\}$$$. The weight of this cut is exactly equal to $$$\sum_{v\notin A} w(v)$$$.
• Conversely, let $$$(\mathcal S, \, \mathcal T)$$$ be a cut of finite weight. We first show that $$$\mathcal S\cap V_1$$$ must be downward closed (if $$$u_1 \in \mathcal S$$$ and $$$u_1 \rightarrow v_1$$$, then $$$v_1\in \mathcal S$$$) and $$$\mathcal T \cap V_2$$$ must be upward closed (if $$$v_2 \in \mathcal T$$$ and $$$u_2 \rightarrow v_2$$$ then $$$u_2\in \mathcal T$$$). Then, $$$A := \{v : v_1\in \mathcal S \: \mathrm{and} \: v_2\in \mathcal T\}$$$ is an antichain, and the cut has weight $$$\sum_{v\notin A} w(v)$$$.
Therefore, computing a maximum weight antichain in $$$\vec G$$$ is equivalent to computing a minimum weight cut in $$$\vec F$$$, which can be done by computing a maximum flow in $$$\vec F$$$. In terms of complexity, $$$\vec F$$$ has $$$2+n^2$$$ nodes and $$$\Theta(n^2)$$$ edges, which should make any reasonable flow algorithm (such as Edmonds-Karp or Dinic's algorithm) efficient enough.
Dilworth's theorem
The reduction from the previous section can be seen as an application of Dilworth's theorem. In the unweighted case, the theorem states that the maximal size of an antichain is equal to the minimum number of paths necessary to cover all elements. Moreover, minimum path cover in a directed acyclic graph can be reduced to maximum cardinality matching in a bipartite graph, which in turn can be reduced to maximum flow.
In the weighted case, a generalization of Dilworth's theorem states that the maximal weight of an antichain is equal to the minimum number of paths needed to cover each element as many times as its weight. Then, this weighted path cover problem can be reduced to maximum flow.
The resulting flow instance is similar to $$$\vec F$$$, however, there is no edge within sets $$$V_1$$$ and $$$V_2$$$, and edges from $$$V_1$$$ to $$$V_2$$$ correspond to the transitive closure of $$$\vec G$$$. This gives a flow instance with $$$\Theta(n^4)$$$ edges, which is too slow for this problem. Observing that we can avoid computing the transitive closure of $$$\vec G$$$ by adding edges within $$$V_1$$$ (and $$$V_2$$$) yields the solution described in the previous section.
Stable matchings
In this editorial, we defined the notions of blocking kids and stable solutions. These choices of terms are deliberate, because this task is in fact a (hopefully well) hidden stable marriage problem.
Lemma 2. Stable solutions are exactly solution of the stable marriage problem where:
• rows have preferences over columns: row $$$i$$$ ranks column $$$j$$$ in $$$M_{i,j}$$$-th position;
• columns have preferences over rows: column $$$j$$$ ranks row $$$i$$$ in $$$(n + 1 - M_{i,j})$$$-th position;
• a row-column pair is blocking if both prefer each other to their respective partners;
• a matching is stable if it contains no blocking pair.
Proof. The only difference between the task statement and the definition of stability given in Lemma 2 is that a kid $$$(i, \, j)$$$ is blocking iff $$$M_{\mu^j,j} < M_{i,j} < M_{i,\mu_i}$$$ (type 1) or $$$M_{i,\mu_i} < M_{i,j} < M_{\mu^j,j}$$$ (type 2), whereas a row-column pair is blocking (in the stable marriage instance) iff $$$M_{\mu^j,j} < M_{i,j} < M_{i,\mu_i}$$$ (type 1). Interestingly, one can show that if a solution has a type 2 blocking kid, then it also has a type 1 blocking kid (left as an exercise). $$$\blacksquare$$$
In the stable marriage problem, one stable matching is optimal for the rows (kids of age $$$1$$$) and one stable matching is optimal for the columns (kids of age $$$n$$$). The set of stable matchings has a distributive lattice structure, which can be represented by closed subsets of a directed graph (closely related to $$$\vec G$$$). The problem of finding a maximum-weight stable matching can be reduced to the closure problem, which can itself be reduced to maximum flow.
Let us finish this editorial with a few fun facts. In the second sample used in this task, $$$n$$$ is a power of $$$2$$$, each kid $$$(i, \, j)$$$ has age $$$1 + (i - 1) \wedge (j - 1)$$$, and the number of stable matchings is given by A005154. This family of instance was first proposed by Donald Knuth, who conjectured that it maximizes the number of stable matchings (still open).