RESTPERM - Editorial

divide-and-conq
editorial
ltime41
recursion
restperm

#1

PROBLEM LINK:

Practice
Contest

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:

exttt{divisible}(x, y, d) := exttt{true} if and only if |A_x - A_y| is divisible by d
exttt{less(x, y)} := exttt{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 exttt{divisible} queries and at most N-1 exttt{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 exttt{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 exttt{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 exttt{less} query is enough to determine the permutation. So the question is what to do when N > 2? Well, we can use exttt{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 exttt{indices} array and using divisor as the value for d in exttt{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 exttt{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 exttt{indices}. The indices 2 and 5 are also in P_1 because the results of exttt{divisible(1, 2, 2)} and exttt{divisible(1, 5, 2)} are true (for example |5-3| is divisible by 2). Other elements are in P_2 because the result of exttt{divisible} query for them is exttt{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 exttt{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 exttt{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 exttt{less} query at most N-1 times, from the same reason.

AUTHOR’S AND TESTER’S SOLUTIONS:


Setter's solution can be found [here][333]. Tester's solution can be found [here][444]. Editorialist's solution can be found [here][555].

#2

can you clarify how the sets p1 and p2 are made. Not able to get that.
more precisely

the i-th element of the indices array, i.e. indicesi goes into P1 if and only if the result of divisible(i,j,d) is true, otherwise it goes into P2

what is ‘j’ here?

and why at each level you are passing 2*divisor?


#3

Why am I getting TLE?


#4

Can anyone tell me Why I am getting TLE even for subtask 1 and 2?

https://www.codechef.com/viewsolution/11977926


#5

Why would elements with rank 1, 3, 5, … would be in one of the result vectors?


#6

And I also did not understand this part of the Editorialist’s solution.

    for(int i = 0; i < SZ(left_indices); ++i)
    {
        int val = (res.se == res_left.se) ? (2 * res_left.fi* - 1) : (2 * res_left.fi*);
        res.fi[left_indices*] = val;
    }
    for(int i = 0; i < SZ(right_indices); ++i)
    {
        int val = (res.se == res_right.se) ? (2 * res_right.fi* - 1) : (2 * res_right.fi*);
        res.fi[right_indices*] = val;
    }

#7

I updated the rules for placing elements to partitions (previously j wasn’t defined by mistake as you pointed out). Is it clear enough now?


#8

Speaking of multiplying the divisor by two. Notice that if we have one partition P_1 containing the first index and all indices i_k from all N indices such that for each of them |A_indices_1 - A_i_k| is divisible by 2, then for half of them |A_indices_1 - A_i_k| is divisible by 2*2 = 4 and for the other half it is not divisible by 4. The same can be applied to the other partition


#9

okay! got it now. thanks :slight_smile:


#10

You have to flush stdout after you have written something to it. Alternatively you could flush it right before reading something from stdin.


#11

@ceilks flushed stdout every time I wrote something to it, still getting TLE.

https://www.codechef.com/viewsolution/12147060