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 steps of the solution are:

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.