Author: Piyush Mehrotra
Editorialist: Piyush Mehrotra
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming
EXPLANATION:
The game which is given is a simple NIM Game. Player 2 will win only if the XOR of all the piles = 0.
Lets call a segment Valid, if -
- ith pile is in a segment, then all the j’s such that Ai = Aj, are also in the segment.
- Say the segment is from l to r, then there is no Valid segment l1 to r such that l < l1 <= r.
Now we can only have these 2 cases -
- When Valid segments are side by side, i.e., say segments l1 to r1 and l2 and r2, then r1 + 1 = l2
- When Valid segment is totally inside another Valid segment, i.e., say segments l1 to r1 and l2 and r2, l1 < l2 <= r2 < r1
We can make chains of the Valid segments which are side by side.
We can apply Dynamic Programming for these chains. We can store prefix XOR for these chains and whenever 2 Prefix XOR (say for i1 and i2, i1 < i2) is same in a chain, then the elements between i1 and i2 will be a contiguous chain of Valid segments which would have XOR = 0.
We can see that the number of such chains will be O(N), and the sum of number of Valid segments for all the chains will also be O(N).
Depending on the implementation complexity will be O(N) or O(NlogN). We had set the Time Limit such that both of them pass easily.
Author’s Solution can be found here