I am unable to understand the editorial of the problem.

https://codeforces.com/contest/1187/problem/D

Can anybody elaborate the solution clearly?

Thanks in advance.

I am unable to understand the editorial of the problem.

https://codeforces.com/contest/1187/problem/D

Can anybody elaborate the solution clearly?

Thanks in advance.

I think I can trying simplifying a little bit.

**Fact 1:** This question does NOT ask you to find the minimum number of operations to convert a[] to b[].

**Fact 2:** Sorting an array is just a series of swaps.

**Fact 3:** b[] needs to be a permutation of a[], else the answer is NO

*Which leads to the question, given arrays a[] and b[], if I could swap two elements of a[] as many times as I wanted to, can I convert it to b[] ?*

*For every element b[i], where i is the index, find the first position of b[i] in a[]. Let’s call this position j. We need to swap the corresponding element with the elements before it to move from position j to position i.*

*How do we find this position j? We can’t iterate over the entire a[] for every element in b[]. We need to extract this position j in O(1) or O(log n) at max.*

*Now notice that the range of the elements is only [1, n] . What we are looking for is the minimum index j in a[] such that a[j] = b[i]. Thus for 1 to n we can have n stacks. The top of stack k, indicates the first position >= i such a[top] = k*

*Right, so now we have figured how to find the first position j of a[] > i such that a[j] = b[i].*

*Now, when can we swap a[j] with the elements before it to bring to position i?*

*Only if a[j] is <= the elements until position i. In other words, only if a[j] is <= the minimum element in range [i,j-1]*

*(or)*

*If the top element of all stacks k such k < b[i] is > i. That is, the minimum top element from stack 1 to stack b[i] - 1 should be either NULL or > i. This minimum can be found using segment tree.*

Correct me if I am wrong

1 Like