Very divisible subsets

Question

I've recently come across the following problem.

We're given up to $10^4$ distinct positive integers $a_1,\dots , a_n$, each of them below $10^6$. Let's call a subset $S \subset \{a_1,\dots,a_n\}$ a very divisible subset if any number in this subset divides the product of other numbers in this subset.

The task is to find the largest such subset. It is guaranteed that there is at least one with at least $3$ elements. If there are several such subsets we can output any of them. For example if we're given numbers $2, 3, 4, 5, 7, 8, 9, 10$ then the algorithm might output $2, 4, 5, 8, 10$.

It's neither a homework nor an ongoing contest. I'm just curious how to solve it. Unfortunarely for now i can't see any solution better than brute force through all the subsets. And such approach is unfeasible under given limitations. Any ideas will be highly appreciated. Thanks in advance.

P.S. Here's an original statement of this problem: https://www.e-olymp.com/en/problems/7331

Answer 1

Here is an idea. By factoring the numbers, we are reduced to the following problem:

Given a set $S$ of vectors in $\mathbb{N}^k$, find a maximum-size subset $T \subseteq S$ such that for every $x \in T$ we have $x \leq \sum_{y \in T - x} y$ (pointwise).

If there is some $x \in S$ and some coordinate $i \in [k]$ such that $x_i > \sum_{y \in S - x} y_i$, then clearly $x_i$ cannot belong to any such set $T$, and we can simply remove it. Keep removing such elements from $S$ until no such elements exist. Then for every $x \in S$ and $i \in [k]$ it is the case that $x_i \leq \sum_{y \in S-x} y_i$, and so the filtered set $S$ is the unique solution.

Let me demonstrate this solution using your example $2,3,4,5,7,8,9,10$. Only 4 prime factors appear here (2,3,5,7), and converting $2^x3^y5^z7^w$ to the vector $xyzw$, we obtain the following vectors: $$ \begin{align*} 2 &= 1000 \\ 3 &= 0100 \\ 4 &= 2000 \\ 5 &= 0010 \\ 7 &= 0001 \\ 8 &= 3000 \\ 9 &= 0200 \\ 10 &= 1010 \end{align*} $$

We remove 7 due to the 4th coordinate. We then remove 9 due to the 2nd coordinate. We then remove 3 due to the 2nd coordinate. We cannot remove any more numbers, and so are left with the answer 2,4,5,8,10.

The challenge is to implement this greedy algorithm efficiently, which you can do by maintaining the sum of all elements left in the set, and using several priority queues (though perhaps there is a better solution). Details left to you.

Answer 2

The good news is: The greedy algorithm works. Start with T = S. Then as long as T has an element that doesn't divide the product of all other elements, remove it. I first had read the problem as "each number in T divides the product of two other numbers in T" - the greedy algorithm works in that case as well.

Just an addition to Juval's algorithm to keep the time polynomial in the problem size, for example if we are given just three 100 digit numbers:

If you had very large numbers, then the factoring could take excessive time. If you have n numbers, and n' of them have large factors that you can't find easily, then you can calculate about ($n'^2 / 2)$ gcd's and find which have common factors. If $a_i$ has a large unknown prime factor and no other $a_j$ has a common divisor then you can throw $a_i$ out without bothering to actually find the factor.