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:])
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
Why minimum number of cities required is not equal to the number of spoons required. Because in every set of cities a spoon server, there should be atleast one city which should be unique. So if every city has at least one unique city, then number of cities will be equal to number of spoons…
Please correct me where I am wrong on this track of thoughts…
@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!
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.
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.
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}.
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
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.
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…
Try to answer for yourself, what is the answer for input 5 = you want to place 5 spoons, how many cities do you need for this? You say 5, but you are looking for minimal number of cities and we can achieve this with 4 cities
