Calculating number of variations

Question

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 <iostream>
#include <vector>
#include <sstream>
#include <cmath>
#include <cstdio>
using namespace std;
vector<int>split(string s){
 stringstream ss(s);
 string item;
 vector<int> elems;
 while(getline(ss,item,' ')){
 elems.push_back(stoi(item));
 }
 return elems;
}
int main(){
 string one,two;
 getline(cin,one);
 getline(cin,two);
 vector<int> testCases = split(one);
 vector<int> nums = split(two);
 int args = testCases[0];
 int k = testCases[1];
 int cases = 0;
 for(int i=0;i<args-1;i++){
 for(int j=1;j<nums.size();j++){
 int temp = abs(nums[0]-nums[j]);
 if(temp >= 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.

• Incomputable: std::cout is in fact slower, but when you'll find out what it is made of you will be stunned by how fast it is given implementation of it.

Answer 1

This problem is a lot simpler than you think it is.

The printf() isn't saving that much time because the printf() is only executing once per program run. Where the code should be saving time is in the calculating loop.

First it should only be using stream input and output, the code does not need to do the conversion from string to int, this will be handled by stream input and stream output. This will speed up the algorithm a lot.

 int N, K;
 std::cin >> N;
 std::cin >> K;

The split function should probably be renamed to loadTestCases. Once again the conversion from string to int isn't needed. Using the stream input improves the performance of the loop.

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;
}

In the loop where the calculation is done the deletion of the zero element is costing too much time. Rather than erasing the zero element in each loop just index through the vector.

 int cases = 0;
 for(size_t j = 0; j < testCases.size(); j++){
 for(size_t i = 0; i < j; i++){
 if(std::abs(testCases[i] - testCases[j]) >= K){
 cases++;
 }
 }
 }

Using iterators for i and j will speed this code even more.

• hellozee: I can't replace that split function cause the input is provided in a single line with digits separated by spaces , so if I follow your loadtestcases function, this won't work, thanks for the rest of the points, I will keep that in my while doing the next program
• pacmaninbw: using std::cin >> TestCaseValue will ignore the spaces and only take the integer values.
• hellozee: Seriously , have to try that, if that works as you are saying , that would solve all the problems I am facing. Do you have some nice recommendations for learning algorithm? If yes then please share that , cause isn't helping me.
• hellozee: man I would love to kiss (only literally not practically though) , that loadTestCases function has solved most of my problems and now I dont have to use string stream anymore.
• hellozee: hmm well I am still getting a TLE

Answer 2

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<int>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<int> split(const std::string& s){
 // ......
 while (std::getline(ss, item, ' ')) {
 // ......
}

---

Consider your function call that splits a sequence of digits.

 vector<int> 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 < args - 1; ++i) {
 for (int j = i + 1; j < args; ++j) {
 int temp = abs(nums[i] - nums[j]);
 if (temp >= 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 < 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.

• hellozee: Thanks to improve my algorithm, except that last paragraph , I have done everything that was mentioned by @pacmaninbw. I also hate to use that using namespace thing but it improves the readability which is necessary for reviewing

Answer 3

Your nested for loop tests every pair — that is an O(N²) algorithm.

Try sorting the numbers first — an O(N log N) operation — then devise an algorithm that walks the array once to do the count.

• hellozee: Thanks, but same here I was also trying to figure out a loop with logarithmic time but I can't do that, do you have some resources from where I can pick up asymptotic analysis? Cause google is not helping me on that .