I got AC with O(N*N);

Idea: use mathematical induction and prove that solution exist always.
Induction gives a solution.

Good hint!
Furthermore, it can be proved that if it is not 'obviously impossible', then there will always be a solution.