The problem's description is deceptively simple. It poses at the end a combinatorics problem that is non-trivial. I submitted a correct solution after a bit of research; my first approach was the naive solution.
Given the number of combinatorial optimization problems that are NP-hard, I don't think that gives anything away to anyone who doesn't already know what you're talking about.
