10
$\begingroup$

This is a problem from the practice session of the Polish Collegiate Programming Contest 2012. Although I could find the solutions for the main contest, I can't seem to find the solution for this problem anywhere.

The problem is: Given a set of $N$ distinct positive integers not greater than $10^9$, find the size $m$ of the smallest subset that has no common divisor other than 1. $N$ is at most 500, and a solution can be assumed to exist.

I managed to show that $m \le 9$. My reasoning is: Suppose there exists a minimal subset $S$ of size $|S|=10$, with gcd = 1. Then all 9-subsets of $S$ must have gcd > 1. There are exactly 10 such subsets, and their gcds must be pairwise coprime. Let these gcds be $1 < g_1 < g_2 < ... < g_{10}$, where $\gcd(g_i,g_j)=1$, for $i \neq j$. Then the maximum number in $S$ is $g_2g_3...g_{10}$. But $g_2g_3...g_{10} \ge 3\times5\times7\times11\times...\times29=3234846615 > 10^9$, a contradiction.

However, even with this, a straightforward brute force is still too slow. Does anyone have any other ideas?

$\endgroup$
  • $\begingroup$ Whay can't $g_2 = 2$? $\endgroup$ – vonbrand Mar 7 '13 at 16:11
  • $\begingroup$ $g_2 > g_1 \ge 2$. $g_1$ cannot be 1, since 9-subsets cannot have a gcd of 1. $\endgroup$ – Wakaka Mar 14 '13 at 17:46
1
$\begingroup$

This problem is equivalent to the following, and it's trivial to construct reduction both ways.

Given a list of bit vectors, find the minimum number of them such that and all of them result the $0$ bit vector. $(*)$

Then we show set cover reduces to $(*)$. By set cover, I mean given a list of sets $S_1,\ldots,S_k$, find the minimum number of sets that covers their union.

We order the elements in the sets to be $a_1,\ldots,a_n$. Let $f(S) = (1-\chi_{a_1}(S),\ldots,1-\chi_{a_n}(S))$, where $\chi_x(S) = 1$ if $x\in S$, 0 otherwise. Note this function is a bijection so it has a inverse.

Now, if we solve $(*)$ on $f(S_1),\ldots,f(S_k)$, and the solutions is $\{ f(S_{b_1}),\ldots,f(S_{b_m})\}$, then $\{ f^{-1}(S_{b_1}),\ldots,f^{-1}(S_{b_m})\}$ is the solution to set cover.

Thus I would think this problem is testing one's ability to prune the search space.

$\endgroup$
  • $\begingroup$ How do you find the minimum vertex cover? $\endgroup$ – Yuval Filmus Mar 8 '13 at 18:48
  • $\begingroup$ oh nvm this solution, it's set cover instead. $\endgroup$ – Chao Xu Mar 8 '13 at 19:19
  • 1
    $\begingroup$ That is true, but I'm thinking maybe we can exploit certain properties of this special case. For instance, in this case the sets are all very huge, with sizes no less than $n-9$. In fact, if the numbers in the sets are all small, their sizes would be even bigger. Furthermore, we can definitely find 9 sets that cover everything. Anyway, how do you suggest I prune the search space? $\endgroup$ – Wakaka Mar 14 '13 at 17:37
  • $\begingroup$ I don't see how problem (*) is equivalent to the one given in the question. For one thing, the problem given in the question has the promise that all integers will be $\le 10^9$, which corresponds to a guarantee about the weights of the bit vectors that doesn't appear in problem (*). $\endgroup$ – D.W. Aug 24 '15 at 16:57
1
$\begingroup$

It's possible to solve this relatively efficiently by computing all pairwise gcd's, removing duplicates, and then recursing. It's the act of removing duplicates before you recurse that makes it efficient.

I'll explain the algorithm in more detail below, but first, it helps to define a binary operator $\otimes$. If $S,T$ are sets of positive integers, define

$$S \otimes T = \{\gcd(s,t) : s \in S, t \in T\}.$$

Note that $|S \otimes T| \le |S| \times |T|$ and $|S \otimes T| \le 10^9$ (in your problem); typically, $S \otimes T$ will be even smaller than either of those bounds suggest, which helps make the algorithm efficient. Also note that we can compute $S \otimes T$ with $|S| \times |T|$ gcd operations by simple enumeration.

With that notation, here is the algorithm. Let $S_1$ be the input set of numbers. Compute $S_2 = S_1 \otimes S_1$, then $S_3 = S_1 \otimes S_2$, then $S_4 = S_1 \otimes S_3$, and so on. Find the smallest $k$ such that $1 \in S_k$ but $1 \notin S_{k-1}$. Then you know that the size of the smallest such subset is $k$. If you also want to output a concrete example of such a subset, by keeping back-pointers you can easily reconstruct such a set.

This will be relatively efficient, as none of the intermediate sets grows in size above $10^9$ (in fact, their size will probably be much smaller than that), and the running time requires about $500 \times (|S_1| + |S_2| + \cdots)$ gcd operations.

Here is an optimization that might improve efficiency even further. Basically, you can use iterated doubling to find the smallest $k$ such that $1 \in S_k$. In particular, for each element $x \in S_i$, we keep track of the smallest subset of $S_1$ whose gcd is $x$ and whose size is $\le i$. (When you remove duplicates, you resolve ties in favor of the subset that is smaller.) Now, rather than computing the sequence of nine sets $S_1,S_2,S_3,S_4,\dots,S_9$, we instead compute the sequence of five sets $S_1,S_2,S_4,S_8,S_9$, by computing $S_2 = S_1 \otimes S_1$, then $S_4 = S_2 \otimes S_2$, then $S_8 = S_4 \otimes S_4$, then $S_9 = S_1 \times S_8$. As you go, find the first $k \in [1,2,4,8,9]$ such that $1 \in S_k$. Once you've found $k$ such that $1 \in S_k$, you can immediately stop: you can find the smallest subset whose gcd is $1$ by looking at the subset associated with $1$. So, you can stop as soon as you reach a set $S_k$ such that $1 \in S_k$, which allows you to stop early if you find a smaller subset.

This should be time-efficient and space-efficient. To save space, for each element $x \in S_k$, you don't need to store the entire set: it's enough to store two backpointers (so the two elements of $S_i,S_j$ that you took the gcd of, to get $x$) and optionally the size of the corresponding subset.

In principle, you can replace the sequence $[1,2,4,8,9]$ by any other addition chain. I don't know whether some other addition chain will be any better. The optimal choice might depend upon the distribution of correct answers and the expected sizes of the sets $S_k$, which is not clear to me, but can probably be derived empirically through experimentation.

Credits: My thanks to KWillets for the idea of storing a subset of numbers along with each element of $S_i$, which allows stopping early.

$\endgroup$
  • $\begingroup$ I believe binary search isn't necessary; you can store the element count with each gcd, and set it to the minimum pair sum during each doubling. $\endgroup$ – KWillets Aug 24 '15 at 22:08
  • $\begingroup$ Great point, @KWillets! Thank you for that beautiful idea! I've incorporated it into my answer. $\endgroup$ – D.W. Aug 25 '15 at 0:05
0
$\begingroup$

Perhaps it is faster looking at this in another way... the largest prime less than $\sqrt{10^9}$ is 31607, for a total count of 3401 primes between 2 and 31607, not a very large number. Write each of the numbers you are given fully factored over the primes up to 31607: $$ a_i = p_1^{n_{i 1}} p_2^{n_{i 2}} \ldots P_i $$ Here $P_i$ is 1 or a large prime. Then a set of the $a_i$'s is relatively prime if the corresponding $n_{i j}$ vectors are linearly independent (and their $P$s are different or both 1), and you are looking for the rank of a matrix.

$\endgroup$
  • $\begingroup$ What is the connection to linear independence? The vectors $(1,1)$ and $(1,0)$ are linearly independent, but the GCD is $(1,0)$ while we want $(0,0)$. $\endgroup$ – Yuval Filmus Mar 7 '13 at 17:31
  • 1
    $\begingroup$ Linear independence doesn't seem to work, but we can use this prime decomposition in a different way. For each prime $p$ (among $3401$ $p_i$'s and at most $500$ $P_i$'s), define set $A_p$ as the collection of all numbers (among the given set) which do not have $p$ as a factor. The problem now is to find a smallest subset $B$ of numbers such that for each $A_p$, $|A_p \cap B| \geq 1$. This is the hitting set problem, equivalent to set cover problem. This is $NP$-complete, but there might be some implementations fast enough for this size. $\endgroup$ – polkjh Mar 7 '13 at 18:41
  • $\begingroup$ Could you direct me to some implementations that could work? So far, I can only find approximation algorithms. Thanks! $\endgroup$ – Wakaka Mar 14 '13 at 17:49
  • $\begingroup$ This survey paper looks at both approximate and exact solutions. And when replying to a comment, please add @name-of-person to the comment. It will send a notification to that person. Otherwise they may never even know about your comment. $\endgroup$ – polkjh Mar 18 '13 at 3:53
-1
$\begingroup$

If you are able to find a subset with gcd(S) = 1, then I can always remove redundant elements from the subset till only 2 elements remain , which have gcd(S) = 1. Therefore, I can claim that either the smallest subset will contain 2 elements or it will not exist.

Now, we use recursion to solve this problem. Let's divide the array of numbers into 2 parts, one with n-1 elements and one with 1 element (last element). Either the 2 numbers will be in the first n-1 elements or one element will be there from 1st part paired with last element. Therefore, we are able to solve this problem in

T(n) = T(n-1) + O(n) time. which means T(n) = O(n^2).

$\endgroup$
  • 4
    $\begingroup$ $\gcd(6,10,15)=1$. Which element can you remove? $\endgroup$ – Rick Decker Aug 24 '15 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.