You’re given two strings A and B. You have to merge those strings into string C in such a way that amount of valid indices i such that C_i \neq C_{i+1} is minimized.

QUICK EXPLANATION

Use 2 \cdot n \cdot m dynamic programming to mark length of merged prefixes and string from which you took last letter.

EXPLANATION:

This problem is straightforward if you use dynamic programming of following form:

DP[pos1][pos2][lastchar]=\text{answer if you merged prefixes $A_{pos_1}$ and $B_{pos_2}$ and last character was from string $lastchar$}

Note that it should be 2 \cdot 2 \cdot n \cdot m and not 26 \cdot n \cdot m since the last one will not fit into TL.

In the code above we consider that we already merged prefixed A_{idx_1} and B_{idx_2}. Variable pz indicates if we had character from A (in case pz=0) or from B (in case pz=1) on the top before adding new character and nz indicates from which string we added new character (same way as pz). After that new character we can assume that we merged prefixed A_{ndx_1} and B_{ndx_2}. Answer for DP[ndx_1][ndx_2][nz] can be relaxed by answer for DP[idx_1][idx_2][pz] plus one if old top character and new top character do not match.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

This question can also be answered using Longest common subsequence.
The answer will be f(s1) + f(s2) - lcs(s1,s2) where s1 and s2 are the two strings.

Yup, the large number of submissions for a 5th problem could only mean one thing that there is pretty standard implementation of it available out there.

@prakhar17252 You’ve got the wrong expression. We don’t have to subtract the lcs of the original strings. We have to subtract the lcs of the reduced substrings of the strings where each section is represented by only one instance of the repeating character.

I could not find one submission in Python which got the 100 points.[1] All these days I spent my time trying to implement the sub-quadratic algorithm for the LCS.

I used 26 instead of 2*2 as short int to pass memory limits, along with some optimisations and got AC. My solution. There should have been stronger test cases. The only downside was I did 67 submissions.

The answer is as simple as this. Just remove all the consecutive duplicates in both the strings like if the string is hello make it as helo. This can be made in O(n) time.

After this find lcs of both modified strings. The answer is length(s1) + length(s2) - lcs

@bvsbrk can you explain how your logic works? why are we compressing strings(removing consecutive duplicates)? and how lcs will lead to the required answer?

Shouldn’t the answer be f(s1)+f(s2)-f(lcs(s1,s2))? Because lcs(s1,s2) will return a string s3 and we have to apply the function f(s3) to determine exactly how many indices satisfies Ci≠Ci+1.

Hi, Can anyone please tell me why I could get only test cases subtask #2 to pass and not others. I had tried it for 4 continuous days to identify my mistake but in vain. I got really frustrated at one moment of time. It will be really helpful if someone can point me the mistake or the test case for which it fails.The link to my submission is: https://www.codechef.com/viewsolution/17087660