Subtask 1

Note that we only care about the parity of each alpaca's happiness index. For the ~i^\text{th}~ alpaca, we can set ~0~ for an even happiness index and ~1~ for an odd happiness index.

We can then brute force all possible numberings and check if any are valid.

Time Complexity: ~\mathcal{O}(N \cdot 2^N)~

Subtask 2

First, let's consider the case where there is no possible solution.

If ~N-X~ is not even, we can prove that there is no possible numbering. This is because if we start with all alpacas happy and switch the parity of a single alpaca, it causes ~2~ alpacas to become sad. We can observe that it is impossible to increment or decrement the number of happy alpacas by ~1~ when changing the parity of any alpaca; therefore, the only values of ~X~ that yield a possible numbering when given ~N~ are ~N~, ~N-2~, ~N-4~, and so on.

If the input is not of the above mentioned case, the given case has a valid solution.

Using the observation in Subtask 1, we can simply initialize our array with zeroes (all even). Note that at this stage, all alpacas are happy. We observe that if we flip an alpaca from even to odd, we decrease the number of happy alpacas by ~2~. Thus, the number of parity flips we have to make to this array is ~\frac{N-X}{2}~. Note that adjacent flips have no effect and should be avoided for simplicity.

We can now iterate through the array and make ~\frac{N-X}{2}~ parity flips, making sure not to make a flip adjacent to a previous flip.

Time Complexity: ~\mathcal{O}(N)~