CodeChef Chewing challenge

Question

The ZCO is today and I did 5 problems to prepare for it overnight. One of the problems is the CodeChef Chewing problem.

The code takes an integer N that specifies the number of chewing gums, integer K that is the maximum hardness quotient of a pair the chewing gums possible to be eaten. This is followed by N integers that specify the hardness quotient of each type of gum. My code selects only gums with a quotient less than K and adds them to a vector. A nested for loop is used to count the number of pairs for which hardness quotient of Gum_Type1+Gum_Type2 < K.

#include <iostream>
#include <vector>
#include <algorithm>
#define ll unsigned long long int
#define speedup ios::sync_with_stdio(false); cin.tie(NULL);
using namespace std;

int main(){
  speedup;
  ll N,K,hq,numPairs=0;
  vector<ll> hardness;
  cin >> N >> K;
  for(ll i=0; i< N; i++){
    cin >> hq;
    if (hq< K) hardness.push_back(hq); 
  }
  sort(hardness.begin(), hardness.end());
  for(vector<ll>::iterator it=hardness.begin(); it<hardness.end();it++){
    for(vector<ll>::iterator it2=it+1;it2<hardness.end();it2++){
      if (*it+*it2 < K) numPairs+=1;
      else hardness.erase(it2);
    }
  }
  cout << numPairs<<endl;
}  

For subtask 2, I'm getting TLE by 0.01s. Could somebody help me optimize this code? I don't want to get TLEs in the exam today.

Answer 1

1. Do not use namespace std; It is a bad practice that you should stop as soon as possible.

2. Do not trust magic macros like speedup. For such small code fragments that are repeated only few time it is often way better to write it out.

3. use std::size_t instead of unsigned long long int

4. You already know the maximum number of chewing gums, So reserve space for your vector early to avoid reallocations. You can always later call shrink_to_fit to free the unneded memory.

5. Use descriptive names even in challenges that only call them N or K. N is the number of gums so call it numGums or whatever you want. This improves readability quite a bit. This also goes for example hardness, which is a vector so it should be plural e.g. hardnesses.

6. Declare variables when you need them. This creates more or less independent code paths that might late be put into functions more easily.

7. In your loop you use it++. This requires a copy of it before the increment. Especially for iterators and friends ++it is more efficient as it does not involve the copy.

8. Try to separate command flow with a whitespace, e.g. for (). This helps to discriminate it from normal functions.

9. EDIT C++11 knows the language construct nullptr, use it rather than NULL

The early portion of our code would then look like this

std::ios::sync_with_stdio(false); 
std::cin.tie(nullptr);
std::size_t numGums, chewingThreshold;
std::cin >> numGums >> chewingThreshold;

std::vector<std::size_t> hardnesses;
hardness.reserve(numGums);
for (std::size_t gum = 0; gum < numGums; ++gum) {
    std::size_t hardness;
    std::cin >> hardness;
    if (hardness < chewingThreshold) {
        hardnesses.push_back(hardness);
    }
}
hardnesses.shrink_to_fit();

If you look at this code in a year, you will still understand most of its meaning, without having to search for documentation.

9. Avoid single line command flow statements like if (*it+*it2 < K) numPairs+=1; as much as possible. This completely breaks readability of your code as you know have to check every for and if statement if it has a coomplicated condition or hidden code or nothing at all.

10. Your code does work, but it is highly inefficient from a mathematical point of view. As a hint I would suggest you think about how to utilize a std::map for this problem.

Answer 2

Possible optimization:

 for (vector<ll>::iterator it = hardness.begin(); it < hardness.end(); it++) {
    for (vector<ll>::iterator it2 = it + 1; it2 < hardness.end(); it2++) {
      if (*it + *it2 > K) break;
      numPairs += 1;
    }
  }

Basically skip erase if the pair is too large and instead break the iteration.