Editorial for ICPC NAQ 2016 E - Dots and Boxes

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Consider the possible unit squares. Each of them can be surrounded by at most $3$ ~3~ line segments, as $4$ ~4~ surrounding line segments form a unit square.
Each unit square starts out with a budget of $3$ ~3~ allowed surrounding line segments, subtract the number of existing line segments that surround it.
Adding a new line segment will reduce the budgets of two adjacent unit squares by $1$ ~1~.

$\text{[math]}$

Adding a line segment can be seen as matching the corresponding adjacent unit squares together.
Each unit square can be matched multiple times (given by its budget), and we want the maximum matching.
This is a standard generalization of maximum matching in a graph.
Key observation: the graph is bipartite (think of the colors on a chessboard).
This type of generalized bipartite matching can be solved using network flow. Similar to the network flow formulation of ordinary bipartite matching, but with modified capacities.
Note: Need to add $1$ ~1~ to answer, as the original problem is posed slightly differently.
Time complexity is $\mathcal O(N^4)$ ~\mathcal O(N^4)~ if Ford-Fulkerson is used.

Comments

There are no comments at the moment.