Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Utkarsh Gupta
Tester: Satyam, Tejas Pandey
Editorialist: Pratiyush Mishra






Chef and Chefina are playing a game involving N piles where the i^{th} pile (1\le i \le N) has A_i stones initially.

They take alternate turns with Chef starting the game.

In his/her turn a player can choose any non-empty pile (say i^{th} pile) and remove X stones from it iff:

  • Parity of X is same as parity of i.
  • 1 \leq X \leq A_i.

The player who cannot make a move loses. Determine the winner of the game if both players play optimally.


This problem is based on
Sprague-Grundy theorem

Here we first calculate the grundy values of the piles:
Case 1: Odd Piles:
Here we would note that if the pile has odd number of stones then grundy value of the pile would be 1 and if the number of stones is even then grundy value would be 0.

Case 2: Even Piles:
Here the grundy value would be half the number of stones, that is for a pile having n stones, its grundy value would be \lfloor \frac{n}{2} \rfloor

Thus we would calculate the grundy values of all the piles and check the xor-sum of the grundy values.
If the xor-sum is 0, then Chefina would win otherwise Chef would win.


O(N), for each test case.


Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

1 Like

For the following test case:
1 4
the expected output is: CHEF
How is that possible?
For i = 1, we have Ai = 1 (parity match)
For i = 2, we have Ai = 4 (parity match)
So, if chef plays first, he can remove all stones from any one pile, and then chefina removes all stones from the remaining pile. So chefina should win in this case. But the expected output is CHEF. Am I getting something wrong here?

Piles = 1 4
Chef plays, and removes 2 stones from pile 2

Piles = 1 2
Chefina plays, she can remove 1 stone from pile 1, or 2 stones from pile 2

Case 1 – she removes 1 stone from pile 1
Piles = 0 2
Chef plays, he removes 2 stones from pile 2
Piles = 0 0
Chef wins

Case 2 – she removes 2 stones from pile 2
Piles = 1 0
Chef plays, he removes 1 stone from pile 1
Piles = 0 0
Chef wins

1 Like

Why not remove all 4 stones from the pile?
We can remove X stones and 1 <= X <= Ai.

In that case Chef will not win. So We will move in a manner that Chef wins.

Okay. I now understand the question properly. Thank you so much.

1 Like

why my solution is wrong ?