A Convex Game
Contest: Codeforces Round 679 (Div. 1, based on Technocup 2021 Elimination Round 1)
Difficulty rating: 3500
Tags: dsu, games

Shikamaru and Asuma like to play different games, and sometimes they play the following: given an increasing list of numbers, they take turns to move. Each move consists of picking a number from the list.

Assume the picked numbers are $$$v_{i_1}$$$, $$$v_{i_2}$$$, $$$\ldots$$$, $$$v_{i_k}$$$. The following conditions must hold:

- $$$i_{j} < i_{j+1}$$$ for all $$$1 \leq j \leq k-1$$$;
- $$$v_{i_{j+1}} - v_{i_j} < v_{i_{j+2}} - v_{i_{j+1}}$$$ for all $$$1 \leq j \leq k-2$$$.

However, it's easy to play only one instance of game, so today Shikamaru and Asuma decided to play $$$n$$$ simultaneous games. They agreed on taking turns as for just one game, Shikamaru goes first. At each turn, the player performs a valid move in any single game. The player who cannot move loses. Find out who wins, provided that both play optimally.

Input format:
The first line contains the only integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) standing for the number of games Shikamaru and Asuma play at once. Next lines describe the games.

Each description starts from a line with the only number $$$m$$$ ($$$m\geq 1$$$) denoting the length of the number list. The second line contains the increasing space-separated sequence $$$v_1$$$, $$$v_2$$$, ..., $$$v_m$$$ from the game ($$$1 \leq v_{1} < v_{2} < ... < v_{m} \leq 10^{5}$$$).

The total length of all sequences doesn't exceed $$$10^5$$$.

Output format:
Print "YES" if Shikamaru can secure the victory, and "NO" otherwise.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first example Shikamaru can pick the last number, and Asuma cannot do anything because of the first constraint.

In the second sample test Asuma can follow the symmetric strategy, repeating Shikamaru's moves in the other instance each time, and therefore win.

Example input:
1
10
1 2 3 4 5 6 7 8 9 10

Example output:
YES

Example input:
2
10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10

Example output:
NO

Editorial:
It's sufficient to calculate the Grundy value for each game instance. Consider a single game. Let $$$maxc$$$ be the maximal value in the sequence $$$v$$$. We are going to prove that the Grundy value does not exceed $$$\sqrt{2 \cdot maxc} + 1$$$.
Proof: Assume the contrary; that is, that the Grundy value equals $$$ d > \sqrt{2 \cdot maxc} + 1$$$. Then, by definition, there is a sequence $$$v_{i_0}$$$, $$$v_{i_1}$$$, ..., $$$v_{i_{d - 1}}$$$ which is a valid sequence of moves. Indeed, initially there is a move into a position in game with the value $$$d - 1$$$, then there is a move from it to the position with value $$$d - 2$$$, and so on. It's easy to see that $$$v_{i_{j + 1}} - v_{i_j} \geq j + 1$$$ for all $$$j\leq d - 2$$$. Then $$$v_{i_{d - 1}} - v_{i_0} \geq \frac {d (d - 1)} {2} \geq \frac {(d - 1) (d - 1)} {2} \geq maxc$$$, which leads to a contradiction.
It is clear from the statement that the outcome of the game is defined by the index of the last move and the last difference between the elements. It follows from the Grundy theory that if we fix the last index and gradually decrease the last difference, the grundy value will not decrease. It'd be great to calculate the value of $$$dp[i][d]$$$ standing for the maximal possible last difference so that the Grundy value equals $$$d$$$, for each index $$$i$$$ and each possible Grundy value $$$d$$$. This, in its turn, can be done by calculating $$$maxv[d][i]$$$ being the maximal $$$v_j$$$ so that after the move from $$$v_i$$$ to $$$v_j$$$ the Grundy value will equal $$$d$$$. If we know it, then, standing at some index $$$j$$$ and knowing the range of last differences so that the Grundy value equals $$$d$$$ for all $$$d$$$ (we can obtain it from the values of $$$dp[i]$$$), we need to remax the values of $$$maxv[d]$$$ on some subsegment. Hence, we can already implement a segment tree solution working for $$$O(n \cdot maxc + \sum m_i \cdot \sqrt{2 \cdot maxc} \cdot log(m_i))$$$. However, it's too long.
Now recall that the initial array is increasing in each game. This means that during the calculation of $$$dp$$$ and $$$maxv$$$ from left to right, we only need to remax something a single time (the first time). This operation can be done via DSU, if we compress subsegments of all already calculated values and one not yet calculated into a single component. Then the final time complexity will be $$$O(n \cdot maxc + \sum m_i \cdot \sqrt{2 \cdot maxc} \cdot \alpha(m_i))$$$.