Code for calculating number of variations

Question

Following up from my previous question where I put up a solution in brute for algorithm to this problem from codechef.

Given some number \$K\$ and a list of \$N\$ numbers, count the number of pairs (\$i\$, \$j\$) such that \$1 \le i \lt j \le N\$ and \$|a_i − a_j | \ge K\$.

• \$1 \le N \le 65000\$
• \$1 \le K \le 10^8\$
• \$0 \le a_i \le 10^8\$

I changed my code quite a bit and was able to get rid of that time-limit-exceded error.Thanks to the responses, here is the updated code:

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


std::vector<int>loadTestCases(int N){
    std::vector<int> testCases;
    for (int i = 0; i < N; i++)
    {
        int TestCase;
        std::cin >> TestCase;
        testCases.push_back(TestCase);
    }
    return testCases;
}

int main(){

    int args,k;
    std::cin >> args >> k;

    std::vector<int> nums = loadTestCases(args);
    int cases = 0;

    sort(nums.begin(),nums.end());


    for(int i=1;i<args;i++){
        int temp = std::abs(nums.at(i)-nums.at(i-1));
        if(temp >=k){
            cases = cases + i;
        }else{
            int j = i;
            while(temp < k && j > 0){
                j--;
                temp = std::abs(nums.at(i)-nums.at(j));
            }
            if(temp >= k){
                cases = cases + j + 1;
            }
        }
    }

    std::cout << cases << std::endl;
    return 0;
}

But according to me the code still looks a little ugly and can be optimized more , can someone help me to identify the parts where simplification without risking the time taken can be done?

Answer 1

Similar to the other question, I would suggest to utilize a std::map changing your loadTestCases accordingly

std::map<int, int>loadTestCases(int N){
    std::map<int, int> testCases;
    int TestCase;
    for (int i = 0; i < N; i++)
    {
        std::cin >> TestCase;
        auto inserted = testCases.emplace(TestCase, 1);
        if(!inserted.second) {
            testCases.at(TestCase)++;
        }
    }
    return testCases;
}

The advantage of this approach is, that you only have to traverse the keys of the std::map once and can multiply the values if there is a match.

Also given that your container is sorted you can actually skip the std::abs call, as a_i - a_j > 0 is guaranteed by that sort, if you traverse the container from the back. Also more importantly, once you find a_i - a_l > k, you automatically know, that any following pair is also valid, as by construction for an a_m < a_l we get a_i - a_m = a_i - a_l - (a_m - a_l), with (a_m - a_l) < 0.

Answer 2

Optimize on design level, not source level. Your program performs the following:

1. Read input
2. Sort
3. Find pairs

The respective complexities are \$O(n)\$, \$O(n~log~n)\$ and \$O(n^2)\$ in your implementation. For now, we can ignore 1. and 2. and focus on finding pairs of distance \$\geq K\$ in a sorted set.

A sorted set has a couple of nice properties:

• You must only search for the first element with a sufficient distance to base. You already use that information.
• \$j > i\$. You already use this property too.
• When you find a pair \$(i_1,j_1)\$ and search for another pair \$(i_2,j_2)\$ with \$i_2 \geq i_1\$, \$j_2 \geq j_1\$ must also hold true.

You can base your inner loop on \$j_1\$ instead of \$i_2\$, which eliminates it altogether, making the search \$O(n)\$. The result are two pointers that traverse the set in a single pass. The pointers keep a distance of \$K\$

• If \$d < K\$, the leading pointer advances.
• If \$d \geq K\$, the trailing pointer advances.

and are therefore guaranteed to hit every pair of interest exactly once.

int countPairs(const std::vector<int> sortedNums, int k)
{
    const size_t size = sortedNums.size();
    size_t trailingIndex = 0;
    size_t leadingIndex = 0;
    int count = 0;

    while (leadingIndex < size)
    {
        if (sortedNums[leadingIndex] - sortedNums[trailingIndex] < k)
        {
            leadingIndex++;
        }
        else
        {
            count += size - leadingIndex;
            trailingIndex++;
        }
    }
    return count;
}

Execution time is reduced by an order of magnitude and well within the required limit.

int main(){
    int args,k;
    std::cin >> args >> k;

    std::vector<int> nums = loadTestCases(args);
    sort(nums.begin(),nums.end());

    int cases = countPairs(nums, k);

    printf("%i\n",cases);
    return 0;
}

If you want to improve it any further, you must focus on the sorting algorithm which became the limiting factor (\$O(n~log~n)\$ vs. \$O(n)\$). You may consider using an Integer Sorting algorithm instead of the generic comparison sort.