409611: GYM103643 N Chiisana Boukensha

Megumin is a small adventurer going on an expedition! Her world has $$$N+1$$$ ($$$N = 2^k-1, \, 0 \leq k \leq 30$$$) cities labeled from $$$0 \,...\, N$$$. There is a bidirectional road between every pair of cities. If Megumin wants to travel from city $$$i$$$ to city $$$j$$$, it takes her $$$i \oplus j \oplus N$$$ days because she needs to explode the enemies on the road. Here, $$$\oplus$$$ is the bitwise XOR operator. Megumin starts at city $$$A$$$ and wants to go to city $$$B$$$ ($$$0 \leq A, \, B \leq N$$$).

For a path $$$p$$$, define $$$\text{explosion}(p)$$$ to be the maximum of $$$p_i \oplus p_{i+1} \oplus N$$$ over all roads $$$p_i \rightarrow p_{i+1}$$$ on the path. If there are no roads on $$$p$$$, $$$\text{explosion}(p) = 0$$$. Find the minimum value of $$$\text{explosion}(p)$$$ amongst all paths $$$p$$$ from city $$$A$$$ to city $$$B$$$.

The first line contains one integer, $$$T$$$ $$$(1 \leq T \leq 10^5)$$$, the number of test cases. Then $$$T$$$ test cases follow.

The first and only line of each test case contains $$$3$$$ integers, $$$N, \, A, \, B$$$.

For each test case, print the minimum value of $$$\text{explosion}(p)$$$ amongst all paths $$$p$$$ from city $$$A$$$ to city $$$B$$$ on a separate line.

3
0 0 0
1 0 1
3 1 2

0
0
0

In the first test case of the example, Megumin starts at her finish city, so she does not traverse any roads. Hence the maximum is $$$0$$$.

In the second test case of the example, Megumin can travel directly from city $$$0$$$ to city $$$1$$$. For $$$p = 0 \rightarrow 1$$$, $$$\text{explosion}(p) = \max(0 \oplus 1 \oplus 1) = \max(0) = 0$$$.

In the third test case of the example, Megumin can travel directly from city $$$1$$$ to city $$$2$$$. For $$$p = 1 \rightarrow 2$$$, $$$\text{explosion}(p) = \max(1 \oplus 2 \oplus 3) = \max(0) = 0$$$. Note that Megumin could also take the path $$$q = 1 \rightarrow 3 \rightarrow 2$$$. However, $$$\text{explosion}(q)$$$ $$$= \max(1 \oplus 3 \oplus 3,\, 3 \oplus 2 \oplus 3)$$$ $$$= \max(1,\, 2) = 2$$$. This is not the minimum for a path from city $$$1$$$ to city $$$2$$$ because $$$\text{explosion}(p) = 0 \leq 2 = \text{explosion}(q)$$$.

$$$---------------------------------------------$$$

Problem Idea: codicon

Problem Preparation: codicon

Occurrences: Novice 11, Intermediate 6, Advanced 4