Calculating number of variations I was practicing for the upcoming zco in CodeChef, where I came across this problem:


  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 got the algorithm correct for \$N \le 4000\$, but for \$N \le 65000\$, it failed to compute in the given time limit. 

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;sstream&gt;
#include &lt;cmath&gt;
#include &lt;cstdio&gt;

using namespace std;

vector&lt;int&gt;split(string s){
    stringstream ss(s);
    string item;
    vector&lt;int&gt; elems;
    while(getline(ss,item,' ')){
        elems.push_back(stoi(item));
    }
    return elems;
}

int main(){
    string one,two;
    getline(cin,one);
    getline(cin,two);

    vector&lt;int&gt; testCases = split(one);
    vector&lt;int&gt; nums = split(two);

    int args = testCases[0];
    int k = testCases[1];
    int cases = 0;

    for(int i=0;i&lt;args-1;i++){
        for(int j=1;j&lt;nums.size();j++){
            int temp = abs(nums[0]-nums[j]);
            if(temp &gt;= k){
                cases++;
            }
        }
        nums.erase(nums.begin());
    }

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


I tried to use the printf instead of std::cout, because I read somewhere that it is much faster than the latter, but the result was same. How can I overcome the TLE? I also tried some few more tricks but they somehow altered the algorithm as a result they were giving wrong outputs.
using namespace std;


See Why is using namespace std in C++ is considered bad practice on why you should avoid using directives at the global scope.



vector&lt;int&gt;split(string s){
    // ......
    while(getline(ss,item,' ')){
    // ......
}


Horizontal spacing helps readability by distinguishing language constructs.  Unless you are code golfing, you should write code for correctness and readability.

std::vector&lt;int&gt; split(const std::string&amp; s){
    // ......
    while (std::getline(ss, item, ' ')) {
    // ......
}




Consider your function call that splits a sequence of digits.

    vector&lt;int&gt; nums = split(two);


How many allocations/reallocations are being made in split()?

Every time you call split(), you are passing the arguments in by value.  Prefer to pass by value when parameters are cheap to copy.  Otherwise, pass by reference (to const if immutable) when parameters are expensive to copy or have an unknown cost. Determining the cost is architecture dependent. For most systems today, anything more the two or three words (size of a double or reference) should be considered expensive.

When creating the sequence, elems.push_back() will do many reallocations.  The amount of reallocations is implementation dependant upon the std::vectors growth factor.  The sequence length is one of the input parameters of the problem.  Use that length to reserve the space before reading.



nums.erase(nums.begin());


Again, avoid unnecessary copies.  Every time nums.erase() is called, you are copying all the remaining elements in the sequence.  You could avoid the calls by just using i and j as the indices.

    for (int i = 0; i &lt; args - 1; ++i) {
        for (int j = i + 1; j &lt; args; ++j) {
            int temp = abs(nums[i] - nums[j]);
            if (temp &gt;= k) {
                ++cases;
            }
        }
    }





  I tried to use the printf instead of std::cout, because I read somewhere that it is much faster than the latter, but the result was same. How can I overcome the TLE? I also tried some few more tricks but they somehow altered the algorithm as a result they were giving wrong outputs.


99% of problems on these code challenge sites will produce TLE's because of your algorithm and not the I/O method being employed.  In the case of scanf/printf vs std::cin/std::cout, I prefer the latter for these types of exercises.  If you really need the performance of C formatted I/O from C++ IOStreams, consider the following:


Disable synchronization 

std::ios::sync_with_stdio(false);

Untie the streams. 

std::cin.tie(nullptr);

Avoid unnecessary flushes (prefer '\n' to std::endl).




A better approach, avoid reading as a std::string and tokenizing.  Read the arguments as their intended type. Ensure you reserve space in your std::vector before reading values.

We can make improvements to the algorithm through sorting. The problem states as one of the preconditions that \$i &lt; j\$.  With a sorted sequence (in ascending order), every element is guaranteed to be less than or equal to the elements that follow it.  When you find one element that meets the variation threshold, every element after that also meets the threshold.  To find the first element that meets that threshold, C++ provides both linear search (std::find_if()) and binary search (std::lower_bound()).  Since the sequence is sorted, binary search should be the faster search for any meaningful sized sequence.  Use std::distance to find the counts, use std::accumulate to sum those counts.  Just using the standard library produced a top-10 time on codechef for c++14.