I want to write an algorithm to count no. of comparisons such that A[i] A[j]> B[i] B[j] where i<j in as less time as possible.

I know the Brute-Force approach for this, but it take O(n^2) time while I need to solve it in less time. I have also explored the approach based on Merge Sort, but it doesn't seem to work properly

#include <algorithm> // for sort

int comparisons = 0;

// sort arrays A and B in ascending order
std::sort(A.begin(), A.end());
std::sort(B.begin(), B.end());

for (int i = 0; i < A.size(); i  ) {
    for (int j = i 1; j < A.size(); j  ) {
        if (A[i]   A[j] > B[i]   B[j]) {
            comparisons  ;
        }
    }
}

CodePudding user response：

Rewriting the condition as A[i] - B[i] > - (A[j] - B[j]), you turn the problem to the detection of C[i] > - C[j]. After sorting, you easily solve this as a merge operation between the array C and the array -C inverted. (There is no need to invert explicitly, just adjust the indexes.) This is done in time Θ(N Log N), unless a faster sort is possible.

CodePudding user response：

As mentioned in a comment, the relation corresponds to C[i] > -C[j], where C[i] = A[i] - B[i].

The count is easy after the sorting of C.

We just have to pay attention to exclude the cases i == j, and to take into account that a direct summation doubles the number of cases.

Complexity is dominated by the sorting: O(n logn).

#include <iostream>
#include <vector>
#include <algorithm>

int n_compar_bf (const std::vector<int>& A, const std::vector<int>& B) {
    int comparisons = 0;
    for (int i = 0; i < A.size(); i  ) {
        for (int j = i 1; j < A.size(); j  ) {
            if (A[i]   A[j] > B[i]   B[j]) {
                comparisons  ;
            }
        }
    }
    return comparisons;
}

int n_compar_opt (const std::vector<int>& A, const std::vector<int>& B) {
    int n = A.size();
    std::vector<int> C (n);
    for (int i = 0; i < A.size(); i  ) C[i] = A[i] - B[i];
    std::sort (C.begin(), C.end());
    int comparisons = 0;
    int right_index = n-1;
    for (int left_index = 0; left_index < n; left_index  ) {
        while ((C[left_index] > -C[right_index]) && (right_index >= 0)) {
            right_index --;
        }
        comparisons  = (n-1-right_index);
        if (right_index <= left_index) comparisons --;  // to exclude the case i==j
    }
    comparisons /= 2;   // because pairs (i, j) have been counted twice
    return comparisons;
}

int main() {
    std::vector<int> A = {2, -4, -5, 8, 1, 13, 0, 2};
    std::vector<int> B = {5, 2, -2, -13, 0, 4, 7, 5};
    std::cout << "brute force: " << n_compar_bf (A, B) << "\n";
    std::cout << "new: " << n_compar_opt (A, B) << "\n";
    return 0;
}

CodePudding user response：

I have done the following implementation now, but it seems to give 1 less than the ans in some cases, I can't figure out why. One such input case is included in this code.

#include <iostream>
    #include <algorithm> // for sort
    
    int count_comparisons(std::vector<int>& A, std::vector<int>& B) {
        int comparisons = 0;
    
        // define C as A[i] - B[i] for all i
        std::vector<int> C(A.size());
        for (int i = 0; i < A.size(); i  ) {
            C[i] = A[i] - B[i];
        }
    
        // sort C in ascending order
        std::sort(C.begin(), C.end());
    
        for (int i = 0; i < A.size(); i  ) {
            // count the number of values C[j] to the right of i where C[i] > A[i] - B[i]
            int count = A.size() - (std::upper_bound(C.begin(), C.end(), -C[i 1]) - C.begin()) - 1;
            comparisons  = count;
        }
    
        return comparisons/2;
    }
    
    
    int main() {
        std::vector<int> A = {5,10,5, 7};
        std::vector<int> B = {2, 4, 6, 8};
    
        int comparisons = count_comparisons(A, B);
        std::cout << "Number of comparisons: " << comparisons << std::endl;
    
        return 0;
    }