# Count Acute, Right and Obtuse triangles from n side lengths

Problem Statement: We have $N$ sticks. The size of the $i$th stick is $A_i$. We want to know the number of different types of triangles created with each side from a single different stick. Calculate the number of acute triangles, right triangles and obtuse triangles.

Input Format: The first line contains $N$. The second line contains $N$ integers. The $i$th number denotes $A_i$.

Constraints:

• For full score: $3 \le N \le 5000$
• For 40% score: $3 \le N \le 500$

For all test cases:

• $1 \le A[i] \le 10^4$
• $A[i] \lt A[i+1]$ where $1 \le i \lt N$

Output Format: Print 3 integers: the number of acute triangles, right triangles and obtuse triangles, respectively.

My Solution: My code runs in the given time for small $n$ (~500). It will work for large $n$ (~5000) but I get time limit exceeded error on the Online Judge.

using System;

namespace CodeStorm
{
class Triangles
{
static void Main(string[] args)
{
int[] A = Array.ConvertAll(A_temp, Int32.Parse);
int[] A_sq = new int[n];

for (int i = 0; i < n; i++)
{
A_sq[i] = A[i] * A[i];
}

int n_m_2 = n - 2;
int n_m_1 = n - 1;

int acute = 0, right = 0, obtuse = 0;
for (int i = 0; i < n_m_2; i++)
{
for (int j = i + 1; j < n_m_1; j++)
{
int k = j + 1;
int AiPlusAj = A[i] + A[j];

while (k < n)
{
int squareSum = A_sq[i] + A_sq[j];
if (AiPlusAj <= A[k])
{
break;
}
else if (squareSum > A_sq[k])
{
acute++;
}
else if (squareSum < A_sq[k])
{
obtuse++;
}
else
{
right++;
}
k++;
}
}
}
Console.WriteLine(acute + " " + right + " " + obtuse);
}
}
}


The above code runs perfectly and finds the possible triangles.

Input:

6
2 3 9 10 12 15


Output:

2 1 4


The possible triangles are:

Acute triangles: 10−12−15, 9−10−12

Right triangle: 9−12−15

Obtuse triangles: 2−9−10, 3−9−10, 3−10−12, 9−10−15

I want to know a more efficient way to approach the problem so that I can get it executed in the given time limit for $n$ (~5000). After I tried to find the complexity, I came up with $O(n^3)$. I am not good with complexities. I might be wrong. I would like a more efficient way for the problem.

Sort your sticks by length; square them when already sorted. Then replace the innermost loop with 3 binary searches. In pseudocode,

        max_obtuse = upper_bound(A[j:n], A[i] + A[j])
max_right = upper_bound(A_sq[j:n], A_sq[i] + A_sq[j])
max_acute = lower_bound(A_sq[j:n], A_sq[i] + A_sq[j])

obtuse += max_obtuse - max_right
right += max_right - max_acute
acute += max_acute - j


That reduces the execution time from $O(n^3)$ to $O(n^2\log n)$.

EDIT:

In the sorted array below, values marked as - are strictly less, and values marked as + are strictly greater, than X:

    -----XXXXXXXXXXXXXXXXX++++++++++
^                ^
|                This is upper bound of X
This is lower bound of X

• Sir I am new to algorithm. I didn't understand the pseudo code. What do you mean by upper bound and lower bound binary searches. I am sorry if I sound weird. But I am not able to understand the code. – Aman Ahuja Oct 30 '15 at 17:29
• @AmanAhuja See edit. – vnp Oct 30 '15 at 19:45
• First of all thank you so much. That helped me a lot. It improved my code. The code was submitted for a problem on hackerearth. Earlier I cleared 8 out of 16 cases(due to TLE). With your help I could do another 4. The 4 remaining cases are still showing a TLE error. Is there any way to reduce the execution time further. I am using C#. Is it a problem with the language. The execution time has to be within 3s. Thank you anyways. – Aman Ahuja Oct 31 '15 at 13:14