Counting pairs of integers whose sum is less than a given threshold

Recently I was going through this codechef problem while practicing for the upcoming zoc.

The problem asks to calculate number of combinations of the given numbers where the sum is less than another given number.

Previously I had a bruteforce algorithm which gave the correct answer but took a lot of time, in some cases even more than a second which raised a TLE error in codechef.

I changed my whole algorithm to get rid of that TLE error and also almost got that but for the last test it still gets stuck.

#include <iostream>
#include <vector>
#include <algorithm>
int main(){
std::vector<long long> tstCases;
std::vector<long long> okset;
std::vector<long long> testset;
for(int i =0;i<2;i++){
long long cases;
std::cin >> cases;
tstCases.push_back(cases);
}
long long n = tstCases.at(0);
long long k = tstCases.at(1);
for(long long i =0;i<n;i++){
long long cases;
std::cin >> cases;
if(cases<=k){
if(cases < k/2){
okset.push_back(cases);
}else{
testset.push_back(cases);
}
}
}
long long l = okset.size();
long long p1 = (l*(l-1))/2;
long long p2 = 0;
sort(testset.begin(),testset.end());
for(long long itr1 : okset){
for(long long itr2 : testset){
if(itr1+itr2 >= k){
break;
}else{
p2++;
}
}
}
long long p = p1+p2;
std::cout << p << std::endl;
return 0;
}


Note : I am using long long because the problem instructed me to do so and I am lazy enough to do it by myself so I used replace all. Sorry for that.

• The problem states you're counting the pairs whose sum is less than k, not greater. – RichN Aug 24 '16 at 15:21
• I am not counting them , if I were there wont be any green marks on that picture – hellozee Aug 24 '16 at 16:53
• What you may and may not do after receiving answers. I've rolled back Rev 3 → 2. – 200_success Aug 26 '16 at 13:51
• there's nothing about posting the code which I finally used to solve the problem – hellozee Aug 26 '16 at 17:06

A better algorithm

Your current algorithm has a worst case time of $O(n^2)$, when the list is half filled with zeroes, and half filled with k/2. You can solve the problem in $O(n \log n)$ time by doing the following:

1. Sort the input.
2. Use two indices, one starting at the low end and one starting at the high end. Call these indices i and j.
3. For each i, walk j down until a[i] + a[j] < k. When this happens, add j-i to the solution count, and increment i. Do not reset j.
4. Stop when i >= j.

Steps 2-4 solve the problem in $O(n)$ time, but the sort in step 1 takes $O(n \log n)$ time. Here is a code snippet to illustrate the key part:

for (int i=0, j=len-1; i < j; i++) {
while (j > i && a[i]+a[j] >= k)
j--;
count += j - i;
}

• your solution is nice but should not that while loop + for loop take O(n^2) time , just a question , I am really a beginner though – hellozee Aug 25 '16 at 8:35
• your answer will be costly if i implement that in vectors , please can you modify your code for faster implemetation for vectors – hellozee Aug 25 '16 at 8:48
• @KuntalMajumder No because neither i nor j ever move backwards, so the inner loop will run at most len times total. In a typical nested loop, the inner loop counter j would be reset, leading to $O(n^2)$ time. Why do you think this loop will run slow using vectors? – JS1 Aug 25 '16 at 8:48
• ahh there I see. – hellozee Aug 25 '16 at 8:49

This won't speed up your program but, since this is a code review site, I recommend simplifying this section of code:

std::vector<long long> tstCases;

for(int i =0;i<2;i++){
long long cases;
std::cin >> cases;
tstCases.push_back(cases);
}
long long n = tstCases.at(0);
long long k = tstCases.at(1);


to this:

long long n, k;

std::cin >> n >> k;


Possible Optimizations

If you're on a 64-bit system, the long long won't be an issue. On a 32-bit system, however, it could add to the execution time. The problem description indicates everything will fit in a 32-bit integer except, possibly, the solution. I'd replace long long with int everywhere but the p2 counter.

I don't fully understand your reason for splitting the input values into okset and testset. I think you might have a bug in that you may not include solutions where both numbers are less than k/2. For instance, does your solution find all the solutions for this

3 5
1 1 3


I think the answer is 3.

I think you can solve this problem with a single array. If you solve it with one array, you can replace:

std::vector<long long> okset;
std::vector<long long> testset;

for(long long i =0;i<n;i++){
long long cases;
std::cin >> cases;
if(cases<=k){
if(cases < k/2){
okset.push_back(cases);
}else{
testset.push_back(cases);
}
}
}


with

std::vector<long long> input;

input.reserve(n);
for(long long i = 0; i < n; ++i) {
long long tmp;

std::cin >> cases;
input.push_back(tmp);
}


Since you know how many values you need to compare (n), you can use .reserve() to preallocate enough memory to hold the input data. This avoid the many re-allocations and copies that would happen with a large data set.

Your idea of sorting the numbers is good. With large data sets, I think it'd be faster to sort (n log n) and stop intelligently than to brute force every combination (n ^ 2). I'll let you investigate this approach on your own.

• Nope if the input is 3 5 and then 1 1 3 , the ouput will be 4 because here k/2 is 2 which include 1 1 i.e 2 , then p1 = 2*(2-1)/2 = 1,now as 3 is greater than 2 it will be included in the test set where I will use bruteforce to compare which will give me p2 = 2, hence p =p1 +p2 = 3. Tada , the previous algorithm was pure brute force which took O(n^2) time but this one takes O((n-x)^2) time where x = number of elements in testset for the worst possible situation,though both are quadratic the 2nd one takes much lesser time thus helping me pass the first 2 test in the subtask 2.Thanks for helping – hellozee Aug 24 '16 at 17:04
• Please can you upvote my question so that I can upvote your answer , really liked the details you included. – hellozee Aug 24 '16 at 17:07
• Interesting optimization! I'll have to give it some thought; it's not obvious to me why it works. I uprooted your post because it is a possible solution that isn't (to me) obvious. – RichN Aug 24 '16 at 20:34
• oops I made a mistake x is the number of elements not in the testset , i.e total number of items in okset + items which were not pushed into any of the vectors during input time. Thanks to MIT opencourse ware to help me – hellozee Aug 25 '16 at 5:30

There seems to be a tiny mistake in your vector assignment:

if(cases <= k)


should actually be

if(cases < k)


It can be, that this is already triggering the relevant test case, if the input has lot of K entries. I really like your separation into "safe" numbers and those above K/2.

Another way to address the computation here would be to use a map and sum up identical cases. So rather than pushing back a vector for every input you could do something along the lines.

std::pair<std::map<size_t, size_t>::iterator,bool> ret;
for(long long i =0;i<n;i++){
long long cases;
std::cin >> cases;
if(cases < k) {
if(cases < k/2){
okset.insert(std::pair<size_t, size_t>(cases, 1);
if (!ret.second)
okset.at(cases)++;
}else{
testset.insert(std::pair<size_t, size_t>(cases, 1);
if (!ret.second)
testset.at(cases)++;
}
}


The advantage might be, that for many repetitions of few entries you save a second full iteration as you can then do something along the lines

for(auto itr1 : okset){
for(auto itr2 : testset){
if(itr1.first+itr2.first >= k){
break;
}else{
p2 += (itr1.second+itr2.second)*
(itr1.second+itr2.second-1)/2;
}
}
}


However, it is not really clear whether this is really better.

• Thanks for noticing that, I really made a mistake there but ,still the result is same , last one has a TLE , but the excution time has come down from 0.34s to 0.33s apart from the last one – hellozee Aug 25 '16 at 5:39
    std::vector<long long> tstCases;
std::vector<long long> okset;
std::vector<long long> testset;
for(int i =0;i<2;i++){
long long cases;
std::cin >> cases;
tstCases.push_back(cases);
}
long long n = tstCases.at(0);
long long k = tstCases.at(1);


Make sure you understand the requirements of the problem. From the problem page, we see

$$0 \leq K \leq 1,000,000\\ Subtask_1: 2 \leq N \leq 2000\\ SubTask_2: 2 \leq N \leq 100,000$$

Whenever values are within a sane countable range, just use int. Once a number gets to a point you wouldn't want to personally count to, say a couple thousand, then move to the fixed width types provided by <cstdint> (std::int32_t, std::int64_t). For this problem, N and K are best represented at 32-bit integer types (std::int32_t) instead of long long (which is at least a wasteful 64 bits).

The worst case scenario for this problem is that every pair meets the hardiness limit. The first few $N$'s produces counts of $[1, 3, 6, 10, 15, 21]$, which would be the sequence for the triangle numbers. $N = 100,000$ would be the $99,999^{th}$ triangle number for our sequence (started at 1). To find the $n^{th}$ triangle number, we can use the formula

$$T(n) = \frac{n(n+1)}{2}$$.

So,

$$T(99,999) = \frac{99,999(100,000)}{2} = 4,999,950,000$$.

Use of a 64-bit integer would be more appropriate since a 32-bit integer cannot store that worst case count size.

You can minimize (re)allocations by reserving space before appending to your container. We know how large the data set is going to be because it's provided by the subtasks as the first value read. Use the information provided.

Keep functions short and simple making them easier to read and test. Functions should perform a single logical operation. Look for opportunities to reuse code.

An example; Let's start with some basic IO helpers that uses NRVO. You can extend it to print out prompts, validate input, but for this exercise, it's something basic and can be used on all of the challenge sites.

#ifndef IO_READ_H
#include <algorithm>
#include <iosfwd>
#include <iterator>
#include <vector>

namespace io {
template <typename Result>
Result result{};
in >> result;
return result;
}

template <typename Result>
std::vector read_n(std::istream& in, std::size_t element_count) {
std::vector<Result> results;
results.reserve(element_count);
std::copy_n(std::istream_iterator<Result>(in), element_count,
std::back_inserter(results));
return results;
}
} // namespace io
#endif


Now in your program, you get straight to the point. Keep main() clean. Use it to parse/forward command-line arguments and configure the environment in which your tests/program will operate in.

void run_zoc13003() {

std::sort(hardiness_quotients.begin(), hardiness_quotients.end());
// .. calls to other functions to do work.
}

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
run_zco13003();
}


I changed my whole algorithm to get rid of that TLE error and also almost got that but for the last test it still gets stuck.

Your program still attempts to brute force it's way through the sequence, comparing each and every element in the worst case ($O(n^2)$). Exploit the properties of the sequence (sorted/contiguous). You can search for things efficiently. For each element, find the first element that falls below the limit (reverse linear search). The elements beyond that point would make invalid pairs. Elements upto that point can be summed with your current element to make a valid pair. Since we are only interested in unique pairs, we just count the number of gums between our current gum and its pair.

Consider the equation $A_i + A_j = K$. If $K$ never changes and the value of $A_i$ increases, we would expect the value of $A_j$ to decrease. Since they are converging, you can resume your search from where you left off. Once $i == j$, you've exhausted all the possible unique combinations. Putting all of this together, you have an algorithm that counts the valid pairs in $O(n)$ time. Combined with the $O(n log(n))$ sort, it's still much faster than your brute-force approach.

You can also optimize for the special case that the last two elements are below the limit. If they are, you just calculate the triangle number in constant time.

• Thanks for that last part , I should have thought that way instead . – hellozee Aug 25 '16 at 8:42

@RichN, i think you approach is sound, but it misses one crucial point that makes the presented code so fast. For numbers that are smaller than K/2 every combination is valid. Therefore, it is not necessary to loop over those and one can directly set the number of combinations to

n (= number of items smaller k/2) over 2 = n*(n-1)/2


This will almost every time be faster than sorting. Also note, that with splitting the array in two, only the testset needs to be sorted, which also reduces complexity considerable.

On the other hand if the ok set was sorted too, one could end the second loop earlier, knowing that the number in testset must be smaller than K - okset:

long long l = okset.size();
long long p1 = (l*(l-1))/2;
long long p2 = 0;
sort(okset.begin(),okset.end());
sort(testset.begin(),testset.end());
for(long long itr1 : okset){
for(unsigned i = 0; testset.at(i)< K-itr1; i++){
p2++;
}
}

• Thanks , I thing using iterators for the testset will make the code even faster. – hellozee Aug 25 '16 at 8:44
• Note that the second loop mimmiks what Snowhawk04 said. The larger the first summand the smaller the second – miscco Aug 25 '16 at 17:38
• ahh thanks and now I am confused which one to choose as answer – hellozee Aug 25 '16 at 18:30