SPOONS - Editorial

editorial
, , , ,
1

Problem Link:

Practice

Contest

Difficulty:

easy-medium

Pre-requisites:

Sperner’s Theorem

Problem:

Given an integer N, find the size of smallest set S such that there exists an antichain of size N among the subsets of S.

Explanation:

The relation between groups of cities A and B served by two spoons can be equivalently stated as: A-B is not empty and B-A is not empty, which is same as A ⊄ B and B ⊄ A.

If we consider the poset of all subsets of a set S, then the two elements A and B above are incomparable, therefore all the N sub-sets form
an antichain.

People could obtain the solution by

The statement and proof of Sperner’s Theorem is given below in very simple language.

Given the Sperner’s Theorem, we would still need to find smallest M such that M choose ⌊ M/2 ⌋ is at least N. For N ≤ 1018, M ≤ 64, and therefore, one could compute these values offline(or online in his code itself), and do a binary search to lookup the best value. Time complexity O(T).

Proof of Sperner’s Theorem

Given a set S of size M, you want to pick a family F of subsets of S (i.e. F ⊂ 2S) such that no set in the family is subset of another set in the family (i.e. x, y ∈ F ⇒ x ⊄ y). The maximum possible size of such a family of subsets is M choose ⌊ M/2 ⌋

It is clear that if we choose all subsets in the family F to be of same size, k, then the family would satisfy the above property, and its size will be M choose k. This is maximum when k=⌊ M/2 ⌋. Therefore, the bound suggested above can be attained by picking all sbsets of size ⌊ M/2 ⌋. Now it remains to show that this is also the best possible bound.

Lets say we have got a family F of subsets satisfying above property, and it has a1 subsets of size 1, a2 subsets of size 2 … aM subsets of size M.

Then we can generate a permutation of S by selecting a set S’ in F and concatenating a permutation of the elements of S’ with a permutation of the non-members. If |S’| = i, it will be associated in this way with i!(n − i)! permutations. Each permutation can only be associated with at most one set in F. This is because otherwise two different prefixes of a single permutation would be associated with different subsets(say S1 and S2) in F, in which case, one(out of S1 and S2) would be a subset of the other. Therefore, the number of permutations that can be generated by this procedure is

sum [i=1 to M] ai * i! (M-i)!

And the above number is no more than M!. For k=⌊ M/2 ⌋ we already have

sum [i=1 to M] ai * k! (M-k)! ≤ sum [i=1 to M] ai * i! (M-i)! ≤ M!

⇒ sum [i=1 to M] ai ≤ M!/ (k! * (M-k)!)

Setter’s Solution:

Can be found here

Tester’s Solution:

  1. Mahbub’s

(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester1/SPOONS.cpp)  
 2. Sergey's

(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester2/SPOONS.cpp)

Editorialist’s Solution:

Can be found here, and code used to generate values offline is here

5 Likes
2

I uses the fact that for any object of n type, nCn/2 is the maximum value in which we can group them such that no two group is common.

1 Like
3

same here :wink:

4

Aye !
But you dont know that unless you have a mathematical proof.
Sperner’s Theorem is the mathematical proof.

5

We know that Comb(n, n/2) is the biggest from Comb(n, i) where 0 <= i and i <= n.

2 Likes
6

@betlista I think what @utkarsh_lath meant to say is we don’t know there are a total of nCr different subsets available (all of the same size r) such that none of them is contained in the other (which is technically termed as Sperner family). Once we figur this out, the solution is just in maximizing the value of nCr, which happens at r = n/2

By the way, we figured out the solution, without knowing there even existed a theorem for this. Thats all! :wink:

1 Like
7

If we have n countries. If a spoon caters to more than n/2 countries then we could take away some countries to get n/2 countries. So any spoon with more than n/2 countries would prevent other combinations that require only n/2 countries. Also adding extra countries wouldn’t distinguish between other spoons since any spoon with n/2 countries must have different countries to any other spoon with n/2 countries provided it’s not the same n/2 countries. (the explanation isn’t quite sound reasoning but basically the answer is nCn/2)

Here is my 3 line solution in python:

from math import factorial; from sys import stdin; from bisect import bisect_left
cache = [(factorial(cities)/(factorial(cities - cities//2))/factorial(cities//2), str(cities)) for cities in range(1, 65)]
print "\n".join(cache[bisect_left(cache, (n,0))][1] for n in map(int, stdin.read().splitlines())[1:])
8

Yes Tijoforyou that’s a good way of reasoning. That’s how I figured it out too although I did n = 1…6 by hand to confirm.

1 Like
9

Yes! The standard method of pencil and paper works well for smaller values, and that usually helps in confirming/figuring-out solutions!!

Worked for me here too!! :smiley:

10

For which test case it fails, can someone please tell me…
http://www.codechef.com/viewsolution/2660085

11

Looks like

		for(j=1; j<=(i+1)/2; j++) {
			temp1 *= num;
			temp2 *=den;
			num--;
			den++;
		}

		//(and the other for loop as well)

has some serious overflow problems. Do you realize i canbe as big as size (70) and j can hence be as big as about 35?

You are trying to compute (i+1)/2 factorial in temp2. Now even 21! will not fit in a 64-bit integer. So, you have overflow issues, in your precomputation part.

1 Like
12

Why it is that all subsets in the family F has to be of same size k?

13

So there was a theorem for this. Interesting. I tried to understand it, but since I have already solved the problem, nothing seems to be going through my head on this topic anymore :p.

14

It is not needed for all cases, just the worst cases, for example for N = 4, you can have 4 spoons connected to cities as {A, B}, {A, C}, {B, C} and {D}.

15

Probably I do not understand what you want…

It is clear that if we choose all subsets in the family F to be of same size, k, then the family would satisfy the above property, and its size will be M choose k

(from editorial)

16

I was not clear. What I am asking is just that is there a mathematical proof to show that for the worst case, all subsets in the family F has to be of same size k.

17

From my point of view it’s clear - we are looking for combinations. We know, for example from Pascal’s triangle, that Comb(n, i) is the biggest for Comb(n, n/2). Now, the question is: “Is that the max possible value?”, in other words: “Can we add set with less than n/2 elements or with more than n/2 element?”. Also this is clear to me. No, we cannot, because while we have all combinations of n/2 elements, each subset with size n/2-1 is contained in one of those. Same applies for bigger set, while we have all combinations for n/2, set with n/2+1 elements have to contain one of those…

18

thanks a lot

19

I thought that it might be nCn/2, and I actually opened OEIS and entered the first few numbers to confirm this. I seem to be the only person who did that, although they’ve mentioned it here :smiley:

20

what property of combinations did problem setter used in his program?

long long int C[100];
// Precomputing (N)C(N/2)
void precompute()
{
C[0] = 1;
C[1] = 0;
C[2] = 1;
long long int prev = 1;
for(long long int i=3;i<=64;i++)
{
C[i]=C[i-1];
if(i%2==1)
{
C[i]/=prev;
C[i]=i;
}
else
{
C[i]=2;
prev = i/2 + 1;
}
}
}