TKCONVEX - Editorial

Problem Link:

Practice

Contest

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

5 Likes

Why is it that Setter’s and Tester’s solution links are broken for every editorial?

1 Like

Yes it is frustrating, especially when I cite the solutions through my Editorial :-/
They will be uploaded ASAP (I believe codechef admins are waiting for all the setters to submit their codes for uploading).

2 Likes

Can you explain about the threshold being 60??. Any proof or ideas??

1 Like

Further explained in Explanation part. Look at the “F” sequence there. F grows atleast as fast as Fibonacci. Fib(50) > 10^9 => F(50+K) > 10^9 => F(60) > 10^9. [First implies is due to first K elements of F being 1, and not just first 2 in the case of Fib. Second implies is due to K <= 10].

I used the same daterministic approach but got WA.can you check my solution http://www.codechef.com/viewsolution/2241143

Nope, there’s a difference. You’re searching only for two sets of K-gons whose stick-lengths both appear consecutively. Consider the following case:
6 3
2 13 15 18 18 18

What do you think the output should be? What will your code output?

Hello…!!
Although i’ve used a substantially different approach here…
I couldn’t find any case that fails my


(http://www.codechef.com/viewsolution/2255744)
Would you please look into it.
If u want I can explain the idea in detail.

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 sticks[] is sorted, to test if sticks[z] can be the longest side of a polygon, we must have sum(sticks[z-k:z]) > 2*sticks[z]

Since sticks[] is sorted, in O(N) time we can iterate through the sticks and find the smallest z such that sticks[z] can be the longest side of a polygon.

Similarly we can find the largest z such that sticks[z] can be the longest side of a polygon.

lets call these small_z and large_z

if neither small_z and large_z exist, we are done the answer is No. If ‘large_z’ < 2*k, we are also done and the answer is No.

if large_z - k > small_z, we are done and can return the two polygons sticks[small_z - k:small_z] and sticks[large_z - k:large_z].

the final case is that (small_z - k) <= (large_z - k) < small_z <= (large_z)

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.

4 Likes

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 2*k length consecutive segments , and find if a subset of length k exists with the required property. With this approach , we have : O((n-k) * (2^k) *(k)).

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

try scanf and printf

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

Please upload the codes! Most of the participants have overlooked the xx112211…xx11xx22 test case. I guess it wasn’t there in the contest test file. So please upload the setter’s and tester’s codes.
Thanks