Removing Graph
Contest: Codeforces Round 868 (Div. 2)
Difficulty rating: 2500
Tags: brute force, dp, games, graphs, math

Alice and Bob are playing a game on a graph. They have an undirected graph without self-loops and multiple edges. All vertices of the graph have degree equal to $$$2$$$. The graph may consist of several components. Note that if such graph has $$$n$$$ vertices, it will have exactly $$$n$$$ edges.

Alice and Bob take turn. Alice goes first. In each turn, the player can choose $$$k$$$ ($$$l \le k \le r$$$; $$$l < r$$$) vertices that form a connected subgraph and erase these vertices from the graph, including all incident edges.

The player who can't make a step loses.

For example, suppose they are playing on the given graph with given $$$l = 2$$$ and $$$r = 3$$$:

A valid vertex set for Alice to choose at the first move is one of the following:

- $$$\{1, 2\}$$$
- $$$\{1, 3\}$$$
- $$$\{2, 3\}$$$
- $$$\{4, 5\}$$$
- $$$\{4, 6\}$$$
- $$$\{5, 6\}$$$
- $$$\{1, 2, 3\}$$$
- $$$\{4, 5, 6\}$$$

Then a valid vertex set for Bob to choose at the first move is one of the following:

- $$$\{1, 2\}$$$
- $$$\{1, 3\}$$$
- $$$\{2, 3\}$$$
- $$$\{1, 2, 3\}$$$

Alice can't make a move, so she loses.

You are given a graph of size $$$n$$$ and integers $$$l$$$ and $$$r$$$. Who will win if both Alice and Bob play optimally.

Input format:
The first line contains three integers $$$n$$$, $$$l$$$ and $$$r$$$ ($$$3 \le n \le 2 \cdot 10^5$$$; $$$1 \le l < r \le n$$$) — the number of vertices in the graph, and the constraints on the number of vertices Alice or Bob can choose in one move.

Next $$$n$$$ lines contains edges of the graph: one edge per line. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$) — description of the $$$i$$$-th edge.

It's guaranteed that the degree of each vertex of the given graph is equal to $$$2$$$.

Output format:
Print Alice (case-insensitive) if Alice wins, or Bob otherwise.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test the same input as in legend is shown.

In the second test the same graph as in legend is shown, but with $$$l = 1$$$ and $$$r = 2$$$.

Example input:
6 2 3
1 2
2 3
3 1
4 5
5 6
6 4

Example output:
Bob

Example input:
6 1 2
1 2
2 3
3 1
4 5
5 6
6 4

Example output:
Bob

Editorial:
The solution requires knowledge of the Sprague-Grundy theory. Recall that $$$a \oplus b$$$ means the bitwise exclusive or operation, and $$$\operatorname{mex}(S)$$$ is equal to the minimum non-negative number that is not in the set $$$S$$$.
The fact that $$$l \neq r$$$ is important.
The given graph is a set of cycles, and the game runs independently in each cycle. If we can calculate nim-value for a cycle of each size, then nim-value of the whole game is equal to XOR of these values.
To calculate nim-value for the cycle of length $$$x$$$ ($$$cycle[x]$$$), we need to take $$$\operatorname{mex}$$$ of nim-values from all transitions. But since all transitions transform a cycle to a chain, then we will calculate nim-values for chains as well, or $$$cycle[x] = \operatorname{mex}(chain[x - r], chain[x - r + 1], \dots, chain[x - l])$$$.
To calculate nim-value for the chain $$$chain[x]$$$, we need to consider all possible transitions. We can either cut off from the end of the chain, or from the middle of the chain. In either case, we end up with two smaller chains (maybe one of them is empty), which are themselves independent games, so $$$chain[x] = \operatorname{mex}{\{chain[a] \oplus chain[b] \mid \forall a, b \ge 0 : x - r \le a + b \le x - l\}}$$$.
Implementing this directly requires $$$O(n^3)$$$ time. A more accurate implementation with recalculations requires $$$O(n^2)$$$ time. For a complete solution, something needs to be noticed in nim-values.
Consider an example. Let $$$l = 4$$$, $$$r = 14$$$.
• $$$chain[x]$$$ on $$$[0, l - 1]$$$ is obviously equal to $$$0$$$;
• $$$chain[x] = \left\lfloor \frac{x}{l} \right\rfloor$$$ on segment $$$[0, r + l - 1]$$$ (proof is below);
• $$$chain[x] > 0$$$ for all $$$x \ge l$$$: since $$$l < r$$$ you can always split the chain $$$x$$$ in two equal chains $$$a$$$. This transition adds nim-value $$$chain[a] \oplus chain[a] = 0$$$ into $$$\operatorname{mex}$$$, that's why $$$chain[x] = \operatorname{mex}{\{\dots\}} > 0$$$.
• $$$cycle[x]$$$ is equal to $$$chain[x]$$$ up to $$$r + l - 1$$$: it's because $$$cycle[x]$$$ is equal to $$$\operatorname{mex}{\{chain[0], chain[1], \dots, chain[x - l]\}}$$$;
• $$$cycle[x] = 0$$$ for $$$x \ge l + r$$$, it's because $$$chain[x] > 0$$$ for $$$x \ge l$$$.
So, if $$$x \le r + l - 1$$$, then $$$cycle[x] = \left\lfloor \frac{x}{l} \right\rfloor$$$, otherwise $$$cycle[x] = 0$$$. We have to calculate the sizes of all cycles in the graph and calculate XOR of those values. If it is zero, the winner is Bob, otherwise, winner is Alice.
Let's prove that $$$chain[x] = \left\lfloor \frac{x}{l} \right\rfloor$$$ on segment $$$[0, r + l - 1]$$$:
1. $$$chain[x] \ge \left\lfloor \frac{x}{l} \right\rfloor$$$: there are transitions to pairs of chains $$$(a, b)$$$ where $$$a = 0$$$ and $$$b$$$ is any number from $$$[0, x - l]$$$. Their nim-value is equal to $$$chain[0] \oplus chain[b]$$$ $$$=$$$ $$$chain[b]$$$, so $$$chain[x] \ge \operatorname{mex}{\{chain[b] \mid 0 \le b \le x - l\}} = \left\lfloor \frac{x}{l} \right\rfloor$$$.
2. $$$chain[x]$$$ is exactly equal to $$$\left\lfloor \frac{x}{l} \right\rfloor$$$: we can prove that for any pair of chains $$$(a, b)$$$ with $$$a + b \le x - l$$$ value $$$chain[a] \oplus chain[b]$$$ $$$\le$$$ $$$\left\lfloor \frac{x}{l} \right\rfloor - 1$$$: $$$$$$chain[a] \oplus chain[b] \le chain[a] + chain[b] = \left\lfloor \frac{a}{l} \right\rfloor + \left\lfloor \frac{b}{l} \right\rfloor \le \left\lfloor \frac{a + b}{l} \right\rfloor \le \left\lfloor \frac{x - l}{l} \right\rfloor = \left\lfloor \frac{x}{l} \right\rfloor - 1$$$$$$