Problem Page : KIRLAB
My solution : Solution WA
It is asking to find out the longest subsequence in array such that every adjacent pair of the subsequence has GCD>1, or we can say every adjacent pair shares some common prime factor.
Suppose We are given array A[ ].
I made an array B[ ] of 10^7 size and initialized with all zeroes.
Then I traverse the given array A[ ], and for each element A[i], I increment B[j] for all prime factors j of A[i] and choose the max of the updated $B[j]$s and then update all these $B[j]$s with this chosen max value. In this way, max of array B[] now tells the max length of subsequence found till now.
This solution is giving WA. Please tell me what is wrong in my solution.
Thanks