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

2★melfice
71725
accept rate: 0%

edited 15 Jan, 21:26

admin's gravatar image

0★admin ♦♦
19.0k348495531


12next »

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
603
accept rate: 0%

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

@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
411
accept rate: 0%

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 ♦
13.6k11036
accept rate: 19%

that's more work for the tester too :P

(15 Jan, 21:47) abdullah7685★

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
1974
accept rate: 6%

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

3★bvsbrk
111
accept rate: 0%

Thanks for keeping it simple :)

(21 Jan, 16:10) harrypotter02★

@bvsbrk Did you get DP approach ?

(21 Jan, 16:15) harrypotter02★

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

2★prashant231997
0
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

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

4★iprakhar22
132
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

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:

×14,365
×3,155
×1,754
×183
×91
×6

question asked: 14 Jan, 03:25

question was seen: 2,372 times

last updated: 08 Feb, 00:11