Educational Codeforces Round 67 Help needed!

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