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 '18, 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 '18, 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 '18, 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 '18, 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 '18, 09:35
Thanks for keeping it simple :)
(21 Jan '18, 16:10)
@bvsbrk Did you get DP approach ?
(21 Jan '18, 16:15)

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 '18, 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 '18, 01:00

can somebody tell me how to do bottoms up DP to the solution indicated above? answered 16 Jan '18, 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 '18, 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 '18, 02:26

this question should have been the 4th one not 5th one .. too much imbalance is not good we get a loss of many medium type questions answered 18 Jan '18, 17:58

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 Just for explanation, I have used this logic: f(s1)+f(s2)f(lcs(s1,s2)). So, I calculate the LCS string of the 2 strings and apply the given function "f(C)". Please help. answered 20 Jan '18, 14:32

Anybody got 100 pts in python ?? Please share the link or give it a try . answered 21 Jan '18, 12:28

@p1p5_5 i saw your solution lcs part is correct but you should do that consecutive diffrent character only in string implementation before LCS in o(n) and after that lcs it will give correct answer and also optimize your dp part(LCS) in most cases except case (abcdefghi....wxyz) because no consecutive same character. and then f(a)+f(b)lcs(a,b) will give correct answer. you can check my code link .if any problem persist you can ask answered 21 Jan '18, 19:17
@abhi55 Thanks for answering my doubt. I understood the part of optimization of my LCS function but I did not exactly understood the first part. " but you should do that consecutive diffrent character only in string implementation before LCS in o(n) and after that lcs it will give correct answer" Can you please explain this again? Sorry for this, I did not get my mistake in the program. I have found out LCS including repetition but my function "findCharacters(String)" will always return be the number of indices satisfying Ci≠Ci+1.
(22 Jan '18, 16:45)
i am saying that suppose you have string aabccdee now you can see that consecutive same character will make no change in total cost like in above string you first minimize it in abcde by removing repition of same character which are consecutive in o(n) then perform LCS part on it
(08 Feb '18, 00:11)

@harrypotter0 you can do this in any programming language by below steps: step 1:process both sting A and String B such that no consecutive similiar character exsist.for example abbaaccde would be abacde after processing.it will take o(n) time where n is length of string step 2:compute LCS of processed strings using Dynamic Programming in o(nm) time where n is length of processed String A and m is length of processed string B.LCS computed is length of longest sequence. step 3:answer will be length of processed string A+length of processed string BLCS answered 21 Jan '18, 19:39

@vijju123 I really think that adding the clause to output the resulting string wouldn't have made things much tougher...
I haven't coded it up yet but I'm sure that it or a very minor variation of it might work. answered 22 Jan '18, 03:01
True I never meant that adding that clause was to make it tougher. Point was, seeing his dp states and table I thought it would have been a nice addition to the problem.
(22 Jan '18, 03:06)

can anyone explain what is wrong in my solution https://www.codechef.com/viewsolution/17183876 answered 28 Jan '18, 13:06

I have done an implemenation of dp on the similar lines of editorial and I can't seem to think of a case where it fails but it is failing while submitting. dp[i][j][k] represents, I have taken i characters from string1 and j characters from string2 and the last character is from stringk answered 01 Feb '18, 01:55
