You are not logged in. Please login at www.codechef.com to post your questions!

×

RESTPERM - Editorial

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:

$\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.

This question is marked "community wiki".

asked 29 Oct '16, 21:50

pkacprzak's gravatar image

6★pkacprzak ♦♦
71483787
accept rate: 12%

edited 30 Oct '16, 04:11


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?

link

answered 30 Oct '16, 00:11

nagpalkaran95's gravatar image

4★nagpalkaran95
16613
accept rate: 12%

edited 30 Oct '16, 00:42

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?

(30 Oct '16, 04:06) pkacprzak ♦♦6★

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

(30 Oct '16, 04:28) pkacprzak ♦♦6★

okay! got it now. thanks :)

(31 Oct '16, 01:28) nagpalkaran954★

Why am I getting TLE?

link

answered 30 Oct '16, 04:05

gokuss's gravatar image

2★gokuss
1
accept rate: 0%

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

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

link

answered 31 Oct '16, 23:15

ritik_27's gravatar image

4★ritik_27
21
accept rate: 0%

edited 31 Oct '16, 23:46

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

(02 Nov '16, 15:37) ceilks7★

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

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

(27 Nov '16, 16:23) ritik_274★

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

link

answered 02 Nov '16, 11:22

shreerockz15's gravatar image

3★shreerockz15
404
accept rate: 33%

edited 02 Nov '16, 16:26

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

answered 02 Nov '16, 12:48

shreerockz15's gravatar image

3★shreerockz15
404
accept rate: 33%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,590
×252
×102
×41
×7

question asked: 29 Oct '16, 21:50

question was seen: 2,339 times

last updated: 27 Nov '16, 16:23