Here is the problem statement
http://www.spoj.com/problems/NOTATRI/
A triangle can be formed (including degenerate triangles) if sum of 2 sides is always biger or equal to the 3rd side. So , we will take pairs and for every pair we will find the number of the other sticks which are greater than the sum of our pair. For doing that fast the first thing is sorting. We need to sort our array . Then after that we need to consider every pair, for every pair find the leftmost element which is greater than the sum of that pair. Suppose that is the element with index I. So if our array is sorted and I is greater than the sum of our current pait, we can say for sure that the elements I+1,I+2,....N are also greater than the sum of our pair. To avoid TLE we will find that element with teh help of binary search,
http://www.spoj.com/problems/NOTATRI/
A triangle can be formed (including degenerate triangles) if sum of 2 sides is always biger or equal to the 3rd side. So , we will take pairs and for every pair we will find the number of the other sticks which are greater than the sum of our pair. For doing that fast the first thing is sorting. We need to sort our array . Then after that we need to consider every pair, for every pair find the leftmost element which is greater than the sum of that pair. Suppose that is the element with index I. So if our array is sorted and I is greater than the sum of our current pait, we can say for sure that the elements I+1,I+2,....N are also greater than the sum of our pair. To avoid TLE we will find that element with teh help of binary search,
No comments:
Post a Comment