viralm's blog

Need Help in Solving a DP Problem !!
By viralm, history, 8 years ago, In English

How to solve this problem — http://codeforces.net/problemset/problem/346/B ? I am not able to understand much by reading the editorial. Please Help!!

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by viralm (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone?

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

You have 3 states:

dp[position on the first string][position on the second string][where you are on the virus]

dp[i][j][k]

if k == virus.size() return -INF, if i == first.size() || j==second.size() return 0

then you take the maximum between

dp[i+1][j][k], dp[i][j+1][k] and if first[i]==second[j] you can take it and and you'll have 1 + dp[i+1][j+1][next_k]. You need to use KMP to know what's the next_k depending on the letter you are taking. Make an array that will remember which choice you took on each step and you can run through the memoization to get the answer.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In order to use kmp, we need to keep track of the LCS found upto a particular state. How do you suggest to do that? Should I store the LCS itself in another array[][][] ?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No you don't need to store it. The next state of the KMP depends on:

      Next letter (on the dp you know what's the next letter)

      Where you are on the virus (that's the k)

      And nothing more

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Notice that the optimal subsequence will be a subsequence of the longest common subsequence. Then, it is a good idea to obtain the longest common subsequence using Needleman-Wunsch (use cost for mismatch equal to infinity and deletions/insertions cost 0) or other equivalent algorithm. Once you have this LCS, use a longest increasing subsequence-like approach in order to know the answer.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    That's not true:

    "aaab" and "abaa", the LCS is "aaa". If the virus is "a", the answer is actually "b"

    → Reply