KIRLAB - Editorial

editorial
,
1

How do we solve the KIRLAB Problem

2 Likes
2

Please stay calm, admin ll upload editorials soon

1 Like
3

The admins will soon upload them but you can have a look at my approach. I used prime factorization to solve the problem. First for any pair of numbers to have a gcd greater than 1 signifies the fact that both of them have at least one common prime factors.

So what id did was i maintained a DP array to store the longest length of each subsequences.
Basically you have to solve in the following way:-

Let us suppose a certain number of prime factors have already been mapped in the DP array. Now when you get another element in the array suppose ai , u break it into its prime factors and map them into the DP array. Now just check for the largest mapped value in the DP array and update the entire DP array with the max value, by doing this you are ensuring the fact that at each step u already have the longest subsequence mapped.

Now you can ask what if we get a number whose none of the prime factors are previously mapped, for this also just maintain a flag to check for it.

I know it would be hard to understand the concept by only reading this, but the editorial would be much more neat and readable.

you can check my code at :- THIS LINK

1 Like
4

Here’s my approach -
Store all the smallest prime of numbers of all numbers till 10^7.
Here’s how you can do it using Sieve of Eranthosenes. http://codeforces.com/blog/entry/7262
Now you can prime factorize in log n.
Now for each test case make a dp array of size 10^7.
Now for each element in the array, do its prime factorization in log n time and store in an array x.
Now go through x. Find the maximum of dp[i] for i in x and call it y.
all the d[i] for i in x will became y+1.
Repeat the steps.
Final answer is max(max(dp),1). Note while taking the max of dp don’t include 1.

My code - https://www.codechef.com/viewsolution/12238894

1 Like
5

Here is the detailed approach atulac - KIRLAB Explained.
Comment to get your doubts cleared.

3 Likes
6

It’s been more than a month now, still the editorials of December Long challenge are not posted. Even the Jan Long challenge’s editorials are posted now. If there is one thing that separates Codechef from other sites is the editorials. How unprofessional from Codechef…

2 Likes