Codeforces - Deltix Round, Summer 2021 - 1556D. Take a Guess

[https://codeforces.com/contest/1556/problem/D](https://codeforces.com/contest/1556/problem/D) ## Problem This is an interactive task William has a certain sequence of integers $a_1, a_2, ..., a_n $ in his mind, but due to security concerns, he does not want to reveal it to you completely. William is ready to respond to no more than 2⋅𝑛 of the following questions: What is the result of a bitwise AND of two items with indices 𝑖 and 𝑗 (𝑖≠𝑗) What is the result of a bitwise OR of two items with indices 𝑖 and 𝑗 (𝑖≠𝑗) You can ask William these questions and you need to find the 𝑘-th smallest number of the sequence. Formally the 𝑘-th smallest number is equal to the number at the 𝑘-th place in a 1-indexed array sorted in non-decreasing order. For example in array [5,3,3,10,1] 4th smallest number is equal to 5, and 2nd and 3rd are 3. ### Input It is guaranteed that for each element in a sequence the condition 0≤𝑎𝑖≤109 is satisfied. ### Interaction In the first line you will be given two integers 𝑛 and 𝑘 (3≤𝑛≤104,1≤𝑘≤𝑛), which are the number of items in the sequence 𝑎 and the number 𝑘. After that, you can ask no more than 2⋅𝑛 questions (not including the "finish" operation). Each line of your output may be of one of the following types: "or i j" (1≤𝑖,𝑗≤𝑛,𝑖≠𝑗), where 𝑖 and 𝑗 are indices of items for which you want to calculate the bitwise OR. "and i j" (1≤𝑖,𝑗≤𝑛,𝑖≠𝑗), where 𝑖 and 𝑗 are indices of items for which you want to calculate the bitwise AND. "finish res", where 𝑟𝑒𝑠 is the 𝑘th smallest number in the sequence. After outputting this line the program execution must conclude. In response to the first two types of queries, you will get an integer 𝑥, the result of the operation for the numbers you have selected. After outputting a line do not forget to output a new line character and flush the output buffer. Otherwise you will get the "Idleness limit exceeded". To flush the buffer use: fflush(stdout) in C++ System.out.flush() in Java stdout.flush() in Python flush(output) in Pascal for other languages refer to documentation If you perform an incorrect query the response will be −1. After receiving response −1 you must immediately halt your program in order to receive an "Incorrect answer" verdict. ## Explanation In short, we can retrieve the first 3 numbers first by asking 3 OR questions and 3 AND questions using the fact that $$ a + b = (a \lor b) + (a \land b) $$ After that we can fix the first number to find the rest of them. Once we have all the numbers, we sort the array and find the $k-th$ one. The first 3 numbers can be obtained by the following approach. First we - ask ``or 1 0`` and ``and 1 0`` to get $ a_{01} $ - ask ``or 1 2`` and ``and 1 2`` to get $ a_{12} $ - ask ``or 0 2`` and ``and 0 2`` to get $ a_{02} $ Now we know that $$ a_{01} = a_0 + a_1 $$ $$ a_{12} = a_1 + a_2 $$ $$ a_{02} = a_0 + a_2 $$ We can use these 3 numbers to obtain the first 3 numbers in the array. $$ a_0 = \frac{(a_{01} + a_{02} - a_{12})}{2} $$ $$ a_1 = \frac{(a_{01} + a_{12} - a_{02})}{2} $$ $$ a_2 = \frac{(a_{02} + a_{12} - a_{01})}{2} $$ Starting from $ i = 3 $, we can fix the first number to find out $a_i$. - ask ``or 0 i`` and ``and 0 i`` to get $ a_{0i} $ so that we will have $$ a_i = a_{0i} - a_0 $$ ## Solution ``` long long OR(int i, int j) { cout << "or " << i + 1 << " " << j + 1 << endl; long long x; cin >> x; return x; } long long AND(int i, int j) { cout << "and " << i + 1 << " " << j + 1 << endl; long long x; cin >> x; return x; } void solve() { long long n, k; cin >> n >> k; vector<long long> a(n); long long a_01 = OR(0, 1) + AND(0, 1); long long a_12 = OR(1, 2) + AND(1, 2); long long a_02 = OR(0, 2) + AND(0, 2); a[0] = (a_01 + a_02 - a_12) / 2; a[1] = (a_01 + a_12 - a_02) / 2; a[2] = (a_02 + a_12 - a_01) / 2; for(int i = 3; i < n; i++) { long long a_0i = OR(0, i) + AND(0, i); a[i] = a_0i - a[0]; } sort(a.begin(), a.end()); cout << "finish " << a[k - 1] << endl; } ```