2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Product of two other numbers, or any number of other numbers? $\endgroup$ – gnasher729 Mar 1 '17 at 0:04
  • $\begingroup$ @gnasher729 "of other numbers in this subset". In provided example $8$ divides the product of $2, 4, 5, 10$; $~~10$ divides the product of $2, 4, 5, 8$ and so on. $\endgroup$ – Igor Mar 1 '17 at 1:53
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for such a good explanation. I was working around it for the last couple of days but still can't see a good way to implement it. At least my implementations didn't work well. How do you think to use priority queues? $\endgroup$ – Igor Mar 3 '17 at 16:45
  • $\begingroup$ I'v tried to keep for each prime number a list of a_i which it divides and then to traverse this lists one by one excluding the numbers. But the problem with this implementation is that deleting number from a list for one of its prime divisors may affect all the numbers in lists for other its prime divisors. And so we need to look for this lists again and again $\endgroup$ – Igor Mar 3 '17 at 16:48
  • $\begingroup$ The priority queues will tell you, for each prime $p$, the highest power of $p$ that divides a surviving number. Together with the prime factorization of all surviving numbers, this should be enough to implement the greedy algorithm efficiently. $\endgroup$ – Yuval Filmus Mar 3 '17 at 21:05
1
$\begingroup$

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.

$\endgroup$

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.