PROBLEM LINK:Author: Hasan Jaddouh DIFFICULTY:EASY PREREQUISITES:Dynamic programming PROBLEM: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 EXPLANATIONUse $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$}$$ You can implement it in the following manner:
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. RELATED PROBLEMS:
This question is marked "community wiki".
asked 14 Jan, 03:25

@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. answered 15 Jan, 21:37

I really think that this question should have had the clause "Also output the string C, which results after merging string A and String B such that F(C) is minimized. In case of multiple correct answers, print any." answered 15 Jan, 21:44

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. answered 15 Jan, 22:25

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 answered 16 Jan, 09:35

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 subquadratic algorithm for the LCS. References: answered 15 Jan, 21:41

@piyush_ravi I think this is because of time constraint set for python codes. As I have submitted a code in python 3.5 https://www.codechef.com/viewsolution/16949756 which gives me TLE in long test cases but when I submitted the same code in C++ I got AC https://www.codechef.com/viewsolution/16957071. answered 16 Jan, 01:00

can somebody tell me how to do bottoms up DP to the solution indicated above? answered 16 Jan, 17:19

Can someone tell me how did they comeup with the LCS solution? Was there a logic behind this or what is the reason this works? Thanks answered 16 Jan, 23:12

@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? answered 17 Jan, 02:26
