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

×

KIRLAB - Editorial

0
1

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
  • 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

wittyceaser's gravatar image

2★wittyceaser
3.4k194376
accept rate: 16%

edited 10 Aug, 16:00

admin's gravatar image

0★admin ♦♦
19.6k349497539

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,129
×82

question asked: 13 Mar '17, 20:33

question was seen: 88 times

last updated: 10 Aug, 16:00