CAPTAIN - Editorial

PROBLEM LINK:

Practice
Contest

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.

//