Alarm system - solution

task description

Alarm system had a polynomial time solution although talking with various teams after the contest revealed that there were other creative approaches which were slower but could solve the problem.

Official solution

For the polynomial time solution there are two main tricks to notice:

• The problem can be stated as edge coloring a bipartite graph with three colors: each horizontal and vertical segment is a node in the graph and the empty cells are the edges connecting them. The task was to color the most edges possible with three colors.
• The more subtle trick is to notice that no matter how the edges are selected it is always possible to color them with three colors if no more than three edges meet in a node.

  The edges of an arbitrary bipartite graph with maximum degree n can be colored with n colors by extending the graph into an n-regular bipartite graph (so all the nodes have degree n, which can always be done by adding some extra edges and nodes). In such a graph there always exists a perfect match so using maximum matching algorithm for the coloring works.

  (see the wikipedi article on edge coloring)

The steps of the solution are:

• Build the bipartite graph from the input.
• Use maximum flow algorithm to find the optimal selection of edges (Add an extra source and target node with edges to the two sides of the bipartite graph respectively with edge capacity 3)
• Extend the selected edges so it is a 3-regular bipartite graph.
• Use maximum matching for the first color and remove those edges.
• Use maximum matching again for the second color and remove those edges.
• Remaining selected edges are colored to the third color.
• Prepare the output based on the colored edges.

The largest input had 47488 nodes and 54917 edges and it took about 10 seconds to solve on my laptop (parsing and graph manipulation was in python and it used a separate (HIPR) maximum flow solver written in c).

Alternative solutions

The grotzsch_men team commented that they formulated the problem as an integer linear programming problem and generated a large input for lp_solve. This approach worked but was really slow, the largest input was solved in about half an hour on a very fast machine.

TheTeddyborg said they used backtracking with all sorts of tricky branch cuts.