Problem Link:
Difficulty:
Medium-Hard
Pre-requisites:
Math, Randomized Algorithm
Problem:
You are given N sticks’ lengths. You need to find two sets of K sticks each, such that each set can form a K-sided convex polygon, or report that this is impossible.
Quick Explanation:
A set of stick lengths a1, …, aK can form a convex K-gon iff 2 * max(ai) < sum(ai). This is similar to triangle inequality, except being for K sides.
Given that sticks’ lengths <= 10^9, for large enough N, we can always find convex K-gon. This threshold is about 60 or less. Thus, given 70 or more sticks, we can remove some K consecutive set of sticks (when considered in sorted order) and from the remaining, we will still have atleast one more K-gon which we can find.
Thus, we only have to concentrate on N < 70 now.
Solution 1, Deterministic (Tester’s):
Let us sort the sticks according to their lengths. Then, without loss of generality, the two convex polygons will either consist of 2k consecutive sticks, or two sets of k consecutive sticks. Both the above cases can be described as “first picking one convex polygon from every k-subset of 2k consecutive sticks, and then finding the remaining convex polygon as a consecutive set of sticks among the remaining”. Thus we iterate over all 2k choose k subsets of all consecutive set of 2k sticks in our input, and check if assigning this set of k sticks into one convex polygon, allows us to find another convex polygon among the remaining.
Time Complexity: O(min(ThreshN * K * (2K choose K)), N * K), where ThreshN is about 70.
Solution 2, Randomized (Setter’s):
Let us suppose that we divide our sticks into two sets A and B, and we need to find a convex K-gon in each set. Wlog, the sides of the K-gon will be consecutive elements in sorted list A and B. Look through all K consecutive lengths in A and in B, and try to find if some set gives you a convex K-gon. Repeat this search a number of times (say: iter).
If there actually are two convex K-gons present in our set X, let us call the probability of finding them (by virtue of partitioning X into A and B) as P. Then, the probability of you not finding the two K-gons in the first iter iterations is (1-P)^iter. Setter chose iter as 2/P, which means the probability of not finding the sets, given that they are present, is about e^-2.
Explanation:
There were a lot of claims made in the Quick Explanation. We proceed to prove such claims.
2 * max(ai) < sum(ai) <=> K-gon exists
First take your sticks that satisfy the given condition. Then let ‘k’ be the longest stick. Fix it, also attach all the other sticks one after the other. You now have one stick of length ak, and a somewhat “bendable” stick of length sum(ai)-ak. Since ak < sum(ai)-ak, we can attach the “bendable” stick to our ak stick, and push out its ends so that it forms our convex K-gon. Now, if ak >= sum(ai)-ak, then no matter how we try, we will not be able to reach across the k’th stick with all the others.
For large enough N, we can always find a convex K-gon
Let us construct an increasing sequence, in which we say F[i] = minimum length of the i’th stick, such that there are no convex K-gons in the first i sticks.
We will have, F[1] = F[2] = … = F[K-1] = 1,
F[i] = F[i-1] + F[i-2] + … + F[i - K + 1].
The above follows from definition of F. All lengths >= 1, so first K-1 entries are 1. Then, given an i’th entry, it is >= maximum sum of (K-1) smaller values => F[i] >= given sum. But since we want F[i] to be the minimum such value, F[i] = F[i-1] + F[i-2] + … + F[i-K+1]. Thus, clearly, F grows atleast as fast as the Fibonacci sequence, which itself crosses 10^9 by the 50th value.
According to this, if we arrange our set of lengths in increasing order, and if L[i] < F[i] for some i >= K, then there will definitely be a convex K-gon in the first i elements. Put i = 50+k, and this gives us our threshold for the phrase “large enough N”.
The Union of the two convex polygons’ sticks will form a continuous sequence in the increasing order of stick-lengths (without loss of generality), or will form two disjoint k-sets.
We have now sorted our length array L. Let us suppose that we have a pair of feasible convex K-gons.
Let us define our “selection mask” as a sequence of x’s, 1’s, 2’s, where x means do not pick the stick, 1 means go into the first polygon, 2 means go into the second polygon. I prove that the selection mask will (without loss of generality), look either like
...xxxx11111...111xx...xx2222...222xxx...
or
…xxxx122121122121…22121xxx…
Case (1) The two feasible k-gons are not interleaved in the L array. Then, if there is a gap in one of them, I can move the lengths of that one up till there is no more gap. And since I am moving lengths UP the array, I will not violate my condition.
Case (2) The two feasibly k-gons are interleaved. Here, if there is a gap in the union of the two k-gons, then I can shift elements up the gap, keeping them in the same K-gon, and it will still not violate the given condition.
The above can be illustrated using the following selection-masks:
Case 1:
…xxxx11xx1xx111xxxx…xxx2222…222xxx…
can become
…xxxxxxxx111111xxxx…xxx2222…222xxx…
Case 2:
…xxxx12121xx12122xxx…
can become
…xxxxxx1212112122xxx…
Pseudocode, using bitmasks follows (note that in this implementation, I am taking O(2^2k) time, instead of O(2k choose k)):
for(bm = 0; bm < (1<<(2 * K-1)); bm++)
if(bitcount(bm) == K-1)
for(i = 2 * K-2; i < N; i++)
//convex polygon1 is defined by choosing positions "i-setbits(bm)"
ak = L[i+1]
sum = 0
for(j = 0; j < 2 * K-1; j++)
if(setbit(bm, j))
sum += L[i-j]
if(sum > ak) //feasible
used[i+1] = true
for(j = 0; j < 2 * K-1; j++)
if(setbit(bm, j))
used[i-j] = true
//find a convex k-gon in the remaining
for(i1 = 0; i1 < N; i1++) //potential starting point for 2nd polygon
if(!used[i1])
k = 1
sum = L[i1]
for(j = i1+1; j < N; j++)
if(!used[j])
k++
sum += L[j]
if(k == K)
ak = L[j]
break
if(sum > ak)
//second polygon found
output required answer
Randomized Analysis:
If there aren’t two convex K-gons, then no matter how you divide your set into two subsets, you will not be able to find two convex K-gons in them. And after all your iterations, you will return “NO” as required.
If there are two convex K-gons, lets call them C and D, then we want to divide our set of n sticks into A and B such that C is a subset of A, and D is a subset of B, or vice-versa. What is the probability P of doing this?
Let us look at one fixed set of our partition: A. Favourable cases are when A ∩ C = φ, A ∩ D = D; or when A ∩ C = C, A ∩ D = φ. Thus P = 2 / 2^(2k) = 2^-(2k-1).
Let us set iter = 2/P = twice the expected time to get find our solution. A simple Markov inequality analysis will give the probability of going wrong <= 1/2. More tightly, the probability of not finding these two convex K-gons in this time is (1-P)^iter ~ e^(-iter*P). For the setter’s choice of iter, this is about e^-2.
Overall Time Complexity: O(threshN * iter).
See Also: Complexity Class RP, of which this algorithm puts this problem in.
A Note on Testdata:
It seems that although it was a very interesting problem, the testdata did not capture all possible approaches. People who searched largely non-exhaustively for convex polygons were getting accepted in spite of there actually being such polygons. We were unable to think of all non exhaustive search approaches prior to the contest, which resulted in large number of people getting AC. For the Practice, the Setter and Tester would think up further boundary cases that would fail certain solutions, and update the problem with the same.
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here