STRMRG - Editorial

editorial
, , , , ,
1

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:

1 Like
2

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.

4 Likes
3

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.

1 Like
4

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

3 Likes
5

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
6

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© is minimized. In case of multiple correct answers, print any.”

2 Likes
7

that’s more work for the tester too :stuck_out_tongue:

8

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.

1 Like
9

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

10

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

11

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

1 Like
12

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

13

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

14

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

15

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

16

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.

2 Likes
17

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©”. Please help.

18

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

19

Thanks for keeping it simple :slight_smile:

20

@bvsbrk Did you get DP approach ?