https://www.codechef.com/viewsolution/12754753
This is my first answer on Codechef blogs so bear with me
1st things first,since the difference between L and R is so big,it’s obvious we can’t iterate through them.
Meaning,we’ll have to somehow come up with something using the 10^6 numbers given.Now,if you will notice-each pair of sides will cover a range of possible third sides.Given by a lower limit of → a-b+1 & upper limit of → a+b-1. (this is simple maths,we know that for a valid triangle sum of two sides should ALWAYS BE STRICTLY GREATER than the third side).
Now herein comes the main part,ie we need to ennumerate all the possible ranges that can be covered by all the possible pairs of the given 10^6 sides. And voila,it turns into a O(n^2) algorithm just like that eh?
Not so fast,we SORT the sides.Now the ranges formed by taking ADJACENT sides from the sorted array will form the limits on what can be minimum and maximum possible lengths for the third side.
Essentially we get an array of ranges denoting the ranges of the third side.
Now the task boils down to merging L and R with the array of ranges we have got.
The number of sides in the merged array of intervals(between L and R) will give you the requisite answer.
Complexity-O(nlogn) n-> 10^6.
This is my solution.I don’t know whether it can be improved upon.I’d like others to comment on their approaches…