×

# STRMRG - Editorial

Tester: Alexey Zayakin
Editorialist: Oleksandr Kulkov

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 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}$$

You can implement it in the following manner:

int sz[2];
cin >> sz[0] >> sz[1];
string a[2];
cin >> a[0] >> a[1];
int dp[sz[0] + 1][sz[1] + 1][2];
memset(dp, 0x3F, sizeof(dp));
dp[1][0][0] = dp[0][1][1] = 1;
int idx[2];
for(idx[0] = 0; idx[0] <= sz[0]; idx[0]++) {
for(idx[1] = 0; idx[1] <= sz[1]; idx[1]++) {
for(int pz = 0; pz <= 1; pz++) {
for(int nz = 0; nz <= 1; nz++) {
if(idx[nz] < sz[nz] && idx[pz] > 0) {
int ndx[2] = {idx[0] + !nz, idx[1] + nz};
dp[ndx[0]][ndx[1]][nz] = min(dp[ndx[0]][ndx[1]][nz],
dp[idx[0]][idx[1]][pz] + (a[nz][idx[nz]] != a[pz][idx[pz] - 1]));
}
}
}
}
}
cout << min(dp[sz[0]][sz[1]][0], dp[sz[0]][sz[1]][1]) << endl;


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.

# RELATED PROBLEMS:

This question is marked "community wiki".

4★melfice
811637
accept rate: 0%

19.6k349497539

 5 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. answered 15 Jan, 20:34 236●1●8 accept rate: 6% 1 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. (15 Jan, 21:29) dwij285★ 1 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. (20 Jan, 13:58) p1p5_53★
 3 @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 66●2 accept rate: 20%
 2 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 14.9k●1●18●56 accept rate: 18% that's more work for the tester too :P (15 Jan, 21:47)
 1 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 4★gomu 207●4 accept rate: 5%
 1 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 2★bvsbrk 11●2 accept rate: 0% Thanks for keeping it simple :) (21 Jan, 16:10) @bvsbrk Did you get DP approach ? (21 Jan, 16:15)
 0 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. References: answered 15 Jan, 21:41 9●2 accept rate: 0% Mine did get AC. Although I use Pypy but it's still Python. (15 Jan, 22:38) dwij285★
 0 @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 10●1 accept rate: 0%
 0 can somebody tell me how to do bottoms up DP to the solution indicated above? answered 16 Jan, 17:19 28●2 accept rate: 0%
 0 Can someone tell me how did they come-up with the LCS solution? Was there a logic behind this or what is the reason this works? Thanks answered 16 Jan, 23:12 32●4 accept rate: 0%
 0 @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 3★mehta_55 1●1 accept rate: 0%
 0 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, 17:58 129●7 accept rate: 0%
 0 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, 14:32 3★p1p5_5 70●8 accept rate: 0%
 0 Anybody got 100 pts in python ?? Please share the link or give it a try . answered 21 Jan, 12:28 278●1●10 accept rate: 1%
 0 @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, 19:17 4★abhi55 42●6 accept rate: 6% @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, 16:45) p1p5_53★ 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, 00:11) abhi554★
 0 @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 B-LCS answered 21 Jan, 19:39 4★abhi55 42●6 accept rate: 6%
 0 @vijju123 I really think that adding the clause to output the resulting string wouldn't have made things much tougher... Compress the input strings by removing consecutive duplicate letters. Find the lcs(a, b) and from the expression mentioned compute the minimum value. Keep track of the next character in lcs(a, b) and erase characters from the input string until the head characters are both equal to the next character in lcs(a, b). 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, 03:01 4★sapfire 41●2 accept rate: 0% 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, 03:06) @sapfire @vijju123 some tweaking for x =1 and x=2 with lcs approach got me AC on this one . But can anyone explain to me the D.P. approach , I am clueless on that . (22 Jan, 07:31)
 0 can anyone explain what is wrong in my solution https://www.codechef.com/viewsolution/17183876 answered 28 Jan, 13:06 1 accept rate: 0%
 0 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. Here is my solution 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, 01:55 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,127
×3,615
×1,965
×184
×95
×6