You are not logged in. Please login at www.codechef.com to post your questions!

×

STRMRG - Editorial

PROBLEM LINK:

Practice
Contest

Author: Hasan Jaddouh
Tester: Alexey Zayakin
Editorialist: Oleksandr Kulkov

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 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".

asked 14 Jan, 03:25

melfice's gravatar image

4★melfice
811637
accept rate: 0%

edited 15 Jan, 21:26

admin's gravatar image

0★admin ♦♦
19.6k349497539


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.

link

answered 15 Jan, 20:34

prakhar17252's gravatar image

5★prakhar17252
23618
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★

@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.

link

answered 15 Jan, 21:37

madhav_1999's gravatar image

5★madhav_1999
662
accept rate: 20%

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."

link

answered 15 Jan, 21:44

vijju123's gravatar image

5★vijju123 ♦
14.9k11856
accept rate: 18%

that's more work for the tester too :P

(15 Jan, 21:47) abdullah7686★

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.

link

answered 15 Jan, 22:25

gomu's gravatar image

4★gomu
2074
accept rate: 5%

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

link

answered 16 Jan, 09:35

bvsbrk's gravatar image

2★bvsbrk
112
accept rate: 0%

Thanks for keeping it simple :)

(21 Jan, 16:10) harrypotter04★

@bvsbrk Did you get DP approach ?

(21 Jan, 16:15) harrypotter04★

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:

  1. https://www.codechef.com/JAN18/status/STRMRG?page=9&sort_by=All&sorting_order=asc&language=4&status=15&handle=&Submit=GO
link

answered 15 Jan, 21:41

piyush_ravi's gravatar image

1★piyush_ravi
92
accept rate: 0%

edited 15 Jan, 21:42

Mine did get AC. Although I use Pypy but it's still Python.

(15 Jan, 22:38) dwij285★

@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.

link

answered 16 Jan, 01:00

prashant231997's gravatar image

4★prashant231997
101
accept rate: 0%

can somebody tell me how to do bottoms up DP to the solution indicated above?

link

answered 16 Jan, 17:19

akshatsharma's gravatar image

4★akshatsharma
282
accept rate: 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

link

answered 16 Jan, 23:12

iprakhar22's gravatar image

3★iprakhar22
324
accept rate: 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?

link

answered 17 Jan, 02:26

mehta_55's gravatar image

3★mehta_55
11
accept rate: 0%

edited 17 Jan, 02:30

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

link

answered 18 Jan, 17:58

worldunique's gravatar image

3★worldunique
1297
accept rate: 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.

link

answered 20 Jan, 14:32

p1p5_5's gravatar image

3★p1p5_5
708
accept rate: 0%

Anybody got 100 pts in python ?? Please share the link or give it a try .

link

answered 21 Jan, 12:28

harrypotter0's gravatar image

4★harrypotter0
278110
accept rate: 1%

@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

link

answered 21 Jan, 19:17

abhi55's gravatar image

4★abhi55
426
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.

Link: https://www.codechef.com/viewsolution/17087660

(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★

@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

link

answered 21 Jan, 19:39

abhi55's gravatar image

4★abhi55
426
accept rate: 6%

edited 21 Jan, 19:41

@vijju123 I really think that adding the clause to output the resulting string wouldn't have made things much tougher...

  1. Compress the input strings by removing consecutive duplicate letters.
  2. Find the lcs(a, b) and from the expression mentioned compute the minimum value.
  3. 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.

link

answered 22 Jan, 03:01

sapfire's gravatar image

4★sapfire
412
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) vijju123 ♦5★

@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) harrypotter04★

can anyone explain what is wrong in my solution https://www.codechef.com/viewsolution/17183876

link

answered 28 Jan, 13:06

viditganpi's gravatar image

2★viditganpi
1
accept rate: 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

link

answered 01 Feb, 01:55

iambatman93's gravatar image

0★iambatman93
11
accept rate: 0%

edited 01 Feb, 01:57

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

question asked: 14 Jan, 03:25

question was seen: 2,805 times

last updated: 08 Feb, 00:11