Editorial : The Equalizer

This section matches the implementation in model_sol.cpp.

Let $S = \sum_{i=1}^{n} a_i$. With only normal moves, each move decreases the total by $1$, so the game lasts $S$ moves: odd $S$ means the first player wins, even $S$ means the second player wins.

The special move replaces the whole array by $k$ everywhere, so after using it the total is $n \cdot k$, and it is then the opponent’s turn with only normal moves left. If $n \cdot k$ is even, that opponent loses in the pure parity game, so playing the special move immediately wins; if $n \cdot k$ is odd, using the special move is never better than avoiding it.

Therefore the first player should answer YES exactly when $S$ is odd (win without special) or when $n \cdot k$ is even (win by using special at once). Equivalently, answer NO only when $S$ is even and $n \cdot k$ is odd. The program computes the parity of $S$ and of $n \cdot k$ in $O(n)$ time to read and sum the array.

Let

If we never use the special move, every move decreases $S$ by exactly $1$, so the number of moves is exactly $S$:

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

Now consider the special move. If Shaunak uses it, the array becomes $[k, k, \dots, k]$, so the total becomes

This move replaces his turn, so immediately after using it, it is Yash’s turn with total $S'$ and no more special effects to consider.

• If $S'$ is even, the player to move (Yash) loses in the normal decrement game, so Shaunak can force a win by using special immediately.
• If $S'$ is odd, using special gives Yash a winning position, so it is never beneficial.

Therefore:

For each test case:

• Time: $O(n)$ to read and sum the array.
• Extra space: $O(1)$.