## 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.