FAKEBS - Editorial

PROBLEM LINK:

Practice

Contest

Author: Abdullah Aslam

Tester: Suchan Park

Editorialist: Suchan Park

DIFFICULTY:

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[5] < x, A[8] > x, A[6] < x and A[7] = 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.

1 Like

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

My solution passed through the larger constraints but it failed in smaller subtasks. Are there any weird test cases in subtasks #1 and #2? Please help.

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! :slight_smile:

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