I don't really understand. The fact that, until now, no one's been able to come up with a better algorithm than the one everyone thinks of in 15s is what makes it an interesting conjecture.
It's made more tantalising by the fact that O(n^2) is so much larger than O(n) (the obvious lower bound needed to read the input), which suggests "room" for "something clever to do better".
It's made more tantalising by the fact that O(n^2) is so much larger than O(n) (the obvious lower bound needed to read the input), which suggests "room" for "something clever to do better".