CF2163D1 Diadrash (Easy Version)

This is the Easy version of the problem. The difference between the versions is that in this version, you can make at most $ \max(300, \lceil\frac{n}{2}\rceil+2) $ queries. You can hack only if you solved all versions of this problem. This problem is interactive. There is a permutation $ ^{\text{∗}} $ $ p $ of the integers from $ 0 $ to $ n-1 $ hidden from you. Additionally, you are given $ q $ ranges $ [l_1, r_1], [l_2, r_2], \ldots, [l_q, r_q] $ where $ 1 \le l_i \le r_i \le n $ . You need to discover the maximum $ \operatorname{MEX} $ among the values of $ p $ in the $ q $ ranges that are given to you in the input. Formally, you must discover the value of $ \max _{i=1}^q {\operatorname{MEX}([p_{l_i}, p_{l_i+1}, \ldots, p_{r_i}])} $ $ ^{\text{†}} $ . To do this, you may make at most $ \max(300, \lceil\frac{n}{2}\rceil+2) $ queries of the following form: - Choose any two integers $ 1 \le l \le r \le n $ and you will receive the value $ \operatorname{MEX}([p_{l}, p_{l+1}, \ldots, p_{r}]) $ . $ ^{\text{∗}} $ A permutation of the integers from $ 0 $ to $ n-1 $ is a sequence of $ n $ elements where every integer from $ 0 $ to $ n-1 $ appears exactly once. For example, the sequence $ [0, 3, 1, 2] $ is a permutation, but the sequence $ [0, 0, 2, 1] $ is not. $ ^{\text{†}} $ The $ \operatorname{MEX} $ of a sequence is defined as the smallest non-negative integer that does not appear in that sequence. For example, $ \operatorname{MEX}([0, 0, 1, 3]) = 2 $ and $ \operatorname{MEX}([1, 2, 2]) = 0. $

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). The description of the test cases follows. The first line of each test case contains exactly two integers $ n $ and $ q $ ( $ 4 \le n \le 10^4 $ , $ 1 \le q \le 3 \cdot 10^5 $ ) — the size of the permutation and the number of ranges, respectively. The $ i $ -th of the next $ q $ lines contains two integers $ l_i, r_i $ ( $ 1 \le l_i \le r_i \le n $ ). It is guaranteed that the sum of $ n $ and $ q $ do not exceed $ 10^4 $ and $ 3 \cdot 10^5 $ respectively over all test cases. Additional Constraint: it is guaranteed that no range is repeated in the same test case.

N/A

In the first example, the hidden permutation is $ p = [0, 3, 1, 2] $ and the ranges are $ [1, 2], [2, 4], [1, 3] $ . The third range is optimal, as $ \operatorname{MEX}([p_1, p_2, p_3]) = \operatorname{MEX}([0, 3, 1]) = 2 $ , which is maximum. In our first query, we ask about $ l = 1, r = 3 $ and the judge gives us the value $ \operatorname{MEX}([p_1, p_2, p_3]) = 2 $ . In the second query, we ask about $ l = 4, r = 4 $ and the judge gives us the value $ \operatorname{MEX}([p_4]) = 0 $ . Likewise, $ \operatorname{MEX}([p_1]) = 1 $ and $ \operatorname{MEX}([p_1, p_2, p_3, p_4]) = 4 $ . Somehow, we figure out that the answer we are looking for is $ 2 $ . In the second example, $ p = [3, 5, 0, 1, 4, 2] $ . In the third example, $ p = [0, 1, 2, 3] $ . Note that this is just an explanation of the way the interaction works and does not show any strategy to solve the problem.