Can anyone share their approach to solve KIRLAB

How to solve this DEC16 Long Challenge’s problem KIRLAB. I tried to solve it for 30 points using DFS, but didn’t got AC. Can anyone share their approach?

1 Like

It can be done with factorization, we have to find the maximum length subset such that ajacent elements present in that subset have gcd > 1.
Traverse the element one by one.

For first element factorize the number into primes , and for each prime do hashing[prime] = 1

Now for second number , factorize into primes and for each prime find the maximum value present
in hashing array , for each prime belongs to second number.

Now maximum length subset ending with second element is maximum value present in hashing array + 1,
Then replace all values of primes involved in second element to its maximum length subset.

At each ith element, factorize it into prime numbers , and find the maximum value present corresponding to any prime factor of ith element in hashing array. (Say P )

Its maximum length subset ending at ith element is ( P + 1 ).
Now replace all prime factor of ith element with (P + 1) in hashing array

Factorization of each element can be done in log(N) with seive.

Complexity : N * log(N) for each test case.

Solution : https://www.codechef.com/viewsolution/12161766

1 Like

The solution is on that link??

I first made an array containing lowest prime factor of each number upto 10**7 and then using it found prime factors of all the elements in the array. I stored those prime factors in a hash map.
After this I maintained another hash map of prime factors observed till now(as key) which contained the max no. of gates which could be opened with the last door having that particular prime factor as I iterated over the array. In other words maxCount[p] = k means maximum k gates can be opened such that number of demons in last gate is divisible by p.
The final answer is then max val in maxCount hashing array. A well commented solution in Python ->


[1].


  [1]: http://ideone.com/hQFRkw
1 Like

@vipsharmavip thanks, can you also share the approach to solve KTHMAX problem.