Insert elements from one array to another such that inversions are minimised

Question

Let say I have array A and B ( always equal size) A = 5 4 2 1

B = 8 3 6 7

I am to insert elements from B in to A while keeping the relative order of A while minimising inversions.

So the answer would be 3 5 4 1 2 6 7 8 (7 inversions)

I have tried sorting B first then poping min(a[0] b[0]) into an array C but cases like A = 99999 1 2 3

B = 5 6 7 8

Gives the wrong 5 6 7 8 99999 1 2 3 (15 inversions)

When the correct is 99999 1 2 3 5 6 7 8 (7 inversions)

I am at a lost please help

Answer 1

Okay, this is an interesting question. My current solution works in O(nlog(n)).

The logic behind this solution can be found here.

However, since there was no implementation there, I've decided to place it here.

The overall logic relies on two things:

1. For the array that does not need to maintain order, sort it in O(n log n).
2. Find the middle element, and insert it into the location in the array that minimizes inversions. This can be done in T(2n) = O(n).
3. The elements to the left of that middle element in the sorted array should be on the left of that element in the combined array to minimize inversions. The elements to the right of that middle element in the sorted array should be on the right of that element in the combined array to minimize inversions. This knowledge reduces the space you have to search to find the insertion point with least inversions each iteration. Hence, you can recurse by applying the above logic on the left half of the sorted array with the left half of the combined array.

Now, onto the code:

#include <bits/stdc++.h>
using namespace std;

long long merge(vector<int>& v, int temp[], int left, int mid, int right) {
    int i,j,k;
    long long inv_count = 0;

    i = left;
    j = mid;
    k = left;

    while ((i <= mid - 1) && (j <= right)) {
        if (v[i] <= v[j]) {
            temp[k++] = v[i++];
        } else {
            temp[k++] = v[j++];
            inv_count += mid - i;
        }
    }

    while (i <= mid - 1)
        temp[k++] = v[i++];
    
    while (j <= right)
        temp[k++] = v[j++];
 
    for (i = left; i <= right; i++)
        v[i] = temp[i];
    
    return inv_count;
}

long long _mergeSort(vector<int>& v, int temp[], int left, int right) {
    int mid; 
    long long inv_count = 0;
    if (v.size() < 2) return 0;
    if (right > left) {
        mid = (right + left) / 2;
        inv_count += _mergeSort(v, temp, left, mid);
        inv_count += _mergeSort(v, temp, mid + 1, right);
        inv_count += merge(v, temp, left, mid + 1, right);
    }
    return inv_count;
}

long long countInversionsInVector(vector<int>& v) {
    int temp[v.size()];
    return _mergeSort(v, temp, 0, v.size() - 1);
}

void solveHelper(vector<int> &a, int sa, int ea, vector<int>& b, int sb, int eb, vector<int>& I) {
    if (sb >= eb) return;
    int mb = (sb + eb) / 2;
    int b_elem = b[mb];
    
    vector<int> sliced_a(ea - sa + 1);

    for (auto index = a.begin() + sa; index < a.begin() + ea; index++) {
        sliced_a.push_back(*index);
    }

    long long invCount = 0;
    for (long long i = sa; i < ea; i++) {
        if (a[i] < b_elem) {
            invCount += 1;
        }
    }

    long long minInvCount = invCount;
    int insertionIndex = sa;

    for (int i = sa; i < ea; i++) {
        if (a[i] < b[mb]){
            invCount -= 1;
        } else {
            invCount += 1;
        }

        if (invCount < minInvCount) {
            minInvCount = invCount;
            insertionIndex = i + 1;
        }
    }

    I[mb] = insertionIndex;
    
    solveHelper(a, sa, insertionIndex, b, sb, mb, I);
    solveHelper(a, insertionIndex, ea, b, mb + 1, eb, I);
    return;
}

void mergeFinal(vector<int>& a, vector<int>& b, vector<int>& I, vector<int>& final) {
    int index_a = 0;
    int index_b = 0;
    for (int i = 0; i < 2 * a.size(); i++) {
        if (i == I[index_b] + index_b) {
            final[i] = b[index_b];
            index_b++;
        } else {
            final[i] = a[index_a];
            index_a++;
        }
    }
}

long long solve(vector<int>& a, vector<int>& b) {
    sort(b.begin(), b.end());
    vector<int> I(b.size());
    solveHelper(a, 0, a.size(), b, 0, b.size(), I);
    
    vector<int> final(2*a.size());
    mergeFinal(a, b, I, final);
    
    return countInversionsInVector(final);
}

int main() {
    int n;
    ios_base::sync_with_stdio(false); // speed up reading input
    cin >> n;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < n; i++) {        
        cin >> b[i];
    }

    cout << solve(a, b) << "\n";
}