STRMRG - Editorial

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

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

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: CodeChef: Practical coding for everyone

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.

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

@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

@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

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

can anyone explain what is wrong in my solution CodeChef: Practical coding for everyone

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

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.

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

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

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

Thanks for keeping it simple :slight_smile:

@bvsbrk Did you get DP approach ?

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.

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

@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: CodeChef: Practical coding for everyone

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

#include<bits/stdc++.h>
using namespace std;

int lcs(char* X, char* Y, int m, int n)
{
int L[m + 1][n + 1];
int i, j;
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++) {
if (i == 0 || j == 0)
L[i][j] = 0;

        else if (X[i - 1] == Y[j - 1])
            L[i][j] = L[i - 1][j - 1] + 1;

        else
            L[i][j] = max(L[i - 1][j], L[i][j - 1]);
    }
}

/* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
return L[m][n];

}

int main()
{
int t; cin>>t;
while(t–)
{
int n,m; cin>>n>>m;
char a[n];
char b[m];
int x=1,y=1;
for(int i=0;i<n;i++) {
cin>>a[i];
if(i==0) continue;
if(a[i-1] != a[i]) x++;
}
for(int i=0;i<m;i++) {
cin>>b[i];
if(i==0) continue;
if(b[i-1] != b[i]) y++;
}

    int res = lcs(a,b,n,m);
   // cout<<x+y<<endl;
    cout<<x+y-res<<"\n";
}

}
what is the error guys?