question link : -https://www.codechef.com/problems/FAKEBS
can anyone please give me easy editorial because i am unable to understand the official editorial thanks in advance
Suppose you have a sorted array of 7 elements : \displaystyle 0, 1, 2, 3 ,4, 5, 6 \text{ } . If you perform binary search for the number 4, the algorithm will check the indices 3, 5, 4 in that order. Similarly, every number in the array has a unique sequence of indices the algorithm will check before reaching there.
Now if that array isn’t sorted, for example 10, 9, 4, 3, 2, 1, 7 \text{ } but we still want to reach the index 4 ( number 2 ) then we want the algorithm to check indices 3, 5, 4 because that is the only way to reach there.
Now how does the algorithm decide whether to go to the right or to the left? If at any point, it encounters a number less than the one we are searching for then it goes to the right otherwise left. So, corresponding to each index we have a sequence of \text{L's} and \text{R's}. For example, for the index 4, we have \text{RL} because it first goes to the right then left. Similarly for index 6 we have \text{RR}.
In the example, while checking for the number 2, we encounter the numbers 3 and 1. So the algorithm wants to go left first ( because 2<3 ) and then right ( 1<2 ). So the actual sequence encountered is \text{LR}.
Comparing these side by side,
Required : \text{RL}
Actual \text{ } : \text{LR}
We want the 2 sequences to be the same by changing the “Actual” sequence. In this case we can simply swap the L with the R to get “Required” sequence.
In general, we will have pairs where we “want L but have R”, “want R but have L”, “want R and have R”, “want L and have L”. I’ll denote the number of these pairs by lr, rl, rr and ll respectively. In the example we had lr=1, rl=1, ll=0, rr=0
So what can we do in general to minimise swaps? Firstly, we can swap as many lr cases with rl as we can. The max we can swap is min(lr, rl). After doing that, we may have some lr’s or rl’s left over. We can swap them with the elements that are not in the unique sequence leading to the required index. so the answer is min(lr, rl) + max( lr-rl, rl-lr ) = max( lr, rl ).
We are almost done, we just have to deal with the case for -1. I’ll try to explain it in a special case the generalize it. Suppose we have 7, 6, 5, 4, 3, 2, 1 then we want \text{RR} but we have \text{LL} but there is no number less than 1 that we can swap 4 or 2 with to get \text{RR}. So answer is -1. In general, we need at least ll + lr elements less than the current element in the array and rl + rr elements greater.
So the algorithm for the problem:
Sort a copy of the array A named B. Calculate an array IND such that IND[i] = index of B[i] in A.
For each query x, calculate ll, lr, rl, rr and do the required math as explained above.
You can find the implementation details in my solution.