PROBLEM LINK:Author: Roman Kachur Tester: Kevin Charles Atienza Editorialist: Vaibhav Tulsyan DIFFICULTY:Easymedium PREREQUISITES:Primefactorization, GCD, Sieve of Eratosthenes, Dynamic Programming PROBLEM:Given a sequence of integers, finding its longest subsequence such that the GCD of the every consecutive integer is greater than $1$. QUICK EXPLANATION:Precompute the smallest primefactor of all integers from $1$ to $10^7$ using the Sieve of Eratosthenes. Use dynamic programming to store the maximum length of the required subsequence such that consecutive integers have common primefactors. $f(i, P)$ stores the maximum length of the subsequence uptil index $i$ such that the lastused prime factor is $P$. Note: In the DP table, we only need to maintain the max length for each prime uptil now  without storing the information for each and every index. EXPLANATION:Subtask 1: For this subtask, the constraint on the no. of integers ($N$) in the array is: $1 \le N \le 10^3$. For each index $i$, we can find number of indexes $j (j \lt i)$ such that $gcd(a_i, a_j) > 1$. Let's call this value $V_i$. Our goal is to maximize $V_i$ over all $i$ from $1$ to $N$. The complexity of this solution is: $O(N^2 * log(max(a_i)))$. This solution would fetch 30 points. Subtask 2: When we say that we want to find the longest subsequence that had $gcd > 1$, it is equivalent to saying we want to find the longest subsequence which has a common primefactor. This is true owing to the nature of the $gcd$ function.
Our final answer would be: $max(count_{P})$, across all $P$ present in $S$ after going through the entire array.
We first use sieve to find the smallest prime factor of all integers in range [1..10^7]. Pseudocode for precomputing smallest prime factors using sieve:
Pseudocode for primefactorization of a number:
Now, we can use dynamic programming to store the maximum possible subsequence length that ends at index $i$, such that $a_i$ contains $P$ as a prime factor. Let the prime factors of $a_i$ be $p_1, p_2, p_3, ... , p_K$. For each $p_j$, let's say the maximum possible subsequence length such that the previous selected number had a common prime factor was $l_j$. We choose the maximum length $M$ equal to $max(l_j) (1 \le j \le K)$. We update $dp(p_j)$ with the value $M$. While performing updates, we maintain a global maximum  the maximum $M$ calculated uptil now.
AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution can be found here. Tester's solution can be found here. Editorialist's solution can be found here.
This question is marked "community wiki".
asked 13 Mar '17, 20:33
