Can you share your logic and solution for Chef and Triangles of February long contest 2017?
Firstly recall Triangle inequality sum of two sides exceeds third side.Note that if the sum of two sides equals third side then we get degenrate triangle which is not we want as we are interested in non-degenrate triangles only.
Now suppose a and b are two sides of triangles. Let c be third side. Now we have three inequalities
a+b>c
b+c>a => b-a>c
a+c>b => a-b>c
Combining above inequalities
Thus, we can say that abs(a-b) < c< a+b
Note that now we need not check all possible pairs of a,b from array. Rather we can just sort it and take adjacent elements. I leave this task for you to think why I am saying this 
So now just sort the array, take adjacent a,b pairs.
Now for every pair of a,b we know valid c is >abs(a-b) and <(a+b)
So get intervals of all possible a,b and then finally find the cardinality ( size of set) of union of intervals and intersection with interval [L,R].
This is your final answer.
My C++ solution for your refernce
https://www.codechef.com/viewsolution/12810949
Hope it helps
3 Likes
First sort the sequence.Complexity O(nlogn)
Then compute the pair(V1[i],V2[i]), where V1[I] represents difference between i’th and(i-1)'th number and V2[i] represent sum of i’th and (i+1)'th number.
Now take union of sets (V1[1],V2[1]) U (V1[2],V2[2]) U … U (V1[n],V2[n]).
Now take its intersection with [L,R].
My idea:
- Sort all the N strands in the increasing order.
- Store the pairs of the abs(differences) and the sum of each consecutive pairs in a vector.
Blockquote
Now, the idea is the any number, say c, will form a triangle if (abs(a-b))<c<(a+b). Where a and b are any two pairs stored in the vector(step 2). We have to find the number of such c’s in [L,R]. So, instead of finding the number of such c’s, we just take the range of values covered between [(abs(a-b)),(a+b)] and lying inside [L,R]. This is just another way of viewing the problem
- To implement the above point in a fast way, we just use the sweep line algorithm.
Can you explain the last part?
“So get intervals of all possible a,b and then finally find the cardinality ( size of set) of union of intervals and intersection with interval [L,R].”
Cause m getting a TLE (checking every value of l to r, kinda expected a TLE). I couldn’t get what you did in code so I would appreciate if you can explain
Firstly sort the array in O(nlogn)
Now no need to check all possible a and b rather we can just check adjacent a and b. So we will have (n-1) values of a,b so it is O(n).We can store this interval as [x,y] where x=abs(a-b)+1 and y=a+b-1
Now once we find set of intervals, we can find union of intervals.
Ex:
Lets say we have intervals [1,3] [2,4] [3,6] [8,10]
Union is [1,6],[8,10]
lets say given l,r is [4,20].
Thus intersection of union with given interval is:[4,6],[8,10]
Now find the cardinality of above interval which is 6.
Thus 6 is our required answer.
Overall complexity O(nlogn)
I get it. But one doubt, this also requires that we check for every value of l and r, right?
https://www.codechef.com/viewsolution/12926053
Please have a look at my code, its giving me a TLE and I cant find how to optimise it.
1 Like
No brother our intervals are continuous which is an asset for us as it gives us O(1) intersection of two contionous.
Recall of our JEE preparation days where we used to find sign schemes of functions in intervals and finding union,intersection of intervals.
So just give it a try. You can check my intersection function in my code. If you face any problem then let me know
Will you please explain this part," Note that now we need not check all possible pairs of a,b from array. Rather we can just sort it and take adjacent elements."
The significance of using only adjacent elements ?
@impratik_17 Well thats because if you take all possible pairs of a,b then unnecessarily you will increase the complexity to O(n^2) and therefore you will get timeout in sub task 3. So to get 100 you only need to consider adjacent pairs