Author: kevind
Tester- mgch
NOTES BEFORE READING THE EDITORIAL:
• This editorial is primarily directed to people with moderate experience in programming. Attempt has been made to make it as beginner- friendly as possible. However, people who are well-acquainted/expert in the skills can skip some parts. My chief aim was to provide simple and convincing explanation, that’s all. 
• If you’re a beginner or have had a lot of trouble with this problem, then it is suggested for you to read this editorial with a pen and paper with you for participation in exercises involved. The aim of exercises is, that, instead of convincing you of something, I will help you prove the statement.
• Please tell your valuable feedback in comments :).
DIFFICULTY:
Varies from Moderate to Hard.
My Comments:
What makes this problem hard to impossible for one, while moderate for another is seeing through the trick involved and overcoming its challenging implementation.
PRE-REQUISITES:
The following knowledge is seen to be helpful for solving the problem-
• Law of Triangle Inequality (Mathematical)
• Basic Use of if-else and loops.
• A logical mind, experienced in thinking of clever approaches.
PROBLEM:
We are supposed to tell how many numbers in interval of [L,R] can possibly form triangles with any values given in an array. (Please read problem statement thoroughly)
**ANALYZING THE PROBLEM STATEMENT:**So, while reading the problem statement, what is the first thing which caught your eye? The constraint section! The constraints which the problem setter gave us are quite…interesting to say the least. Have another look at them-
Constraints
• 2 ≤ N ≤ 10^6
• 1 ≤ L ≤ R ≤ 10^18
• 1 ≤ Li ≤ 10^18
The first thing that we notice is a moderately large value for N, and an EXTREMELY HIGH value of L and R. They range from [1,10^18]. This means that even a simple for loop from L to R would take days to complete. The problem setter clearly ruled out the solution of checking every value in [L,R] for conditions of forming triangle.
But we see that the value of N is just moderately large. In fact, its quite small if we compare it to L and R. The value of N hints that “perhaps some kind of operation needs to be done on array to find answer easily.” But don’t get carried away! N is from [2,10^6], meaning we can afford only upto O(NlogN) algorithms. Anything which needs O(N^2) will, by no doubt, give a TLE.
THE FIRST STEP TOWARDS SOLVING IT:
Okay, so we now have quite big constraints to deal with. It is clear that going ‘step by step’, or by any algo which ‘checks every value in range of L and R &etc’ will give TLE. Lets try to look in other direction for now.
What we have to do in this question, is finding how many numbers between [L,R] will make a triangle. But how will we check that? A high school theorem comes handy here-
Let a and b be value of length of sides of triangle (from array) and let c be the third side (some value from [L,R] which we are checking)
For c to be a valid side length, we know that-
c < a+b
But its incomplete. C cannot possibly range from 0 to a+b. The other side of this theorem is-
a-b < c
Combining them-
abs(a-b) < c < a+b
WAIT RIGHT THERE!
I would like to draw the attention of our condition for c to be a valid side length. c must be strictly greater than a-b and strictly less than a+b, or we can say that the value of c must lie in the interval [a-b+1,a+b-1] (since a-b and a+b are excluded)
[Note- in below explanations, it is understood that by “a-b < c” I mean " abs(a-b) < c"]
What was our problem before? That we needed a way by which we can complete program within 3 seconds. Does the interval of c offer any help? Yes it does! Since we now have an interval of C, we know that the values between [a-b+1,a+b-1] are valid. In this way we can actually check multiple values of [L,R] in one go! Understanding this is the first trick towards solving this question. (Read “For beginners below if you are having a doubt in what I explained here)
For Beginners (if not understood above)-
What the above statement said was, lets say we get c belongs to [4,7] interval by above relation, for some a and b. And lets say our interval of L and R was [1,20].
Now, its obvious that, any value from [4,7] is valid choice for c. Since all values of 4 to 7 are valid, we need not check separately for c=4, c=5,c=6 and c=7. In one go we can say that all values ranging from this value to that value are valid. And in this way, we were able to successfully check 4 values of c in one go! This is exactly what I meant when I wrote “we are able to check multiple values of c in one go.”
The first step towards solving this problem was getting this concept right. Since the values of elements in array can range from [1,10^18] , we can successfully check values over a large range of interval in one go. (Eg- Lets say 2 values a and b are 999 and 1000. We can easily conclude that c will be as 1 < c < 1999 or 2 < = c < = 1998. We checked almost 2000 values in one go!)
IMPLEMENTATION:
This is the challenging part of the question. There are around 5 tricks involved here, and these are what made the question have a mere 6% accuracy. So, you got the feel of the question, got the concept of intervals and all. How do we implement it?
Now we have taken the input. The first trick, which I explained above, is to conclude that we have to solve this question using intervals. Intervals are defined explicitly by 2 numbers, the starting number and ending number (eg- Consider [3,10]. 3 is the ‘starting number’ and 10 is the ‘ending number’). It will do us good to make two arrays, each of length n-1, one to store interval’s starting number and other to store interval’s ending number.
I know that this might have raised many questions, like “Why n-1, especially when total number of possible intervals are far greater than it?”
True. Total number of all intervals are far greater [= n(n+1)/2], but I will later show that all those intervals “overlap” and/or “lie completely inside” the intervals I am going to find. For now, we just declare it n-1. (This is the second tricky part)
Now sort the array. This is the third tricky part. Array is sorted to place similar values near each other. In next step, you will see that this makes life easy for finding the required intervals. Now, compute and store possible intervals by computing ONLY ADJACENT values. Meaning, a and b must be COMPULSARILY adjacent. This is the fourth and the trickiest part to understand.
Explanation-
Lets say I have an array A = [1,12,5,8,6]. The intervals possible are –
For 1-
12-1 < c < 12+1; 5-1 < c < 5+1 ; 8-1 < c < 8+1….. and so on.
For 12-
12-5 < c < 12+5; 12-8 < c < 12+8…and so on [note that 12+1 > c > 12-1 is omitted as we already found it above).
.
.
And so on for rest.
BUT THIS CANNOT BE DONE. This would require a O(N^2) time, and as I mentioned earlier, a O(N^2) approach would immediately give us a TLE. We cannot compute every possible interval, store it and check it. And we don’t have to do it. There is a clever way around the problem.
Sort the array. After sorting, you will find that A becomes [1,5,6,8,12]. Then I asked you to compute intervals by taking only adjacent elements. Why?
Because for an interval based on [a-b+1,a+b-1] we can say that-
The length of interval is greatest when computed among similar values. In fact, any interval computed from element other than adjacent elements, will lie COMPLETELY INSIDE the interval computed using adjacent elements.
This is something one has to (and was expected to) conclude from common observations.
/* Beginners Note-
Read this if you’re not convinced as such how length of interval is greater when we take adjacent values. Lets take an example-
Array A is [1,5,6,8,12]
1. Lets compute the interval considering 12 and 8. WE get 12-8 < c < 12+8 . Hence 4 < c < 20 or 5 < =c < =19.
The length of the interval is (which is equal to number of elements in it) =b-a+1= 19-5+1 = 15.
So, we got length of interval as 15, with 5 <= c <= 19.
2. Lets consider any other value instead of 8. Lets say we choose 5. Now the interval is-
12-5< c < 12+5 == > 7 < c < 17 == > 8 <= c <= 16.
Notice closely, this interval of [8,16] is lying COMPLETELY INSIDE the interval [5,19], which we found in 1.
Even if we take the other extreme value, say 1, the interval was, 12-1 < c < 12+1 == > 11 < c < 13 == > c =[12,12] (only value in interval)
Thus, by examples we have proved the statement above. Feel free to take your own examples, play with them for a while and arrive at the same fact which we concluded above.
(If still not convinced, read below)
**Exercise 1** Take any random array, consisting of atleast 3-7 elements. Sort it. And now compute every possible interval. Use this data to prove that only intervals computed using adjacent elements are meaningful to us, and intervals computed using non-adjacent elements lie completely inside them.
This was the most important trick which we used to reduce this O(N^2) computation to O(N)computation! Since intervals formed by non-adjacent elements lied COMPLETELY INSIDE the intervals found via adjacent elements, we only need to compute intervals of adjacent elements as it would include intervals via other combinations inside them.
To be honest, if you have come till here, understanding the concept thoroughly, then bravo dear! 85% of the problem is done. This was the most difficult part to grasp. Now all we have to do is to implement our solution. Just 1 more tricky part is left. Converting our new-found data to answer.
Now, we found the intervals using adjacent elements. And since the array was sorted in ascending order, we can clearly see that intervals are sorted by their end values. Refer to explanation below if under doubt.
**EXPLANATION:**(Recall that elements to right are greater than elements to their left. This means that sum of two adjacent elements on right is greater than sum of 2 elements in left. And their sum is nothing but the end value of intervals. Refer to above example’s array A and find out for yourself by playing with numbers if under doubt!)
What we need to find now, is intersection of our found intervals with [L,R]. There are a total of 5 conditions possible, interval being completely left/right of [L,R] (no intersection), element partially overlapping with [L,R] at left/right, interval lying completely inside [L,R].
FINDING INTERSECTION OF OUR INTERVALS WITH [L,R] (Read only if you don’t know how to implement this)
This is the final tricky part, but if you have understood above clearly, then this part wont pose any problem to you. We will first initialise our answer variable to 0. We also set a variable “low” to R+1 (you will appreciate this later). This variable will store the start point of interval we found the intersection of, and the purpose is to ensure that no element is counted more than once. More detailed working is explained below. Now, we will run a loop from N-2 to 0 (Hint: Number of intervals is N-1, so index of last interval is N-2) as intervals are naturally sorted in ascending order of their end values. When you see our working, you will appreciate that the loop running from N-2 to 0 and purpose of “low” variable are complementing each other.
I roughly divided it into 2 parts here, for convenience.
Note- For all examples below, consider our [L,R] as [15,30], and 5 intervals [3,10] , [12,18] , [19,25] , [28,35] , [40,50]
1 . Intervals lie completely outside (0 intersection).
We first check if found intervals are completely outside [L,R]. Remember, there are 2 possibilities in this case, i.e. interval may completely lie to left of [L,R] or completely to its right. (See intervals [3,10] & [40,50])
To check if an interval is completely towards left (i.e. smaller. See [3,10]), all we need to check is if the end value of interval is less than L. (See in [3,10], 10 < 15 implies the interval lies completely towards left).
To check if an interval lies completely towards right, we check if the start value is greater than R. (In [40,50] , seeing that 40>30 implies that this interval is outside and to the right).
Overall implementation :
if(interval_end[i]<L || interval_start[i]>R)
continue; //You are reminded that the use of continue keyword is skipping that iteration of loop.
Feel free to take some examples to confirm this!
2 . Partially and Completely overlapping Intervals:
This can be dealt in MANY ways. It all up to your own creativity to come up with a solution to count elements in partially overlapping elements! I am going to discuss what is done in the reference code of mine. Firstly, I made sure that the interval’s start point is not less than L, and its end point is not more than R.
Implementation-
interval_start[i] = max(interval_start[i], L);
interval_end[i] = min (interval_end[i], R);
(Consider cases of [12,18] and [28,35]. See how this statement “trims” these intervals to lie inside [L,R])
Now all we have to focus on is, making sure that we count elements correctly. (as there is always a possibility of counting overlapping elements twice.) We do this by considering the two possible conditions.
1 . Here the “low” variable comes to play. Let us take an example to show see its purpose. Let [L,R] be [10,20] and 2 intervals be [11,14] and [16,19]. We pre-defined low as R+1, so its 21 right now.
Now, we will check if the end interval is less than “low”. If its true, then we will count all elements from interval-start[i] to interval-end[i] (Remember- We can do this as we trimmed interval to always lie inside [L,R]!!). Once it is done, we update the value of low to interval_start[i].
Example- (if you are facing difficulty in visualising/thinking)
In first iteration of loop, we considered interval [16,19] (Remember: Loop running from end to beginning!).
Since 19<21, we will now count all elements in interval [16,19], which is, 19-16+1 = 4. We now set new low value as interval_start[i], which is 16.
In next iteration, we check for [11,14]. Since 14<16, we count all elements of this interval too.
(BEWARE- The use of “<=” operator instead of “<” will prove to be suicidal for your code. Consider case of intervals [16] and [16,19]. You will now appreciate why R was pre-defined to R+1 and “<” was used everywhere!!)
2 . There is another possibility of intervals overlapping (like [12,18] and [16,19]). Here the end-value merges into the other interval. Such an interval is ignored by condition above, and we must use another condition. We notice that the starting value of this interval is less than “low” (assume 2nd iteration).
Working: Since condition one is false, this means interval-end[i] >=low. We will now check if interval-start[i] is < low, as if its less than low, this interval is overlapping, and if its more than or equal to low, this interval is already counted. (Check with [16,19] using intervals [12,18] and [17,18])
(NOTE- High stress on use of “<” instead of “<=”)
Lets say its already counted ( like [17,19]), then we need not do anything.
Lets say that the intervals overlap. Where does this overlap start? From “low”. Considering 2 intervals above, overlap is from [16,18]). But elements from [12,15] are distinct. Any relation between last distinct element and low? YES! The final distinct element is low-1. (Check using your own examples!!)
This means we have to add elements from [ interval-start[i], low-1] , and this is equal to low- 1 - interval-start[i] +1 =low- interval-start[i]. We now update low to interval-start[i].
Implementation: Check reference code of me or meooow.
By the end of this loop, we are ready with our final answer.
EXERCISE 2: Come up with a custom array of yours, and repeat the algorithm I gave above for finding intersection. Observe the working. Try and formulate 2-3 corner cases where you feel the code may fail and record the observations.
That’s it, all now we have to do is to print our final answer.
-END OF EXPLANATION.
CREDITS-
The editorial is possible only due to significant contribution of-
aniketsandhya- For motivating me to write editorials
inovation123- Among all the 20-25 codes I saw, his code was best. Also, he was the one who explained the concept to me earlier. Many thanks to him. Seriously, his code is worth seeing. In fact, I have also added his code in the link.
meooow- I got inspired when I saw him post an editorial for BRIBEBEAR. Else I was of thought that its better to leave editorial writing to editorialists. Also many thanks to him for bringing out a simpler, alternative approach!!
Codechef community for its love and support it showered on me.
The 20-25 bunch of people whose codes I shamelessly stalked upon (:p)
IN CASE OF ANY DISPARANCY, ANY DOUBT, FEEL FREE TO COMMENT. I WILL TRY MY LEVEL BEST TO RESOLVE IT.
**COMMENTS ON TESTCASES: ** Well, I did check 2-3 codes of other programming language, and found that they passed the test cases despite lack of checking for “Disjoint intervals” in our stack. To further clear my doubts, I took a C++ program, ran it on test case of-
3 1 20
1 5 15
C++ output -
10
JAVA OUTPUT-
1
If you see, the intervals above are [4,4] U [11,19]. So in total we have 10 elements. I think the problem setter tried to tone down difficulty be not giving test cases of disjoint intervals, and was more than willing to credit us with full points even if we exclude it. Well, despite his leniency that problem had ~6% accuracy rate 
(because, its tough to think and implement this much. It takes time and skills) In case someone comes across a good JAVA code, or any other language’s code, do ping me or add it in your answer. We will appreciate :).
REFERENCE CODES
Vijju123 – My code is just a copy-paste of meooow’s code, with one additional condition for checking intervals lying completely outside [L,R]. Meooow’s code is also completely fine, except that it has a minor bug for test cases where the interval is lying completely towards left. But anyways, his approach and concepts are correct.
The thing is, the problem setter put up lenient test cases for this problem. 2 types of corner cases were not put up. They were satisfied with us working and thinking of continuous intervals in [L,R]. But as I am writing an editorial for it, it is my sole responsibility to check, cross check and come up with a flawless code, which is correct in concept and accounts for all possibilities. Because I don’t want you people to just see the answer, I want you people to absorb the concepts, analyse the mistakes and advance your skills.
I highly advise you people to RE-ATTEMPT this problem after 3-5 days of reading this editorial.
meooow - Kudos to him for showing us this approach!! I highly HIGHLY respect and am indebted to his contribution towards the editorial!!
inovation123- His code for reference. Also, many thanks to him as he was the one who originally explained this Q and its solution to me, in different approach (given below).
Also, in case some of you are trying to build your concepts of advanced Data Structures like Stacks, or “struct” (in C++) you can try solving the Q using them.
Here is inovation123’s unique solution for solving this Q with advanced data types.
MORE TEST CASES
After implementing your program, try to run your code on following test cases-
Input (stdin)
3 1 20
1 5 15
Your Output
10
Input (stdin)
3 10 20
1 5 15
Your Output
9
Input (stdin)
3 50 80
1 5 15
Your Output
0
Input (stdin)
3 1 2
1 5 15
Your Output
0