Connection Status:
Competition Arena > NonSimilarTriangles

NonSimilarTriangles

2020 Humbleool Cup Prelims · 2020-02-26 · by misof

2020 Humbleool Cup Prelims · 2020-02-26 · by misof · Brute Force, Simple Math, Simple Search, Iteration, Sorting
Class Name: NonSimilarTriangles
Return Type: int
Method Name: count
Arg Types: (vector<int>)
Problem Statement

Problem Statement

You have a collection of straight sticks. The lengths of these sticks are given in the int[] L. You are going to use three of these sticks to form a triangle.

Two triangles are called similar if one of them can be translated, rotated, mirrored, and/or uniformly scaled (in any order) to produce the other one. For example, any triangle with sides 30, 40, and 50 is similar to any triangle with sides 500, 300, and 400, and also to any triangle with sides 33, 55, and 44.

Consider all possible triangles that can be formed using three of your sticks. Suppose we divide these triangles into groups, each group being a collection of triangles that are similar to each other. How many groups will there be? In other words, how many different (i.e., non-similar) triangles can be constructed using three of your sticks? Compute and return this number.

Notes

  • A valid triangle must have a positive area. (See Example 5.)

Constraints

  • L will have between 3 and 150 elements, inclusive.
  • Each element of L will be between 1 and 10^6, inclusive.
Examples
0)
{3,4,5}
Returns: 1

We can build exactly one triangle.

1)
{1,1,1,1,1,1}
Returns: 1

Regardless of which three sticks we choose, we will get the same triangle: an equilateral triangle with side length 1.

2)
{2,2,2,3,3,3}
Returns: 3

There are three different triangles we can build: an equilateral triangle (with side 2 or side 3, those are similar to each other), a triangle with sides 2,2,3, or a triangle with sides 2,3,3.

3)
{1,2,4,8,16,24}
Returns: 0

We cannot build any triangles at all: regardless of which three sticks you pick, you won't be able to build a valid triangle.

4)
{10,3,10,4,10,5,10,6,10,7,10,8,10,9}
Returns: 50
5)
{5, 5, 10}
Returns: 0

These three sticks do not form a valid triangle. A valid triangle must have a positive area.

Submissions are judged against all 99 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class NonSimilarTriangles with a public method int count(vector<int> L) · 99 test cases · 2 s / 256 MB per case

Submitting as anonymous