Author: | Anton Trygub |
Developer: | Stanislav Bezkorovainyi |
Editorialist: | Stanislav Bezkorovainyi |
If n \le 30, that we can simply find the array using queries of type . Otherwise we should do the following:
At first, we should find the position of maximum or minimum element of the array. Let's define those positions as and respectively. Now, use query of type on the whole array. Let's denote the maximum element of the resulting array as . It is obvious that M = a_w - a_u.
What does it mean if the maximum element of the resulting array on query of type for some subset of indexes is equal to ? It means that both and belong to . Now, we can using binary search find the leftmost position such that the maximum element of the resulting array on the query of type for set of indexes \{ 1, 2,\ldots,pos \} is equal to .
Since both and belong to \{ 1,2,\ldots,pos \} and one of them does not belong to \{ 1,2,\ldots,pos - 1 \}, or is equal to . For now, it does not really matter whether u = pos or w = pos. What matters is that, since all a_i are distinct and that the value of a_{pos} is whether smaller or greater than value of any a_i, there is no such pair of indexes (j, i), i \neq j that |a_{pos} - a_i| = |a_{pos} - a_j|.
Let's denote b_i = |a_{pos} - a_i|. It's obvious, that b_{pos} = 0. Now we should find b_i for every 1 \le i \le n, i \neq pos. All b_i will be distinct.
At first, let's define function F(Q) = B that takes some set of indexes , such that pos \notin Q as an argument and returns set that contains all b_i for any i \in Q. How to implement such function in your program? That's quite simple. At first, let's denote set as the result of query 2 on set of indexes and set A' as the result of query 2 on set Q \cup \{ pos \} . Then, F(Q) = A' \setminus A (All elements, that belong to A', but do not belong to ). Since all b_i are different, size of set will always be equal to size of .
Now, let's use divide and conquer approach.
Let's say that we have some set of positions and set B = F(Q). We want to know b_i for every i \in Q. There are two possible scenarios:
Size of is equal to . Then b_i is the only element of set , while is the only element of set . Thus, we know b_i without any additional queries.
We split into two sets S_1, S_2 such that first \lfloor \frac{|Q|}{2} \rfloor elements of set go into set S_1 and the rest of them go into S_2. We can find B_1 = F(S_1), B_2 = F(S_2) in one call of function : B_1 = F(S_1), B_2 = B \setminus B_1. Now, we should solve the problem independently for sets S_1, B_1 and S_2, B_2.
At the beginning of the algorithm, contains all indexes except and is calculated in a straightforward way B := F(Q).
A split of a set takes call of , but wait a second... There are splits. It is no better than simply asking value for every index with query ! Yeah, I know. But we can optimize it easily into O(log_2{n}) calls of .
It is easy to notice that splits on the same depth of our "divide and conquer binary tree" can be done simultaneously with only only call of function . Let's say that there are sets Q_1, Q_2, \ldots, Q_k about to be split on the same depth. Their first halfs are S_{1_1}, S_{2_1}, \ldots, S_{k_1}. Let's define A = F(S_{1_1} \cup S_{2_1} \cup \ldots \cup S_{k_1}) (Function of union of all S_{i_1}). Now, for every 1 \le i \le k B_{i_1} = B_i \cap A, B_{i_2} = B_i \setminus B_{i_1}.
Depth of the tree is at most \lceil log_2{n} \rceil. So that we will make at most \lceil log_2{n} \rceil calls of function + one call in order to get for the initial set. Every call of takes exactly queries, so we will spend 2 \cdot \lceil log_2{n} + 1\rceil queries on this part of the program.
Now, we know b_i for every 1 \le i \le n. Let's define pos_2 as such index that b_{pos_2} = \max(b_1, b_2, \ldots, b_n). Since the minimal element has the greatest difference with the maximal element and vice versa, if a_{pos} is the minimal element, then a_{pos_2} is the maximal one and vice versa. Let's use query 1 to ask the value of a_{pos} and the value of a_{pos_2}. There are two possible scenarios:
a_{pos} > a_{pos_2}. That means a_{pos} is the maximal element of the array and thus a_i = a_{pos} - b_i for every 1 \le i \le n.
a_{pos} < a_{pos_2}. That means a_{pos} is the minimal element of the array and thus a_i = a_{pos} + b_i for every 1 \le i \le n.
Overall, we used 1 + \lceil log_2{n} \rceil queries to find , 2 \cdot \lceil log_2{n} \rceil + 2 queries to find b_i for every and queries to find values of a_{pos} and a_{pos_2}.
Note. Be careful while implemeting binary search and function . Otherwise, you may find yourself getting Wrong Answer due to very strict constraints.