The 4th is definitively the funniest.
In addition to the disclaimer, one thing which worried me was the N <= 1000 in the large problem specification. I got a quite elegant fast solution and a so low bound was really surprising.
In addition to the disclaimer, one thing which worried me was the N <= 1000 in the large problem specification. I got a quite elegant fast solution and a so low bound was really surprising.
That should probably be a few orders of magnitude higher to realistically make the time constraint remotely difficult.
This was a fun problem to think about, though. Naomi is such a cheater.