In my icpc regionals they put this problem (link below), but no one came up with a correct solution that runs in time. Does anyone know a solution? The time limit is 60 seconds.

Do you think it can be solved in time? The official solution is a silly heuristic and it is easy to find test cases to make it give wrong answer.

http://localdoc.scusa.lsu.edu/problems-regional/prb.php?prob=10