PROBLEM LINK:
Author: Raghav Vashishth
Tester: Arjun Kathail
Editorialist: Tushar Malik
DIFFICULTY:
Medium
PREREQUISITES:
Nim-Sum, Difference Array
PROBLEM:
It is the festival of Holi and Chef and his friends are playing an interesting game. There are N buckets numbered from 0 to N−1, each of these buckets is initially empty. Now each of Chef’s friends will provide a total of Q queries, where each query gives a range of buckets from L to R and a value X which is the number of water balloons that must be added to each of these buckets from L to R both included.
Now Chef and one of his friends are challenged to play a two-player game taking turns, In each turn, a player can choose only one bucket and remove any number of water balloons (at least one) from that bucket. The player who cannot move is considered to lose the game (i.e., one who take the last water balloons is the winner). Chef will only play the game if he is certain that he will win and so he asks you to confirm the same.
Assume that both the players play the game optimally.
QUICK EXPLANATION:
If both A and B play optimally (i.e- they don’t make any mistakes), then the player starting first is guaranteed to win if the Nim-Sum at the beginning of the game is non-zero. Otherwise, if the Nim-Sum evaluates to zero, then player A will lose definitely.
Nim-Sum : The cumulative XOR value of the number of baloons in each bucket at any point of the game is called Nim-Sum at that point.
EXPLANATION
For finding the number of balloons in each bucket after the end of all queries in constant time, we will use the concept of Difference array. Otherwise, using a normal loop to do that would take O(n) time and will result in a TLE.
Difference array D[i] of a given array A[i] is defined as D[i] = A[i]-A[i-1] (for 0 < i < N ) and D[0] = A[0] considering 0 based indexing. Difference array can be used to perform range update queries “l r x” where l is left index, r is right index and x is value to be added and after all queries you can return original array from it. Where update range operations can be performed in O(1) complexity.
- update(l, r, x) : Add x to D[l] and subtract it from D[r+1], i.e., we do D[l] += x, D[r+1] -= x
- printArray() : Do A[0] = D[0] and print it. For rest of the elements, do A[i] = A[i-1] + D[i] and print them.
Time complexity of update here is improved to O(1).
This game depends on two factors-
- The player who starts first.
- The initial configuration of the baloons.
Initially two cases could exist.
Case 1: Initial Nim Sum is zero
As we know, in this case if played optimally B wins, which means B would always prefer to have Nim sum of zero for A‘s turn.
So, as the Nim Sum is initially zero, whatever number of items A removes the new Nim Sum would be non-zero (as mentioned above). Also, as B would prefer Nim sum of zero for A‘s turn, he would then play a move so as to make the Nim Sum zero again (which is always possible, as mentioned above).
The game will run as long as there are items in any of the buckets and in each of their respective turns A would make Nim sum non-zero and B would make it zero again and eventually there will be no elements left and B being the one to pick the last wins the game.
It is evident by above explanation that the optimal strategy for each player is to make the Nim Sum for his opponent zero in each of their turn, which will not be possible if it’s already zero.
Case 2: Initial Nim Sum is non-zero
Now going by the optimal approach A would make the Nim Sum to be zero now (which is possible as the initial Nim sum is non-zero, as mentioned above). Now, in B‘s turn as the nim sum is already zero whatever number B picks, the nim sum would be non-zero and A can pick a number to make the nim sum zero again. This will go as long as there are items available in any buckets.
And A will be the one to pick the last item.
So, as discussed in the above cases, it should be obvious now that Optimal strategy for any player is to make the nim sum zero if it’s non-zero and if it is already zero then whatever moves the player makes now, it can be countered.
Let us apply the above theorem in an example case. In the first game A started first and the Nim-Sum at the beginning of the game was, 3 XOR 4 XOR 5 = 2, which is a non-zero value, and hence A won. Whereas in the second game-play, when the initial configuration of the piles were 1, 4, and 5 and A started first, then A was destined to lose as the Nim-Sum at the beginning of the game was 1 XOR 4 XOR 5 = 0 .
SOLUTIONS:
Setter’s Solution
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,q;
cin>>n>>q;
int arr[n+1]{0};
int l,r,x;
for(int i=0;i<q;i++){
cin>>l>>r>>x;
arr[l]+=x;
arr[r+1]-=x;
}
for(int i=1;i<n;i++){
arr[i]+=arr[i-1];
}
int xr=0;
for(int i=0;i<n;i++){
xr^=arr[i];
}
if(xr==0){
cout<<2<<endl;
}else cout<<1<<endl;
}
return 0;
}