PROBLEM LINK:
DIFFICULTY:
Easy
PREREQUISITES:
basic knowledge of triangle inequality
intersection and union of ranges
PROBLEM:
You are given an array a of size n consisting of positive integers. You have to find number of integers x in the range [L, R], s.t. it is possible to create a non-degenerate triangle with sides x, a_i, a_j for some i, j, s.t. 1 \leq i, j \leq n, i \neq j.
QUICK EXPLANATION
You can define the set of valid values of side x for each pair a_i, a_j by an inclusive range. The problem then converts into finding union of these \binom{n}{2} ranges, which can be done in \mathcal{O}(n^2 \, logn) time.
After making an observation that the set of ranges defined by pairs (a_{j - 1}, a_{j}) completely contain the ranges defined by (a_i, a_j) for each i < j - 1 where the array a is sorted, this allows to consider only the n - 1 pairs (a_{i - 1}, a_i), and enables us to solve the problem in \mathcal{O}(n \, log n) time.
EXPLANATION:
Three positive numbers x, y, z can be the sides of a triangle if and only if they satisfy the triangle inequality. The triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side. In our case, the degenerate triangles are not allowed, so sum of lengths of any two sides must be strictly greater than the length of remaining side. With loss of generality, let us assume x \leq y \leq z, then x + y must be greater than z in order to form a triangle. You can check that this ensures that y + z > x and z + x > y.
We can iterate over each x in the range [L, R], and check whether there exists some a_i, a_j such that x, a_i, a_j form a triangle or not. It will take \mathcal{O}(|R - L + 1| \cdot n^2) time.
For a fixed a_i, a_j, we can find the possible values of x, s.t. x, a_i, a_j form a triangle. As we know that the number x must satisfy the following inequalities.
- x + a_i > a_j
- x + a_j > a_i
- a_i + a_j > x
Simplifying these inequalities we get
- x > a_j - a_i
- x > a_i - a_j
- x < a_i + a_j
In other words, x must be in the range (max(a_i - a_j, a_j - a_i), a_i + a_j) (exclusive range). You can also write this range as [max(a_i - a_j, a_j - a_i) + 1, a_i + a_j - 1] (inclusive range). Obviously this expression only makes sense if max(a_i - a_j, a_j - a_i) + 1 \leq a_i + a_j - 1, otherwise this won’t be a valid range.
Now, there can be total \binom{n}{2} such ranges (one for each a_i, a_j pair). We can find the total number of integral points in the range if we can find the union of these ranges. You can find union of N ranges in \mathcal{O}(N log N) time. Please see the following link for a detailed explanation about it. Now, as we know that the union of all ranges, we can take their intersection with range [L, R] to find the total number of valid values of x. Time complexity of this approach will be \mathcal{O}(n^2 \, log n).
One possible thing that might come to our mind is whether there are some ranges out of the \binom{n}{2} which lie entirely in some other range, because you can see that considering the smaller (the range which lies completely) range which is inside the other range is not going to affect the union of ranges.
Let us say there are three numbers a_1, a_2, a_3 s.t. a_1 \leq a_2 \leq a_3. Let R_{(i, j)} denote the range corresponding to (a_i, a_j) pair, i.e. R_{(1, 2)} = [a_2 - a_1 + 1, a_2 + a_1 - 1], R_{(1, 3)} = [a_3 - a_1 + 1, a_3 + a_1 - 1] and R_{(2, 3)} = [a_3 - a_2 + 1, a_3 + a_2 - 1]. The range R_{(2, 3)} contains the range R_{(1, 3)} completely inside it, as
a_3 - a_2 + 1 \leq a_3 - a_1 + 1 and a_3 + a_2 - 1 \geq a_3 + a_1 - 1.
Using the above observation, you can make the following claim. Let us sort the array a. The set of ranges defined by pairs (a_{j - 1}, a_{j}) completely contain the ranges defined by (a_i, a_j) for each i \leq j - 2.
Therefore we just have to take union of the ranges corresponding to n - 1 pairs of consecutive pairs (a_{i - 1}, a_i) after sorting the array a, which can be done in \mathcal{O}(n \, log n) time.
Taking intersection of these n - 1 range with range [L, R] can be done in \mathcal{O}(n) time.
Overall time complexity of the algorithm will be \mathcal{O}(n \, log n) which enables you to solve all the subtasks.
Time Complexity :
\mathcal{O}(n \, log n)