Help with ACM-ICPC Greater New York Regional Contest problem

Revision en3, by snacache, 2016-08-16 05:56:00

Hi everyone! I was training with some regional contests, and today we (my team) picked the Greater New York Regional Contest 2015.

We managed to solve all but one problem. Here is the link

The statement lacks of constraints, but the official data tests contains cases with at most 600 nodes.

We tried a brute force with no success (obviously, there could be at most 2n possible states).

Can you help me? I read the official solution but I really couldn't understand it, however it doesn't seem very complicated. Maybe I'm missing something.

If you want to check it out, here is the official solution

Thanks!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English snacache 2016-08-16 05:56:00 52 Tiny change: 'ne! I was practicing with s' - (published)
en2 English snacache 2016-08-16 05:54:03 112
en1 English snacache 2016-08-16 05:52:33 705 Initial revision (saved to drafts)