You are not logged in. Please login at www.codechef.com to post your questions!

×

NUMSET - Editorial

7
2

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

This question is marked "community wiki".

asked 19 Jun '16, 15:17

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 30 Jun '16, 23:55

2

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

(21 Jun '16, 19:25) lohit_974★

@lohit_97 Corrected. Thank you!

(30 Jun '16, 23:55) kevinsogo7★

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.

link

answered 03 Jun '17, 13:29

satyam_shekhar's gravatar image

2★satyam_shekhar
111
accept rate: 0%

edited 03 Jun '17, 13:34

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

link

answered 19 Jul '16, 09:15

ankesh18's gravatar image

6★ankesh18
627111
accept rate: 7%

edited 19 Jul '16, 09:17

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,682
×2,172
×1,672
×105
×36
×13

question asked: 19 Jun '16, 15:17

question was seen: 3,538 times

last updated: 03 Jun '17, 13:34