KIRLAB - Editorial

PROBLEM LINK:

Practice

Contest

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
  1. 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
  1. Pre-computation using sieve: O(X*log(log(X))), where X = 10^7.
  2. 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.