NULL's blog

By NULL, history, 13 months ago, In English

Given a set of distinct positive integers, let's say that it can "construct a triangle" if it can be partitioned into three subsets whose sums can be the lengths of the three sides of a triangle (that is: three subsets whose sums satisfy the triangle inequality). For example, { 1, 2, 3, 4 } can "construct a triangle" by partitioning it into { { 1, 2 }, 3, 4 }, because a triangle can have side-lengths 1+2, 3, and 4 (because 1+2 + 3 > 4, 1+2 + 4 > 3, and 3 + 4 > 1+2).

I'm given an array A of up to 105 distinct nonnegative integers in the range [0, 109] and an integer k, and I need to find how many contiguous subarrays of length k can construct triangles.
For example, if A = [1, 3, 4, 2, 5, 9] and k = 3, then there are two such subarrays: [3, 4, 2] and [4, 2, 5].

I've tried the following approach:

Iterate over A, examining each contiguous subarray of length k. For each such subarray, find every partition of it into three subsets. For each such partition, calculate the sums of the three subsets, and check whether they satisfy the triangle inequality.
Return the number of subarrays where the check passed for at least one partition.

This gives the right answer, but it takes O(3kn) time, where n is the length of A.

I've read about an O(n) algorithm for this problem, but I don't understand why it works:

Iterate over A, examining each contiguous subarray of length k. For each such subarray, determine its sum S and its greatest element aG, then check if S > 2aG.
Note #1: The subarray can construct a triangle if and only if this is the case.(explain at (1))
Note #2: the sums of all subarrays can be determined in O(n) time by using prefix sums.
Note #3: the greatest elements of all subarrays can be determined in O(n) time by using a deque.
Return the number of subarrays where the check passed for at least one partition.

(1)I was given this explanation for Note #1:

Let i be the first index of the subarray, and j be its last index (such that j = i + k − 1). Imagine that we've sorted the elements of the subarray, so that Ai < Ai+1 < … < Aj.
Imagine partitioning the subarray as follows:
x = Ai + Ai+2 + … + Aj−2
y = Ai+1 + Ai+3 + … + Aj−1
z = Aj
It can be easily proved that y + z > x and x + z > y; so to check if it satisfies the triangle inequality, all that remains is to check if x + y > z, which is equivalent to checking if x + y + z > 2z. But we can check this without actually sorting: x + y + z is the sum of the entire subarray, and z is its greatest element.

What I don't understand is — this explanation shows that if we partition the subarray in a specific way, then that partition satisfies the triangle equality if and only if x + y + z > 2z. But what if we partition the subarray in a different way? Even if this partition doesn't satisfy the triangle inequality, can't there be a different one that does?

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

let z= max{A[i]..A[j]}. If z<1/2*(A[i]+..+A[j]) so you can create a triangle following the above proof.

Otherwise if z> 1/2*(A[i]+...+A[j]). Consider any partition of K elements into 3 sets A,B, C; and z in C. Let a,b,c be the sum of elements in A, B, C. so a+b<c since z in C => we cannot create any triangle.