 # FEB-17, MAKETRI Editorial (Unofficial)

Contest

Practice

Author: kevind

Tester- mgch

• 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.

DIFFICULTY:
Varies from Moderate to Hard.

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  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
10

Input (stdin)
3 10 20
1 5 15
9

Input (stdin)
3 50 80
1 5 15
0

Input (stdin)
3 1 2
1 5 15
0
``````
8 Likes

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

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

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!

Awesome editorial. Explanation was very nice. I wouldn’t say cut your editorial as it has been already said. Keep writing editorials like this it will surely help all of us here. Also DEC16 Editorials are pending. If you can cover them it would be a great help.

May u get lots n lots of AC everyday!

One of the best editorial i have seen till date keep it up bro…
made my day keep it up

After reading this editorial, I think that we must not wait for office editorial, soon after the contest is end, we can write editorial by discussing with our fellow contestants. Slack or facebook group chat will be fine for our conversation.

P.S.:- We must take care that we should not break spirit of codechef by discussing problems before hand.

Just an idea. Need reviews.

@swamicoder I agree with you. This is our community and we should be sharing our ideas and contribute to maximize the knowledge building. I am fortunate to have been a small part of journey of this editorial and I remember that it all started with this question

https://discuss.codechef.com/questions/91822/your-logic-for-chef-and-triangles

Now I would like to say one thing. My IAS research topic was Crowdsourced Knowledge Building: Finding Ideal Skillset distribution for maximal knowledge building. I found a mathematical model for the same and thus I would just give a glimpse of the dynamics of knowledge building in crowd sourced environment like StackOverflow, Wikipedia, Quora or our CodeChef discuss community. I will stick to CodeChef discuss community for explanation.

Lets frame base for our understanding. KBS is knowledge building system (CodeChef discuss community) in this case. KU stands for Knowledge Unit. For Q-A community KU is question,answer or vote. Now most important concept in crowdsourced knowledge building is triggering and internal knowledge.

Internal knowledge as the name suggests refers to the knowledge which you possess which is quite small and is constant for isolated system. Major component of knowledge building is Triggered knowledge .

I will give a simple example to simplify things. Suppose I ask you the names of states of India and you say 16 names rapidly, this is your internal knowledge. But then you get stucked and then I give you a hint of say Haryana and you immediately get names of its neighbouring states like Punjab, Uttarakhand etc. This is triggered knowledge. Had I not prompted Haryana, you might not have recalled these names. This is called Triggered knowledge (Recollected Triggered Knowledge).

Triggering is like throwing apples to each other. Best thing is that one KU triggers other KU by some factor which is called triggering factor. Thus, simplifying the stuffs, had the above question not been asked, then we might not have answered and thus our approach might not have come into notice. Also had this question not been asked, some of us might have still been struggling to tackle this problem. Thus, this question triggered some of us and we answered the question, thus adding new KU(answers or unique approaches to the problem) to the KBS which was possible only due to triggering.

Thus, on the whole, I want to say that we should be sharing our approaches and discussing rather than complaining for editorials because this will trigger some of us and we will get some KU in our KBS which would never have come in the community.

I know this might be hectic for most of you and there are various terms like Newton hypothesis, Ortega hypothesis, Internalization, Externalization etc. But @swamicoder your idea has triggered me to apply skillset model for CodeChef discuss community to maximize knowledge building of this community. I framed my model for StackOverflow and Wikipedia but this can be applied here as well.

Please note that I am neither publicizing my research nor my approach to this problem In case anyone did not get idea of triggering or if anyone wants to explore more they can drop a comment.

And @vijju123 kudos to you bro again for an awesome editorial and keep up the good job.

Thanks

Gonna implement on my own.
thanks mate.

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

done !
it will work for the disjoint cases right?

@ashishsb95

Yes, your code is perfectly fine and it is running for disjoint cases too. I am sorry for replying late, I have an assignment due today, so I m kinda running here and there for material (XD).

Side Note: Do you people want me to put up those additional test cases too? Cause I thought that one could check himself/it’d be enough to see the reference codes. If you people need something more in editorial then suggestions are always welcome! @utsavgoel

Your code fails to check if the possible values of triangle lie inside interval of [L,R] or not. See here. If your run your code against the 3rd corner case I posted in the end, your code would fail as-

``````Compilation Successful
Input (stdin)
3 50 80
1 5 15
-74
``````

It simply updates the values without checking if the lower/upper limits are inside L and R or not. You will take max of start[I] and L, but what if start[I] is more than R? Similar argument holds for end[I].

Check the reference codes carefully. We put have used-

``````if(interval_end[i]<L || interval_start[i]>R)
continue;
// make sure we don't go less than L
interval_start[i] = max(interval_start[i], L);
interval_end[i] = min (interval_end[i], R);
``````

The if statement at the start is worth million dollars, as it would immediately skip the iteration if the intervals lie completely outside [L,R]. Hope that clarifies your doubts 1 Like

Thanks @vijju123 for this excellent editorial and also to @meooow for his clear solution
Thank you very much learnt a lot and very happy that count of partially solved problems decreased by one:)

@vijju123 @meooow @inovation123
What is wrong in this submission. https://www.codechef.com/viewsolution/16147596

``````    import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;
class MAKETRI {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
BigInteger l = in.nextBigInteger();
BigInteger r = in.nextBigInteger();
BigInteger arr[] = new BigInteger[n];
for(int i=0;i<n;i++)
arr[i] = in.nextBigInteger();

Arrays.sort(arr);

Range obj[] = new Range[n-1];
for(int i=0;i<n-1;i++){

}

//finding range in O(n)
for(int i=n-2;i>=0;i--){
if(obj[i].start.compareTo(r)>0 || obj[i].end.compareTo(l)<0){
continue;
}
BigInteger effEnd = low.min(obj[i].end);

BigInteger effStart;
if(obj[i].end.compareTo(low) >= 0){

effEnd = effEnd.subtract(BigInteger.ONE);

}
if(obj[i].start.compareTo(l) < 0)
effStart = l;
else
effStart = obj[i].start;
low = effStart;
}
}

static class Range{
BigInteger start;
BigInteger end;
Range(BigInteger start, BigInteger end){
this.start = start;
this.end = end;
}
}
``````

}

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! 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