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?

up vote 2 down vote accepted

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.

  • Note that starting from front is equivalent of a_i-a_j < 0 – miscco Aug 28 '16 at 18:54

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.

  • Personally i would not use a while loop if I know the exact range of the loop. EDIT: Sorry, missread the condition. – miscco Aug 29 '16 at 6:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.