1
$\begingroup$

A sequence is called good if it contains at least one pair of numbers which are adjacent and equal. A good sub-sequence of an array is a sub-sequence of that array which is good and has maximal length.
Now you are given two arrays $S$ and $T$ with integers. You need to find a sub-sequence which is common to both arrays, has maximum length, and is a good sub sequence.

This is a pure dynamic programming problem, in which states ( I am not sure,but is is my guess) are $dp[i][j]$ is answer for $S[1:i]$ and $T[1:j]$ ($A[1:i]$ means subarray of $A$ from $1$ to $i$). But I could not find transition between states, could anyone help me.

P.S - Problem link

$\endgroup$
5
  • $\begingroup$ How do you know that the algorithm has states of the given form? $\endgroup$ – D.W. Sep 15 '20 at 6:44
  • $\begingroup$ @D.W. It appeared trivial to me,there might be extra state i might be missing. $\endgroup$ – nope Sep 15 '20 at 9:26
  • $\begingroup$ I think you are making a faulty assumption, and you should broaden your perspective on what the states might look like... especially since you could not find a recursive relation with those states. $\endgroup$ – D.W. Sep 15 '20 at 16:27
  • $\begingroup$ @D.W. Can you give hint for states ? $\endgroup$ – nope Sep 15 '20 at 16:30
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ – D.W. Sep 15 '20 at 17:04
1
$\begingroup$

A two-dimensional $dp[i][j]$ is not fine enough to enable a recurrence relation. We need to track more information to be able to find the solutions to larger problems from the solutions of smaller problems.

Instead of $dp[i][j]$, try filling the following two tables simultaneously

  • $dp\_good[i][j]$, which means the length of longest common good subsequence of $S[1:i]$ and $T[1:j]$ that ends at $S[i]$ and $T[j]$. This number is $0$ is $S[i]\not=T[j]$.
  • $dp\_bad[i][j]$, which means the length of longest common bad subsequence of $S[1:i]$ and $T[1:j]$ that ends at $S[i]$ and $T[j]$. Here a bad subsequence just means it is not a good subsequence. Again, this number is $0$ is $S[i]\not=T[j]$.

The answer will be the maximum of all $dp\_good[i][j]$.

The above approach should work when you are looking for a sequence that "contains at least one pair of numbers which are adjacent and equal."

For the original problem, Task: ZAJ Stutter, we should define a good string as a stutter, i.e., a string that consists of successive pairs of two equal elements. A bad string will be defined as "almost a stutter", that is, a strings which becomes a stutter if we delete its last element.

$\endgroup$
1
  • $\begingroup$ More techniques are needed to solve that original problem within a second or two if, for example, $n=m=15000$. $\endgroup$ – John L. Sep 15 '20 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.