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.

• miscco: Note that starting from front is equivalent of a_i-a_j < 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.

• miscco: Personally i would not use a while loop if I know the exact range of the loop. EDIT: Sorry, missread the condition.