Optimizaion(Reduce Complexity). Count Acute, Right and Obtuse triangles from n side lengths

Question

Edit 1: Changed 104 to 10^4 in constraints. Sorry for the mistake.

Problem Statement: We have N sticks. The size of the ith stick is Ai. 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 ith number denotes Ai.

Constraints:

For full score: 3≤N≤5000
For 40% score: 3≤N≤500

For all testcases:

1≤A[i]≤10^4
A[i]<A[i+1] where 1≤i<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.

My Code: I have used C# as the language. I hope to get a solution in the same.

using System;

namespace CodeStorm
{
    class CountingTriangles
    {
        public static double square(int x)
        {
            return Math.Pow(x, 2);
        }

        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string[] A_temp = Console.ReadLine().Split(' ');
            int[] A = Array.ConvertAll(A_temp, Int32.Parse);

            int acute = 0, right = 0, obtuse = 0;
            for (int i = 0; i < n - 2; i++) 
            {
                for (int j = i + 1; j < n - 1; j++) 
                {
                    int k = j + 1;
                    while (k < n && A[i] + A[j] > A[k])
                    {
                        if (square(A[i]) + square(A[j]) == square(A[k]))
                        {
                            right++;
                        }
                        else if (square(A[i]) + square(A[j]) > square(A[k]))
                        {
                            acute++;
                        }
                        else
                        {
                            obtuse++;
                        }
                        k++;
                    }
                }
            }
            Console.WriteLine(acute + " " + right + " " + obtuse);
            Console.ReadLine();
        }
    }
}

https://ideone.com/zbQXE9

The above code runs perfectly and find 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.

Answer 1

You can improve the approach in the following manner: first sort all the sticks by their length. After that iterate over each pair of sticks(i.e. double cycle with square complexity). For each pair perform a binary search to find the location in the array of sticks where you switch from acute to right angled triangles(considering the two sticks you've preselected and the third one as base). Then perform another binary to find the location where you switch form right to obtuse triangles. After that you will have to perform yet another binary search to find the position where the third stick is so long that you can not form a valid triangle with it. You will have to handle one more case - if there are no right angle triangles and you switch from acute directly to obtuse(this can be done by adding a single if).

It is important to note that the type of triangle is determined by the angle opposite to the biggest side of the triangle, thus in the above algorithm you should only consider side lengths bigger than the two preselected sticks(which can be done using another binary).

Overall the approach I propose has complexity O(N² * log(N)) which is asymptotically better than your algorithm.

Answer 2

Just a small hint: Math.Pow() is rather slow for computing squares. You should modify your method square:

public static double square(int x)
{
    return x * x;
}