NUMSET - Editorial

PROBLEM LINK:

Contest
Practice

Author: Sergey Kulik
Testers: Vasya Antoniuk and Kevin Atienza
Translators: Vasya Antoniuk (Russian), Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

DIFFICULTY:

Easy-medium

PREREQUISITES:

Dynamic programming, prime factorization

PROBLEM:

Given a list of positive integers, find the size of the largest pairwise-coprime sublist.

QUICK EXPLANATION:

Let’s call a prime number small if p \le \sqrt{1000}, i.e., p \le 31. There are 11 such primes, so a set of small primes can be represented by a bit set of 11 bits.

Let S(k) be the set of small prime factors of k.

Sort the list a_1, \ldots, a_n by their largest prime factor. Then, if S is a set of small primes, define the function F(i,S) as the size of largest pairwise-coprime sublist of a_1, \ldots, a_i such that are also pairwise-coprime with S. Then the answer we’re looking for must be F(n,\emptyset). F(i,S) can be computed with the following recurrence:

F(i,S) = \begin{cases} F(i-1,S) & \text{if $S \cap S(a_i) \not= \emptyset$} \\ \max(F(i-1,S), 1 + F(p_i, S \cup S(a_i))) & \text{if $S \cap S(a_i) = \emptyset$} \end{cases}

where p_i is the largest index i' less than i and such that either a_{i'} = 1 or the largest prime factor of a_{i'} is different from the largest prime factor of a_i.

For the base case, we have F(0,S) = 0 for any S.

EXPLANATION:

Two numbers are coprime if and only if they don’t share a common factor. This allows us to check whether two numbers are coprime without having to compute \gcd. Let P(k) be the set of prime factors of k. For example, P(980) = \{2, 5, 7\}. Then a and b are coprime if and only if P(a) \cap P(b) = \emptyset.

This formulation also gives us a straightforward dynamic programming solution. Suppose the numbers are [a_1, a_2, \ldots, a_n]. If S is a set of primes, let F(i,S) be size of the largest pairwise-coprime of [a_1, a_2, \ldots, a_i], assuming the primes in S have already been taken, i.e., no prime in S appears as a prime factor in the sublist. Then the answer that we want is F(n,\emptyset). F(i,S) itself can be computed with the following recurrence:

F(i,S) = \begin{cases} F(i-1,S) & \text{if $S \cap P(a_i) \not= \emptyset$} \\ \max(F(i-1,S), 1 + F(i-1, S \cup P(a_i))) & \text{if $S \cap P(a_i) = \emptyset$} \end{cases}

For each value v up to 1000, we can precompute P(v).

To understand the recurrence, notice that there are two types of pairwise-coprime sublists of [a_1, a_2, \ldots, a_i].

  • Pairwise-coprime sublists that doesn’t contain a_i. In this case, the whole list is a sublist of [a_1, a_2, \ldots, a_{i-1}], so the largest such sublist is F(i-1,S).

  • Pairwise-coprime sublists that contains a_i. This is only valid if S doesn’t contain any prime factor of a_i, that is, S \cap P(a_i) = \emptyset.

    Now, if we remove a_i from this sublist, the remaining values form a sublist of [a_1, \ldots, a_{i-1}], with the additional condition that the values don’t have prime factors from P(a_i). The largest size of such a sublist is F(i-1,S \cup P(a_i)), so if we bring a_i back to the sublist, the size becomes 1 + F(i-1,S \cup P(a_i)).

So, F(i,S) must be the larger between these two.

Unfortunately, this runs very slowly. To see this, note that there are 168 primes below 1000, to the number of possible sets S is 2^{168}, which is a very large number!

Small and big primes

We can improve this solution by noticing that every prime > \sqrt{1000} only ever appears alongside primes \le \sqrt{1000} in any number. In other words, suppose we call a prime number small if it is \le \sqrt{1000} and big otherwise. Then a number cannot have two big prime factors at the same time, because suppose n has the big prime factors p and q. Then n \ge pq > \sqrt{1000}\sqrt{1000} = 1000, which violates the constraints.

This means that we can handle big primes specially. For example, consider a big prime factor p. Consider the list of values that are multiples of p. We can select at most one number in that list, and after choosing that number, we can basically ignore the prime factor p! In other words, we don’t have to add p to the set S because the remaining numbers don’t have p as a prime factor.

This gives us an improved version of our DP solution. First, we sort the list [a_1, \ldots, a_n] in increasing order of their largest prime factor. This way, for each big prime p, its multiples will appear consecutively in the array. Next, we define S(k) as the set of small prime factors of k. Next, we redefine F so that S only contains the set of taken small primes. Now, the answer is still F(n,\emptyset), but the recurrence for F(i,S) becomes slightly different. Consider a particular F(i,S). Again, there are two types of pairwise-coprime sublists:

  • Pairwise-coprime sublists that doesn’t contain a_i. This case is the same as before. The whole list is a sublist of [a_1, \ldots, a_{i-1}], so the largest such sublist is F(i-1,S).

  • Pairwise-coprime sublists that contains a_i. As before, this is only valid if S doesn’t contain a prime factor of a_i. But this time, S only contains small primes, so this is the same as S \cap S(a_i).

    Now, if we remove a_i from the sublist, the remaining values form a sublist of [a_1, \ldots, a_{i-1}] with the additional condition that the values don’t have prime factors from P(a_i). But note that S can only contain small prime factors, so F(i-1, S \cup P(a_i)) is invalid if a_i has a big prime factor. But in such a case, remember that the multiples of big prime factors can be found consecutively in the array, so all we have to do is find the largest index i' such that the largest prime factor of a_{i'} is different from the largest prime factor of a_i. So instead of calling F(i-1, S \cup P(a_i)), we call F(i', S \cup S(a_i)).

    By adding a_i back, we get the size of the sublist as 1 + F(i', S \cup S(a_i)).

As before, F(i,S) must be the larger among these two candidates.

More formally, we now find the following recurrence for F(i,S):

F(i,S) = \begin{cases} F(i-1,S) & \text{if $S \cap S(a_i) \not= \emptyset$} \\ \max(F(i-1,S), 1 + F(i', S \cup S(a_i))) & \text{if $S \cap S(a_i) = \emptyset$} \end{cases}

where i' is defined as:

  • If a_i doesn’t have a big prime factor, then i' = i-1.
  • If a_i has a big prime factor, then i' is the largest index less than i and such that the largest prime factor of a_{i'} is different from the largest prime factor of a_i.

Now, this time, there are only 11 small primes, the number of possible sets S is now just 2^{11} = 1024, and the number of distinct valid arguments to F is (n+1)\cdot 2^{11} = 2050048, which is much more manageable.

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester

4 Likes

“Two numbers are coprime if and only if they share a common factor”, something wrong with this statement in the first line of explanation!

1 Like

@lohit_97 Corrected. Thank you!

i am trying to solve this question greedily. i sort the list of input numbers according to the number of different prime divisiors in ascending order.
then there is the list of used prime numbers.

then i traverse each of the input numbers in above mentioned order and for each number, if all the prime divisors are not used, mark them used in the prime number list and add 1 to ans. getting WA.
pls help.

SAMPLE 5
1 2 3 4 5
DIFFERENT PRIME DIVISORS (sorted list)
1-0
2-0
3-0
5-0
4-1
traverse above list
if(1) add 1; else check all prime divisors of number (for 2,check 2, if !used,mark and add 1 to ans)
for 4 it checks 2 which is used so nothing is added

pls help where this approach fails

This is a reply for above greedy answer
check this test case

1
3
10 42 715

output should be 2 becoz we can select 42 and 715 which are coprime.
But your approach will give o/p 1. first nos will be sorted according to the no of prime dvisors.
10(2,5),42(2,3,7),715(5,11,13) have 2,3,3 prime divisors respectively.
So, after sorting u will get 10,42,715 once u will mark prime divisors of 10(2 & 5), u will not be able to include 42 and 715 in answer as they have prime div which is already used(2&5). So,greedy soln will give o/p 1, which is wrong.

1 Like