# FAKEBS - Editorial

Practice

Contest

Author: Abdullah Aslam

Tester: Suchan Park

Editorialist: Suchan Park

Easy-Medium

# PREREQUISITES:

How binary search works, greedy argument

# PROBLEM:

You are given a pairwise distinct 1D array A of size N. For each element A[i], find the number of minimum swaps required to make the binary search algorithm that trys to find A[i] successfully find that it is in the position i. We are not allowed to swap A[i]. For details, consult to the problem statement. The binary search algorithm is defined as the following:

integer binary_search(array a, integer n, integer x):
integer low, high, mid
low := 1
high := n
while low ≤ high:
mid := (low + high) / 2
if a[mid] == x:
break
else if a[mid] is less than x:
low := mid+1
else:
high := mid-1
return mid


### QUICK EXPLANATION:

Let’s solve it for fixed i. From the binary search algorithm that finishes at position i, we can find O(\log n) constraints of the form “A[j] < x” and “A[k] > x”. There will be some j s and k s that doesn’t satisfy the given constraints, so let’s define such set of indices as J' and K'. If j' \in J' and k' \in K', A[j'] > x and A[k'] < x holds. So, if we swap these two elements, A[j'] < x and A[k'] > x will hold, so the constraints involving j' and k' both becomes valid. After repeating this as much as possible, at most one of the two sets will be non-empty. In that case, it is possible to just greedily swap with other elements to make such constraint valid, only if there are enough elements to swap. In conclusion, only \max(|J'|, |K'|) swaps are required or it is impossible. It takes only O(\texttt{\# of constraints}) = O(\log n) time to determine everything, we can just fix i = 1, 2, 3, \cdots, n to solve the whole problem in O(n \log n).

### EXPLANATION:

How does the binary search work? It assumes the array A is sorted, and takes an interval [low, high], meaning that there must be an i \in [low, high] such that A[i] = x. Take mid = (low + high) / 2. If A[mid] < x, A[low] < A[low+1] < \cdots < A[mid] < x holds, so the algorithm shrinks the interval to [mid+1, high]. There is no way 1, 2, \cdots, mid can be our desired position. If A[mid] > x, x < A[mid] < A[mid+1] < \cdots < A[high] holds, so the algorithm shrinks the interval to [low, mid-1]. There is no way mid, \cdots, high can be our desired position. One thing we can note here is, if an element is once excluded in the “candidate interval” [low, high], it will never re-appear forever.

For the sake of understanding, let’s draw a decision tree of a binary search, which is a well-known concept. I take a look at the case when n = 9. Internal nodes denotes the case when the answer is not decided. In that case, it will compare A[mid] with x to shrink the interval or find the answer. Leaf nodes of the tree denotes the case when the answer is decided.

Since this is a tree, we can see that there are some unique constraints required to obtain a certain resulting position. For example, if we want the answer to be 7, we have to visit nodes [1, 10], [6, 10], [6, 7] and [7, 7]. So the necessary conditions required are A < x, A > x, A < x and A = x. There will be at most O(\log n) constraints since this is a binary search decision tree (there are at most O(\log n) comparisons). Also, the important constraints will look like “A[j] < x” or “A[k] > x”. A[i] = x constraint is useless since we seek to find position i with parameter x = A[i].

So, let’s think that we want the resulting position to be i when x = A[i].

First thing to check: if there are s_1 constraints of the form A[j] < x and s_2 constraints of the form A[k] > x, there must be s_1 elements smaller than x and s_2 elements larger than x in the array A. This can be checked by looking at the position of A[i] in the sorted array of A.

Suppose this check is passed. Some constraints will be satisfied, others will not. We have to swap elements that appears in the non-satisfied constraints, so that all constraints could be satisfied. Define J' as a set of indices j such that the constraint A[j] < x exists and isn’t true right now. Similarly, define K' as a set of indices k such that the constraint A[k] > x exists and isn’t true right now.

If j' \in J', A[j'] > x holds. Also, if k' \in K', A[k'] < x holds. This inequality looks exactly the same as other constraints. Therefore, if we swap A[j'] and A[k'], both of the original constraints A[j'] < x and A[k'] > x will be satisfied!

If we apply this swap as long as both sets J' and K' are non-empty, eventually both sets will be empty or only one set will be non-empty. If the former case happens, we are done and this is the optimal strategy (minimizes the number of swaps). Otherwise, WLOG let’s say conditions of the form A[j''] < x are left unsatisfied and let those indices as J''. If there are |J''| or more indices p such that A[p] < x, we can swap A[j''] and A[p] for all j''. We can say the same argument for K'' too.

To summarize: Let A[i] be the v-th smallest element of A. Let J be a set of indices j such that the constraint “A[j] < x” exists, and K be a set of indices k such that the constraint "A[k] > x exists. Then,

• If p < |J| (there are less than |J| elements smaller than x) or N - p + 1 < |K| (there are less then |K| elements larger than x), the answer is -1.
• Otherwise,
• If |J'| = |K'|, the answer is |J'|.
• If |J'| > |K'|, the answer is |J'| if v \ge |J'| - |K'|, otherwise -1.
• If |J'| < |K'|, the answer is |K'| if N - v \ge |K'| - |J'|, otherwise -1.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.

2 Likes

Hello,

Thank you for the editorial. I have a question regarding the first condition you put forward where if |J’|=|K’| then the answer is 0. I feel if these two sets are equal then we still have to do |J’| swaps.

Also I would like to know if there is any simpler way to solve the smaller data sets of this problem.

Warm Regards,
Ruddra

Here’s my solution:
FAKEBS - kvmsc

Any help Would be great. Thanks in Advance!

1 Like

Can someone please guide me on how to build test cases for problems like these? It seems I have coded the solution according to the editorial, but can’t seem to pass it.

Here’s a video editorial of the same–

Feedbacks are most welcome! 3 Likes

Yes you’re right, we have to do |J’| swaps as I mentioned above. It was just a typo, thanks for noticing it.

I am writing editorials in a rush since the real editorialist is gone. I’ll write more details about the easier subtasks after I write the editorials for all other problems. In short: subtask 1 can be solved by considering all N! permutations, and subtask 2 is just to avoid number compression.

2 Likes

Subtask1 and subtask 2 are the real deal, because things get tighter for smaller N. Making edge cases are easier for smaller N, especially for this problem. Try to think awhile, if after 1 day you are unable to, then see. N=8 to N=13 were the cases for me.

Nice Explanation