jhjfbsbfkbjfnfnfjfj's blog

Nice DP Problem
By jhjfbsbfkbjfnfnfjfj, history, 4 years ago, In English

I have studied about finding LIS (longest increasing subsequence) How do I extend that knowledge to find LIS where gcd(xi, xi+1) > 1? Please help me here is the link to the question https://codeforces.com/problemset/problem/264/B

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hint : The problem is related to prime factors. # of prime factors of $$$a_i$$$ is small.

Another hint
DP hint
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you mean this dp would work dp[i] = dp[i] + 1. where i is one of the primefactors of ith number. right? if yes then the maximum value of this array will be our answer?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      No, (1) all dp[i] must be replaced with (2) (max of all dp[i])+1 where i is one of the primefactors. For example, when a=6, replace dp[2] and dp[3] with max(dp[2],dp[3])+1. This is because (1)[6 is a multiple of 2 and a multiple of 3], and (2)[we can put 6 after a multiple of 2 or a multiple of 3]. However, "max of dp array will be our answer" is right.

      /* If you need, see my submission. */ Sorry my submission isn't fit the explanation.

      → Reply