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

×

KIRLAB - Editorial

-4
1

How do we solve the KIRLAB Problem

asked 12 Dec '16, 15:16

coder_voder's gravatar image

2★coder_voder
593332
accept rate: 8%

edited 13 Dec '16, 09:09


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

link

answered 13 Dec '16, 09:40

atulac's gravatar image

4★atulac
1837
accept rate: 16%

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

link

answered 12 Dec '16, 17:07

entangledcat's gravatar image

4★entangledcat
993
accept rate: 25%

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

link

answered 12 Dec '16, 18:36

mathecodician's gravatar image

6★mathecodician
2.6k11034
accept rate: 7%

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

link

answered 18 Jan '17, 18:01

aniketsanadhya's gravatar image

1★aniketsanadhya
115210
accept rate: 0%

Please stay calm, admin ll upload editorials soon

link

answered 12 Dec '16, 16:38

neilit1992's gravatar image

3★neilit1992
1.1k13
accept rate: 20%

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

question asked: 12 Dec '16, 15:16

question was seen: 3,921 times

last updated: 18 Jan '17, 18:01