Lightoj 1307 - Counting Triangles

Problem link:

Problem Analysis: 

for any triangle with edges a, b, c we know that 

(1)   a + b > c

(2)   b + c > a

(3)   c + a > c

for being a valid triangle it must follow all these . we can use a brute force algorithm O(n^3) with 3 nested loops and checking the validity of those selected edges of those but it's too big so we will try to make this better.  So first we sort the array of lengths for simplicity.

 Than for each 'e1' we select another edge after that and thats 'e2' and we know we sorted the aray so e1<=e2. After that we search the maximum element 'e3' that follows all three of those triangle validity formula we wrote above.

 we already know that e1+e3 > e2 and e2 + e3 > e1 as they are sorted and e1<= e2 < e3 so we just need to find the maximum edge length for which e1+e2>e3. and than we also know that all the edges between e2 and e3 also makes valid triangles.  because they also follow all the three rules.

So we just search index  of (e1+e2-1)  using binary search.

here we searched for (e1+e2-1) we used -1 because e1+e2 , e1, e2 these three can not actually make a valid triangle. After finding the upper bound of e3 (e1+e2-1) we just add the difference of the index of e2 and e3 and repeat it for the next e1, e2' .  so our algorithm now becomes
O(N^2 + Nlog(N)) = O(N^2) that easily passes. 

for better visualization go here  

Here goes the code: 

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main(){
4.     int ts;
5.     scanf("%d", &ts);
6.     for(int p = 1; p <= ts; p++){
7.     int n;
8.     scanf("%d", &n);
9.     vector<int>v;
10.     for(int i = 0; i <n; i++){
11.         int a;
12.         scanf("%d", &a);
13.         v.push_back(a);
14.     }
15.     sort(v.begin(), v.end());
16.     long long unsigned sum = 0;
17.     for(int i = 0; i <n-2; i++){
18.         for(int j = i+1; j<n-1; j++){
19.             sum+= upper_bound(v.begin(), v.end(),v[i]+v[j]-1)-v.begin()-j-1;
20.         }
21.     }
22.     printf("Case %d: %llu\n",p,  sum);
23.     }
24.     return 0;
25. }