A chain is a sequence of positive integers A1, A2, A3, ..., An such that Ai+1 divides Ai. (In other words, A1 is a divisor of A2, A2 is a divisor of A3, and so on.)
The length of a chain is the number of elements in the sequence.
Given N elements, you need to find a chain of maximum length using a subset of the given elements.
1<=N<=1e6 1<=a[i]<=1e6
Now, you can sort the array and track gcd (LIS like approach), but how do you come up with a solution which adheres to the time limit?
N = 5 array = 4 2 5 80 4
ans = 4, i.e. [2,4,4,80]
Did you try by yourself?
Obvious TLE.
would you please share the problem link?
Btw this solution is completely wrong.
sort -> apply DP
I will lyk if I manage to implement it.
This might work
I don't know if this will help, but the number of distinct elements in the final subset will be < 20. Because:2, 4, 16, ......, log N
Edit: it's wrong, I misunderstood the problem at first.
for every index i and for every prime p, draw an edge from i to the smallest index j such that that A_j is divisible by p*A_i. This creates a DAG and then you can DP on this to find the longest path. I think you can do this N log N.
Could you implement it please, thanks!!!
Won't this TLE? N <= 10^6 and there are roughly 70K primes less than 500000.
For A_i there are only MAX_N/A_i numbers you can multiply by (even less primes), so if you combine identical values that bounds the complexity to the harmonic series (N/1 + N/2 + ...) or N log N.
Oh shoot primes don't even matter, there are very few possible edges (by the same harmonic series argument) so you can just draw all edges explicitly and then find the answer.
Won't this be enough?
sir will this work? I have very little knowledge so asking
dp problem