PROBLEM LINK:
Author: Varun Singh
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Geometry, Greedy, Sorting
PROBLEM:
Given n line segments calculate whether one can form a non-degenerate triangle using exactly 3 segments.
EXPLANATION:
Let x, y and z be the lengths of 3 segments such that x ≤ y ≤ z, If they can’t form a non-degenerate triangle, segments of lengths x - 1, y and z or x, y and z + 1 can’t form a non-degenerate triangle, So we don’t need to try all the combinations, If we try y as the middle one, We need to try the maximum x that is less than or equal to y and the minimum z that is greater than or equal to y, The easiest way to do so is to sort the segments and try every consecutive 3.
Time complexity: O(nlog(n)).
ALTERNATIVE SOLUTION:
Depending on the note from the first solution, If we try to generate a sequence such that after sorting, Every consecutive 3 segments will form a degenerate triangle, It will be 1 1 2 3 5 8 13 … which is Fibonacci sequence, Fibonacci is a fast growing sequence, fib(45) = 1134903170, Notice that Fibonacci makes maximum n with “NO” as the answer, That means the answer is indeed “YES” for n ≥ 45, For n < 45, You can do the naive O(n^3) solution or the first solution.
Let x be the number that satisfies these inequalities.
fib(x) ≤ maxAi
fib(x + 1) > maxAi
Time complexity: O(x^3) or O(xlog(x))
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.