CF2210E.Binary Strings are Simple?

This is an interactive problem.

You are given an unknown binary string $ s $ $ ^{\text{∗}} $ of length $ n $ . The function $ f(l, r) $ is defined as the number of distinct elements in the array $ a $ formed by the following operation:

• Let $ S $ be the substring $ s_l s_{l+1} \ldots s_r $ . Let $ m $ be the length of the substring.
• We start with an empty array $ a $ .
• For the $ i $ -th $ (0 \le i \lt m) $ left cyclic rotation $ ^{\text{†}} $ of $ S $ , let's denote the number of inversions $ ^{\text{‡}} $ as $ x_{i} $ .
• For every $ i $ such that $ 0 \le i \lt m $ , append $ x_{i} \mbox{ mod } m $ to the array $ a $ , where $ u \mbox{ mod } v $ denotes the remainder of dividing $ u $ by $ v $ .

To determine $ s $ , you can ask some questions. In each question, you can choose $ 2 $ integers $ l $ and $ r $ ( $ 1 \le l \le r \le n $ ) and get the value of $ f(l, r) $ . Asking each query incurs a cost of $ \dfrac{n}{r-l+1} $ . Note that the cost does not necessarily have to be an integer.

You have to determine the hidden binary string while keeping the total cost of queries atmost $ \mathbf{max(30,3\cdot n)} $ . You are allowed to make at most $ \mathbf{2} $ guesses.

$ ^{\text{∗}} $ A binary string only contains characters $ \texttt{0} $ and $ \texttt{1} $ .

$ ^{\text{†}} $ Let there be a binary string $ s ; = ; s_{1}s_{2}\cdots s_{n} $ . The $ k $ -th left cyclic rotation of $ s $ is defined as $ t_{k} ; = ; s_{k+1}s_{k+2}\cdots s_{n}s_{1}s_{2}\cdots s_{k} $ .

$ ^{\text{‡}} $ Let there be a string $ s ; = ; s_{1}s_{2}\cdots s_{n} $ . The number of inversions of $ s $ is defined as the number of pairs of indices $ i,j ; (1 \le i \lt j \le n) $ , such that $ s_{i} \gt s_{j} $ .

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 a single integer $ n $ ( $ 2 \le n \le 3000 $ ) — the length of the unknown string $ s $ .

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3000 $ .

null

In the example interaction, the input and output contain empty lines to align interactor responses with queries. These empty lines do not appear in the actual input and output.

In the first test case, the hidden string is $ s = $ 00000. Here, since 0 cannot create any inversion, the array $ a $ will always be $ [0] $ for all substrings. Hence $ f(l, r) $ returns $ 1 $ for all queries.

Here we made $ 3 $ queries.

The first query is $ f(1,5) $ which returns 1 — the cost of this query is $ \dfrac{5}{5-1+1} = 1 $ .

The second query is $ f(2,5) $ , which returns 1 — the cost of this query is $ \dfrac{5}{5-2+1} = \dfrac{5}{4} $ .

The third query is $ f(3,5) $ , which returns 1 — the cost of this query is $ \dfrac{5}{5-3+1} = \dfrac{5}{3} $ .

The total cost after all these queries $ = 1 + \dfrac{5}{4} + \dfrac{5}{3} = \dfrac{47}{12} $ which is less than $ \max(30, 3\cdot n) = 30 $ .

After this, we guess $ s = $ 00000, for which the interactor returns $ 1 $ , indicating correct guess. We then move to the next test case.

In the second test case, the hidden string is $ s = $ 001.

We make the query $ f(1,3) $ , which returns 3. The cost of this query is $ \dfrac{3}{3-1+1} = 1 $ .

The total cost of the query is $ 1 $ which is less than $ \max(30, 3\cdot n) = 30 $ .

We then guess 100, for which the interactor returns 0, indicating it is incorrect.

We guess 001, for which the interactor returns 1, indicating our guess is correct. We then move to the next test case.

For the third test case, the hidden string is $ s = $ 10101010.