PROBLEM LINK:
Author: Sergey Kulik
Tester: Misha Chorniy
Editorialist: Pawel Kacprzak
DIFFICULTY:
MEDIUM
PREREQUISITES:
Divide and conquer
PROBLEM:
Given an unknown permutation A of numbers from 1 to N, ask queries of form:
\texttt{divisible}(x, y, d) := \texttt{true} if and only if |A_x - A_y| is divisible by d
\texttt{less(x, y)} := \texttt{true} if and only if A_x - A_y
and find out what the permutation is exactly. The hard part of the problem is the fact that you can ask at most 13 \cdot N \texttt{divisible} queries and at most N-1 \texttt{less} queries.
QUICK EXPLANATION:
Use divide and conquer and recursion to solve the problem. While there are more than 2 elements in the instance of a problem, partition them into two almost equal sets using \texttt{divisible} query. Solve the problem for both partitions recursively and merge these sub-results using the less query.
EXPLANATION:
In subtasks 1, 2 and 3 the constrains are low enough to allow multiple different approaches. In particular they allow more calls to the \texttt{divisible} query. The general idea behind some of them is also covered in the explanation of the intended solution, so we recommend to read the below detailed explanation of this method.
In the last subtask, the permutation is quite large - it has up to 10^4 elements. We are going to solve the problem recursively using divide and conquer approach. Notice that when the instance of the problem is very small, i.e. N \leq 2, the problem is very easy to solve. In particular, when N=1 there is nothing to do, because the partition is already known, and if N = 2 then, one \texttt{less} query is enough to determine the permutation. So the question is what to do when N > 2? Well, we can use \texttt{divisible} query then. The idea is that we want to partition the initial indices of the permutation into two almost equal in size groups, solve the problem recursively for the partitions and finally somehow combine these result into the final result.
Let solve(indices, divisor) be a recursive function finding out the absolute order of elements of the permutation with indices belonging to \texttt{indices} array and using divisor as the value for d in \texttt{divisible} query to partition the elements. Moreover, the solve function will return the index of the smallest number in the permutation with index in indices - we will be using this element to merge two subproblems solved recursively. The final answer to the problem will be the partition returned by calling solve([1,2,\ldots,N], 2). If there are no more than 2 indices we know what to do, otherwise we are going to partition indices into two groups P_1 and P_2 as follows:
- the first element of the indices array, i.e. indices_1 goes into P_1
- the i-th element of the indices array, i.e. indices_i goes into P_1 if and only if the result of divisible(indices_1, indices_i, d) is \texttt{true}, otherwise it goes into P_2. In other words it goes to P_1 if and only if |A_{indices_1} - A_{indices_i}| is divisible by d.
The above method partition the indices into two almost equal in size sets. For example, let’s assume that the initial permutation is 5,3,2,4,1 and we are solving the problem for all the indices 1,2, \ldots, 5. Then the partition will assign indices as follows:
P_1 = \{1, 2, 5\}
P_2 = \{3, 4\}
The index 1 is in P_1 because it is the first element of \texttt{indices}. The indices 2 and 5 are also in P_1 because the results of \texttt{divisible(1, 2, 2)} and \texttt{divisible(1, 5, 2)} are true (for example |5-3| is divisible by 2). Other elements are in P_2 because the result of \texttt{divisible} query for them is \texttt{false}.
After the partition, we are going to solve the problems corresponding to the indices in P_1 and P_2 separately with divisor multiplied by two, so we will call two functions:
- solve(P_1, 2 \cdot divisor)
- solve(P_2, 2 \cdot divisor)
We multiply the divisor by 2 to allow the partitions performed during these subcalls to be done in the same way. By the definition, these functions returns the absolute orders of the elements in the permutation with indices in P_1 and with indices in P_2. The only thing left to do is to merge these two orders into the final order. Let s_1 be the index of the smallest element in the permutation among elements with indices in P_1. Similarly, let s_2 be the index of the smallest element in the permutation among elements with indices in P_2. These elements are also returned from recursive calls. We are going to use them to merge sub-results into the final result. Notice that if s_1 < s_2, then the smallest element, i.e. the element with value 1 is among the element with indices in P_1. Moreover, the 3 rd smallest, 5 th smallest, … elements among all elements with indices in \texttt{indices} have also indices in P_1 and all other elements have indices in P_2. In the other case, if s_2 < s_1 the situation is opposite and the elements with ranks 1, 3, 5, \ldots have indices in P_2 and all other elements have indices in P_1. Thus calling a query less(s_1, s_2) allows us to determine how to merge the absolute orders of element with indices in P_1 and P_2 into one absolute order of elements with indices in P_1 \bigcup P_2.
Notice that this method calls \texttt{divisible} query at most 13 \cdot N times because it calls it no more than N times on each level of recursion tree besides two deeper ones and the recursion tree has depth non greater than \log N = 14. Also, this methods calls \texttt{less} query at most N-1 times, from the same reason.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.
