**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