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 line segments, as 4 surrounding line segments form a unit square.
  • Each unit square starts out with a budget of 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.
  • 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 to answer, as the original problem is posed slightly differently.
  • Time complexity is \mathcal O(N^4) if Ford-Fulkerson is used.

Comments

There are no comments at the moment.