Prerequisites

First of all, if you have not learnt about Grundy numbers in combinatorial game theory, you can read the following blog on Codeforces: https://codeforces.com/blog/entry/66040.

In the following editorial \(\oplus\) represents the bitwise XOR operation. If you don’t know about the bitwise XOR operation, consider not attempting this problem using the Grundy numbers approach and coming back later.

In the following editorial MEX of a list of numbers represents the smallest non-negative integer that is not present in the list. If you don’t know about MEX, consider not attempting this problem using the Grundy numbers approach and coming back later.

The basic idea

The following is a solution that uses Grundy numbers, that is, finding all \(g_0, g_1 , g_2, \dots, g_N\)​ , where \(g_N\) ​ is the Grundy number when there are only \(N\) consecutive integers on the table. If the table contains \(k\) consecutive unmarked segments, each having \(a_1, a_2, \dots, a_k\) consecutive integers, then the state is winning if and only if \(g_{a_1} \oplus g_{a_2} \oplus \dots \oplus g_{a_k} > 0\).

The initial state has \(k=1\) and \(a_1=N\). Therefore, if \(g_N>0\), play as the first player. Else, play as the second player. Now, we are left with two questions:

1. How do we calculate the \(g_i\) values?
2. Assuming we have all the \(g_i\) values calculated, how do we make a move?

Calculating \(g_i\) values in \(O(N^2 \log N)\) time

In the official editorial, the naive way to calculate all \(g_i\) values uses \(O(N^2(R-L))\) time. Here we present a solution that uses \(O(N^2 \log N)\) time.

Firstly, we shall prove that \(g_i \le i\) for all \(0 \le i \le N\).

\(g_0 = 0 \le 0\), so the statement is true for \(i=0\).

Assume \(g_j \le j\) for \(0 \le j \le i-1\). We must show that \(g_i \le i\) is also true.

To find \(g_i\), we want to find the MEX of \(g_u \oplus g_v\) satisfying \(u+v=i-y\), where \(L \le y \le R\) and \(0 \le u,v\). Since \(g_u \oplus g_v \le g_u + g_v\), on the assumption that \(g_j \le j\) for \(0 \le j \le i-1\), we have:

\(g_u \oplus g_v \le g_u + g_v \le u + v = i-y\)

The maximum of \(g_u \oplus g_v\) does not exceed \(i-y\). Since \(y \ge 1\), the MEX of \(g_u \oplus g_v\) satisfying \(u+v=i-y\) does not exceed \(i-1+1=i\). Therefore, \(g_i \le i\).

This shows that \(g_i \le i\) is true whenever \(g_j \le j\) is true for \(0 \le j \le i-1\). This completes the inductive step of the proof. Therefore \(g_i \le i\) for all \(0 \le i \le N\).

How can we make use of the above property to calculate the Grundy numbers?

Recall that, to find \(g_i\), we want to find the MEX of \(g_u \oplus g_v\) satisfying \(u+v=i-y\), where \(L \le y \le R\) and \(0 \le u,v\).

Since \(g_i \le i\), \(g_u \oplus g_v \le 2 \times N\) for any arbitrary \(u,v\) satisfying \(0 \le u,v \le N\). So let’s make \(2 \times N + 1\) vectors (C++), vector \(w\) (\(0 \le w \le 2 \times N\)) storing the list of pairs of \((u,v)\) such that \(g_u \oplus g_v = w\), sorted by ascending \(u+v\).

Now, to find \(g_i\), iterate over \(val=0,1,\dots\). it is guaranteed that the MEX will be found by the time all \(val \le i\) has been iterated. Now, for each \(val\), we check in the vector \(val\), use lower bound to find if there is any pair with \(u+v \ge i-R\) and \(u+v \le i-L\) and \(g_u \oplus g_v = val\). If there is, then \(val\) is not the MEX and we increment it by \(1\). If there isn’t, then we have found our MEX value.

Since lower bound takes \(O(\log N)\), the overall complexity for computing Grundy numbers is \(O(N^2 \log N)\).

Making a move in \(O(N \log N)\) time

Now, we describe how to make a move given the Grundy numbers.

As stated above, if the table contains \(k\) consecutive unmarked segments, each having \(a_1, a_2, \dots, a_k\) consecutive integers, then the state is winning if and only if \(g_{a_1} \oplus g_{a_2} \oplus \dots \oplus g_{a_k} > 0\). When it is our turn, \(g_{a_1} \oplus g_{a_2} \oplus \dots \oplus g_{a_k} > 0\) is always satisfied and we only need to find a state (reachable in exactly one move) such that the xor of new Grundy numbers equals \(0\).

We can do this by keeping track of a list of \(k\) segments such that each segment in the list \([x,y]\) has not been covered by anyone. If you chose First, initially the list of segments is just \([1,N]\). If you chose Second, initially the list of segments is \([1,a-1]\) and \([a+b,N]\), where \((a,b)\) is the pair chosen by the jury initially.

During our turn, iterate over each of the \(k\) segments. Consider making a move on a specific segment \(i\) (\(1 \le i \le k\)), call it \([l_i,r_i]\). Let’s say we want to take the segment \([x,x+y)\), satisfying \(l_i \le x, x+y-1 \le r_i\), then the following should be satisfied:

\(g_{a_1} \oplus g_{a_2} \oplus \dots \oplus g_{a_k} \oplus g_{a_i} = g_{x-l_i} \oplus g_{r_i-x-y+1}\)

Notice that \(g_{a_1} \oplus g_{a_2} \oplus \dots \oplus g_{a_k} \oplus g_{a_i} \) can be easily calculated, so we can use the \(2 \times N+1\) vectors from calculating the Grundy numbers again: do lower bound on vector \((g_{a_1} \oplus g_{a_2} \oplus \dots \oplus g_{a_k} \oplus g_{a_i})\), search if there exists a pair \((u,v)\) satisfying \(g_u \oplus g_v = g_{a_1} \oplus g_{a_2} \oplus \dots \oplus g_{a_k} \oplus g_{a_i} \), such that \(u+v \ge r_i-l_i+1-R\) and \(u+v \le r_i-l_i+1-L\). If there is, then we take such pair \((u,v)\) as our answer.

Remember after each move (yours and jury’s), update the list of segments that have not been covered.

Making a move takes \(O(N \log N)\) time, and there can be \(O(N)\) moves, so the overall complexity is \(O(N^2 \log N)\).