Can this problem be solved?

Revision en6, by PeterNaut, 2016-12-21 11:26:06

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English PeterNaut 2016-12-29 05:00:29 4 Tiny change: 'hp?prob=10' -> 'hp?prob=10\n\n'
en7 English PeterNaut 2016-12-21 11:26:30 1 Tiny change: 'g answer. \n\nhttp:' -> 'g answer. \n\nhttp:'
en6 English PeterNaut 2016-12-21 11:26:06 1 Tiny change: 'ng answer.\n\nhttp:/' -> 'ng answer. \n\nhttp:/'
en5 English PeterNaut 2016-12-20 07:37:32 2 Tiny change: ' limit is 30 seconds.' -> ' limit is 60 seconds.'
en4 English PeterNaut 2016-12-20 05:14:26 107
en3 English PeterNaut 2016-12-20 05:11:24 43
en2 English PeterNaut 2016-12-20 05:07:20 29 Tiny change: ' solution?\n\nhttp:/' -> ' solution? The time limit is 30 seconds\n\nhttp:/'
en1 English PeterNaut 2016-12-20 05:01:18 241 Initial revision (published)