Game, Game Everywhere

O(N3) approach

For each pair of indices (i,j) such that i ≤ j, check that if the elements from i to j are non-decreasing. If the amount of such pair is odd then first player will win. Otherwise second player will win.

O(N) approach

We need to find the amount of pair of indices (i,j) such that i ≤ j, and the elements from i to j are non-decreasing. Rest of the work is stated above.

We will try to find segments of the array which are non-overlapping, non-decreasing such that we cannot increasing the size of the segment furthermore. Let's explain with an example:

Let's take an array:
[ 5, 6, 6, 4, 3, 2, 1, 2, 3, 2, 2]
If we partition the array in segments as we stated before:

** (5, 6, 6), (4), (3), (2), (1, 2, 3), (2, 2) **

Now note that for this type of segment, we can choose any pair of indices in the segment and subarray formed from the indices will be a non-decreasing. For a segment of size k we can choose a pair of indices in (k*(k+1))/2 ways.

Back to the example, we have 6 segments of size 3, 1, 1, 1, 3, 2.

So the total number of valid pair of indices is: (3*4)/2 + (1*2)/2 + (1*2)/2 + (1*2)/2 + (2*3)/2 = 12.

So, how do we find this type of segment?
Lets a segment start at st = 1, and end at ed = 1. Now check if the element at index 2 can be added to this segment. Then check if the element at index 3 can be added to this segment. continue the process untill you reach at a index which cannot be added to current segment. So you got a segment. The next segment starts after the ending point of this segment. continue the process untill you reach at the end of the array.