PROBLEM LINK:
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:
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:
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):
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.