PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Utkarsh Gupta
Tester: Satyam, Tejas Pandey
Editorialist: Pratiyush Mishra
DIFFICULTY:
2767
PREREQUISITES:
None
PROBLEM:
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.
EXPLANATION:
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.
TIME COMPLEXITY:
O(N), for each test case.
SOLUTION:
Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution
