Hints: The Equalizer

Let $S = \sum_i a_i$. In the game with only normal moves (each move decreases the total by $1$), who wins depends only on the parity of $S$.

If $S$ is odd, output YES immediately: the first player wins without needing the special move.

If $S$ is even, consider using the special move once: the array becomes all $k$, so the new total is $n \cdot k$.

If $n \cdot k$ is even, output YES (the special move hands the opponent an even total in the remaining normal game). Otherwise output NO.

Ignore the array structure for a moment and track only the total number of stones $S = \sum a_i$.

If only normal moves are used, each move decreases $S$ by exactly $1$. What decides the winner in such a game?

Answer to Hint 1:
With only normal moves, the game lasts exactly $S$ moves.

• If $S$ is odd, first player wins.
• If $S$ is even, second player wins.

Now include the special move.

Answer to Hint 2:
When Shaunak uses the special move, the whole array becomes all $k$, so the new total is fixed:

$$ S' = n \cdot k. $$

That move consumes his turn (it replaces a normal move).

Answer to Hint 3:
Suppose Shaunak uses the special move immediately on turn $1$.

Then it is Yash’s turn with total $S' = n \cdot k$ and only normal moves left. So:

• if $n \cdot k$ is even, Yash gets an even pile and loses;
• if $n \cdot k$ is odd, Yash wins.

Answer to Hint 4:
So if $n \cdot k$ is even, Shaunak has an instant winning strategy: use special move at once.

If $n \cdot k$ is odd, using special is never helpful (it gives opponent a winning odd total).

Answer to Hint 5:
When special is not useful (or not used), we are back to pure parity of $S = \sum a_i$:

• odd $S$ $\Rightarrow$ first wins,
• even $S$ $\Rightarrow$ first loses.

Final condition:

$$ \text{YES} \iff (n \cdot k \text{ is even}) \;\;\text{or}\;\; \left(\sum a_i \text{ is odd}\right). $$

So per test case we only compute the sum parity and $n \cdot k$ parity. Complexity is $O(n)$ time and $O(1)$ extra space.