# FEB-17, MAKETRI Editorial (Unofficial)

Contest

Practice

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
``````
8 Likes

kudos to you bro for such a nice and detailed editorial, awesome explanation and I am sure this editorial is gonna help many newbies and motivate them to enjoy competitive programming. Keep up the good work

1 Like

No bro, to be honest you have a HUGE contribution towards it too!! I was simply in love with your code and the comments you added there. They were simply mind-blowing!

@vijju123 and @inovation123 you both are doing good job. Just keep doing and exploring the coding environment.

Thanks dear

Nice effort @vijju123
A few things:

1. I understand that you explained the problem in detail but the length of the editorial might scare the beginners.
2. Since we are asked to find the combined length of the intervals and not the intervals themselves, we can avoid the stack.
3. We do not need to sort the intervals before going over them because they are guaranteed to be already sorted by their ending values (by triangle inequality).
The last two points will reduce the size of your editorial considerably. I can help you with the code if you are willing to make the changes
4 Likes

@vijju123 Thanks for the complement but seriously editorial is amazing, keep it up

1 Like

Thanks bro

@meooow is right. The editorial is too scary for every one to grip each and every line. This question belong to easy level so i don’t think that there is any need for such a big and bulky explanation. You should try to cut down some part of it so that everyone could able to give time to read this one. I hope you will consider that point.

@meooow. Yeah…length :3. That’s something I tried to contain (and failed miserably lol).

I would love to see your POV too! I sorted the intervals because it was easy to have “feels” when they are sorted by starting positions (and most of the codes I came across used same implementation. So I felt its easier to connect).

Why don’t you put up your POV as an answer? I can redirect the people quoting there “In case you want a quicker way, check meoow’s answer below. Else if its easier to connect with this implementation, proceed below.” Or anything you say. I am perfectly fine with it

We are trying our best. I tried editing and will keep editing till it is best suitable to everyone’s needs. I kinda knew the explanations were bulky, but I don’t want anybody to have a blank face and go googling like crazy after reading editorial. I just wanted this editorial to be independent and self sufficient :). That’s all!

Hey @vijju123 here is my solution. No structs, no stacks, no sorting of intervals. And I think you should update your explanation to make it simpler, it’s your editorial after all

1 Like

Thanks! I shall do the needful by tomorrow evening. (Please excuse me for today, I am dead tired after writing this editorial. I think you can feel me here :p)

finally 20lines accepted C++ code of this problem. Agree with @meooow that rather than doing computation on starting of interval, we can do the job with end of interval which is sorted and eventually we can get a green tick with 20lines.

My code for reference and @vijju123 we now have quite efficient and easy code bro

https://www.codechef.com/viewsolution/13056881

1 Like

Yes bro! I will try my bestest best to edit the editorial and make it crispier by tomorrow evening. Actually I would have done that now…but I have these monstrous college assignments. But truthfully, it was a good learning experience and I hope I get such a support from you, community and everybody here in future as well!!!

sure bro I am a learner myself, just learning bit by bit daily by you all amazing people and I can understand your pain because I have Mid sem knocking the door from next week

1 Like

The editorial is updated and current round of editing (for checking grammar, format) is also complete. People are requested to comment their feedbacks. Specifically I am looking for feedback on-

1. Format
2. Language
3. Clarity of Explanations and Codes
4. Quality of Content.
5. What more I could add/remove to make editorials better.
1 Like

@vijju123 thanks for mentioning my name brother… Please don’t stop giving us such detailed explanation. Thanks again!

You were the prime motivation which made me believe I can also write editorials. You deserved a place there. I hope that the explanation made the Q and its concepts clear to you

Sure it did clear the concepts… Are you on Quora?

1 Like