I'm not particularly proud of the code, since it's rather messy. I spent about 5 days thinking about the algorithm, and I coded it in about 30 min and submitted it, and to my surprise it passed.
I am aware that this is probably the most challenging Facebook puzzle, which is why I was initially reluctant to share the solution. In the end, though, I decided that none of this really matters anyway. It's just 250 lines of poorly written Java code that when compiled and ran against some input produces the expected output, and some bot decides that it's good enough.
Update 03/18: I plan to rewrite this using immutable sets instead of
java.util.BitSet; I was worried that the algorithm is way too slow and thought I'd need to squeeze every bit of performance to pass the bot. I think this optimization is premature.
Fact: the original passing solution had 100 more lines of various preprocessing heuristics; they turned out to be unnecessary, since the current version still passes.