PROBLEM LINK:
Author: Roman Kachur
Tester: Kevin Charles Atienza
Editorialist: Vaibhav Tulsyan
DIFFICULTY:
Easy-medium
PREREQUISITES:
Prime-factorization, GCD, Sieve of Eratosthenes, Dynamic Programming
PROBLEM:
Given a sequence of integers, finding its longest sub-sequence such that the GCD of the every consecutive integer is greater than 1.
QUICK EXPLANATION:
Pre-compute the smallest prime-factor of all integers from 1 to 10^7 using the Sieve of Eratosthenes.
Use dynamic programming to store the maximum length of the required sub-sequence such that consecutive integers have common prime-factors.
f(i, P) stores the maximum length of the sub-sequence uptil index i such that the last-used 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 sub-sequence that had gcd > 1, it is equivalent to saying we want to find the longest sub-sequence
which has a common prime-factor. This is true owing to the nature of the gcd function.
- Approach
For each index i in the given array, we can store the set S of prime factors of all integers we have seen upto this index.
For each of these prime factors P, we can maintain a value count_{P} - the number of integers that have P as a prime factor.
Our final answer would be: max(count_{P}), across all P present in S after going through the entire array.
- Implementation
- We will need to prime-factorize each integer in the array.
We first use sieve to find the smallest prime factor of all integers in range [1…10^7].
Pseudo-code for pre-computing smallest prime factors using sieve:
smallest_prime_factor = [1 for all ints uptil 10^7] # initialize
for i in [2..10^7]:
if smallest_prime_factor[i] == 1:
for j in [i..10^7]:
smallest_prime_factor[j] = i
j += i
Pseudo-code for prime-factorization of a number:
prime_factors = set()
while number != 1:
prime_factors.add(smallest_prime_factor[number])
number /= smallest_prime_factor[number]
Now, we can use dynamic programming to store the maximum possible sub-sequence 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 sub-sequence 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.
- Complexity
- Pre-computation using sieve: O(X*log(log(X))), where X = 10^7.
- Computation of max length sub-sequence: O(N * log_2(Y)), where Y is the number in the array with maximum no. of prime factors.
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.