Can anyone share their approach to MAKETRI and also explain the same?
Especially how to get around the 10^18 limit
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…
6 Likes
I think I can write an editorial for this problem. Comment if you still need one, I will post it by tomorrow or latest day after tomorrow (its going to be a huge typing task XD)
Some of answers in another thread:
Sure bro. Please do share with us your approach.
Lol. I am glad dude you liked it. I am just making it shorter atm 
@vijju123 I didn’t see that you’v already written an editorial. Thanks man. Please do continue writing such detailed explanations. It really helps for beginners like me. Keep doing the good work…
Oh dear, you haven’t seen it yet! Don’t see it now. I am making it shorter. The editorial went a bit tooo long.