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!
Auto comment: topic has been updated by snacache (previous revision, new revision, compare).
I have seen this task already few times and it is really nice. Note that in order for all robots to meet in some place you need to be able to find such a sequence for every pair of robots. Reverse statement happends to be true, because imagine you did some operations and robots are present in some subset of vertices. You can take two of those vertices and perform a sequence of operations so that they will meet which will shrink a size of our subset and perform it while its size is >1. That equivalent condition can be easily checked by means of creating a graph of pairs of vertices and checking whether every vertex is reachable from some vertex of form (i, i).
Wow! Thanks! But if there were, let's say 3 colors, would it work too?
Sure, no matter the number of colors, we will need to create a graph on pairs not on triples or anything, it just increases number of edges in our graph what should be clear if you got the solution.