Problem Link:Difficulty:MediumHard Prerequisites: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 Ksided convex polygon, or report that this is impossible. Quick Explanation:A set of stick lengths a_{1}, ..., a_{K} can form a convex Kgon iff 2 * max(a_{i}) < sum(a_{i}). 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 Kgon. 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 Kgon 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 ksubset 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 Kgon in each set. Wlog, the sides of the Kgon 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 Kgon. Repeat this search a number of times (say: iter). If there actually are two convex Kgons 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 Kgons in the first iter iterations is (1P)^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(a_{i}) < sum(a_{i}) <=> Kgon existsFirst 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 a_{k}, and a somewhat "bendable" stick of length sum(a_{i})a_{k}. Since a_{k} < sum(a_{i})a_{k}, we can attach the "bendable" stick to our a_{k} stick, and push out its ends so that it forms our convex Kgon. Now, if a_{k} >= sum(a_{i})a_{k}, 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 KgonLet us construct an increasing sequence, in which we say F[i] = minimum length of the i'th stick, such that there are no convex Kgons in the first i sticks. We will have, F[1] = F[2] = ... = F[K1] = 1, The above follows from definition of F. All lengths >= 1, so first K1 entries are 1. Then, given an i'th entry, it is >= maximum sum of (K1) smaller values => F[i] >= given sum. But since we want F[i] to be the minimum such value, F[i] = F[i1] + F[i2] + ... + F[iK+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 Kgon 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 sticklengths (without loss of generality), or will form two disjoint ksets.We have now sorted our length array L. Let us suppose that we have a pair of feasible convex Kgons. 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
or Case (1) The two feasible kgons 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 kgons are interleaved. Here, if there is a gap in the union of the two kgons, then I can shift elements up the gap, keeping them in the same Kgon, and it will still not violate the given condition. The above can be illustrated using the following selectionmasks: Case 2: Pseudocode, using bitmasks follows (note that in this implementation, I am taking O(2^2k) time, instead of O(2k choose k)):
Randomized Analysis:If there aren't two convex Kgons, then no matter how you divide your set into two subsets, you will not be able to find two convex Kgons in them. And after all your iterations, you will return "NO" as required. If there are two convex Kgons, 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 viceversa. 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^(2k1). 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 Kgons in this time is (1P)^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 nonexhaustively 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
This question is marked "community wiki".
asked 18 Jun '13, 23:31

I had a pretty simple solution to this one that I'm sure is correct: http://www.codechef.com/viewsolution/2273459 Intuition:
If the int array Since Similarly we can find the lets call these if neither if the final case is that In that case we simply consider the 2k sticks new_sticks[] = sticks[large_z  2k:large_z] note that we can't include any sticks bigger than large_z. Also we need not include any sticks smaller than large_z  2k since we could always replace them with one of the 2k large sticks. Now that we have 2k sticks, we simply try all possible ways of dividing the 2k sticks into two groups of size k until one both groups form polygons. Otherwise we return No. In the worse case there will be 20 choose 10 groups to consider which is 184756 groups. Checking each group requires less than 20 operations, so Even with python we can comfortably fit within the time limit while enjoying use of pythons itertools.combinations(new_sticks, r=k) method to iterate over the groups while maintaining sorted order. answered 19 Jun '13, 08:17

I have a simple solution which doesn't need that n <= 70 analysis and has ~10^6 iterations even in the worst case. I used meet in the middle approach over every 2k length consecutive segments , and find if a subset of length k exists with the required property. With this approach , we have : O((nk) * (2^k) (k)). answered 19 Jun '13, 11:14

I attempted using a simple approach and I couldn't find a test case that fails my solution. The code was judged TLE despite the complexity being O(n^2) for n<70 otherwise O(nlogn). Please tell me where I'm going wrong. http://www.codechef.com/viewsolution/2265976 answered 20 Jun '13, 10:30

I used the same daterministic approach but got WA.can you check my solution http://www.codechef.com/viewsolution/2241143 answered 19 Jun '13, 00:33
Nope, there's a difference. You're searching only for two sets of Kgons whose sticklengths both appear consecutively. Consider the following case: What do you think the output should be? What will your code output?
(19 Jun '13, 01:13)

Please note that the Setter's Solution is incomplete.
What test cases were added for the rejudging? Was the test case mentioned in the comments added? There are solutions that fail the given test case and were still judged correct after the rejudging. 6 3 1 5 6 6 8 9