I am unable to understand the editorial of the problem.
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