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

This can be solved in time O(N²). If necessary, sort the sizes increasingly.

Let the sides of a triangle be a = A[k], b = A[j], c = A[i], with a < b < c to ensure uniqueness. For a triangle to be possible, the constraint c < a + b must be verified. Then a triangle is classed as acute/right/obtuse based on the relation c² >< a² + b².

Let us choose c = A[i]. Then in the plane (a, b) (a horizontal), the constraints a < b < c define the domain of the possible triangles, itself a triangle (green in the picture), which is traversed by the circle of equation c² = a² + b².

Proceed as follows:

• start from b = c = A[j] = A[i] and loop

  • for a given value of b, find the largest a's that verify a + b < c (let a = A[k0]), a² + b² < c² (a = A[k1]) and a < b (a = A[k2] = A[j]). These correspond to intersections of an horizontal with the oblique sides and the circular arc.

  • get the next smaller b = A[j] and update the the three a's. (You are "cross-hatching" the two regions in the triangle.)

• until you reach b < c / 2.

The numbers of triangles of each type are given by the three sums of the numbers of solutions, i.e. respectively k1 - k0, 1 if equality is met, and k2 - k1.

The cost of the loop is linear, O(N), by monotonicity (when you decrease b, you increase/decrease the k's always in the same direction).

Repeating for all c = A[i], we get the claimed O(N²).

Answer 2

We can just start the search for the third stick where we left off, for a complexity of O(n²). Python (sorry; should be comprehensible though), now tested:

acute = 0
right = 0
obtuse = 0
a = sorted(a)  # copy and convert to a list
a.append(2 * a[-1])  # add a sentinel equal to twice the max
for i in range(len(a) - 3):  # exclude the sentinel
    if a[i] <= 0:
        continue
    ka = i + 2
    kr = i + 2
    ko = i + 2
    for j in range(i + 1, len(a) - 2):  # i < j, exclude the sentinel
        ka = max(ka, j + 1)
        while a[i] ** 2 + a[j] ** 2 > a[ka] ** 2:
            ka += 1
        acute += ka - (j + 1)
        kr = max(kr, ka)
        while a[i] ** 2 + a[j] ** 2 == a[kr] ** 2:
            kr += 1
        right += kr - ka
        ko = max(ko, kr)
        while a[i] + a[j] > a[ko]:
            ko += 1
        obtuse += ko - kr

Answer 3

Two things that will almost certainly improve things:

1. Make the squaring faster, use x * x rather than casting to double, and calling Pow.

2. Calculate the square once per i, once per j and once per k.

Things that may improve things, and may make them worse (profile):

1. Work on pre-sorted data.

2. Calculate the threshold for the final size (square-root of the other two squares) and just compare with that in the loop.

3. Have a different loop for when the two squares don't sum to a whole-number square (no value can match the right-angle case).

Answer 4

I do not see a method to reduce complexity at the moment but you can make some speedups about your code.

• calculate the squares of the A[i] upfront instead of calculating them over and over again
• if the lengths are sorted as in your example (if not sort them) you can exit the while loop as soon as the condition A[i] + A[j] > A[k] is violated the first time
• store the values for n - 1 and n -2 in variables instead of calculating them over and over again (may already be optimized by the compiler)
• do not calculate square(A[i]) + square(A[j]) twice, store the result in a variable.
• change order of checking-conditions. right angled triangles are the less likely. Always check the most common case first.
• using a * a is likely to be much faster for integer values than square(a)

Here you can see what I mean (you still have to implement the TODO parts)

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);
            // TODO: sort A[]  (if it is not already always sorted)
            // TODO: create an array of the square-valuee
            int[] Asquares = ....
            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 )
                    {
                        if(AiPlusAj <= A[k]){
                          break; 
                        }

                        int squareSum= Asquares[i] + Asquares[j];
                        else if (squareSum > Asquares[k])
                        {
                            acute++;
                        }
                        else if (squareSum < Asquares[k])
                        {
                            obtuse++;
                        }
                        else
                        {
                            right++;
                        }
                        k++;
                    }
                }
            }
            Console.WriteLine(acute + " " + right + " " + obtuse);
            Console.ReadLine();
        }
    }
}

Answer 5

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;
}

Answer 6

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.