3
\$\begingroup\$

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 n = int.Parse(Console.ReadLine());
            string[] A_temp = Console.ReadLine().Split(' ');
            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);
            Console.ReadLine();
        }
    }
}

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.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Aman Ahuja Oct 30 '15 at 17:29
  • \$\begingroup\$ @AmanAhuja See edit. \$\endgroup\$ – vnp Oct 30 '15 at 19:45
  • \$\begingroup\$ 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. \$\endgroup\$ – Aman Ahuja Oct 31 '15 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.