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

×

# KIRLAB - Editorial

Practice

Contest

Author: Roman Kachur

Tester: Kevin Charles Atienza

Editorialist: Vaibhav Tulsyan

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:

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.

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.

This question is marked "community wiki".

asked 13 Mar '17, 20:33 3.4k194377
accept rate: 16% 19.8k350498541

 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,852
×82

question asked: 13 Mar '17, 20:33

question was seen: 143 times

last updated: 10 Aug '18, 16:00