Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Abinash's blog

By Abinash, 6 years ago, In English,

You are developing a 'Love calculator'. So, given two names your software will generate the percentage of their 'love' according to their names. The software requires the following things: 1.The length of the shortest string that contains the names as subsequence. 2.Total number of unique shortest strings which contain the names as subsequence. Now your task is to find these parts.

I find 1st part by computing (length of 1st name +length of 2nd name — LCS(1st name , 2nd name ).

But how to find 2nd part ??

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

We know unique string length from s1.length+s2.length — LCS(s1,s2)=L. Lets define the DP states , one states will be unique string length (L) , another two will be s1.length(a) and s2.length(b). The recurrence will be ... 1.We take a letter from first string means solve(l-1,a-1,b). 2. We take a letter from second string means solve(l-1,a,b-1). 3. If letter from first string and second string same that means solve(l-1,a-1,b-1) cause if we take from both string will not unique. Now come some condition... 1. If letter from first string and second string same that means , we have only one way . solve(l-1,a-1,b-1). 2. If letter from first string and second string different that means we have two way solve(l-1,a-1,b) and solve(l-1,a,b-1) . 3. If any a=0 then we must have take letter from second string means solve(l-1,a,b-1) . 4. If any b=0 then we must have take letter from first string means solve(l-1,a-1,b).

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Dada, what was your final solution ?? :D

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please Explain the base case !!!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    int solve(int l,int a,int b) {

     if(l==0)
     return 1;
     if(dp[l][a][b]!=-1)
     return dp[l][a][b];
     if(a==0)
     return dp[l][a][b]=solve(l-1,a,b-1);
     if(b==0)
     return dp[l][a][b]=solve(l-1,a-1,b);
    
    if(s1[a-1]==s2[b-1])
    return dp[l][a][b]=solve(l-1,a-1,b-1);
    return dp[l][a][b]=(solve(l-1,a,b-1)+solve(l-1,a-1,b));
    

    }

    int not understanding why my implementation is not working for the sample test case

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

first, calculate LCS, all states by d[n][m]

build dynamic on this states :

dp[i][j] :

  1. s[i] == t[j] -> dp[i + 1][j + 1] += dp[i][j]

else

  1. d[i][j + 1] + 1 == d[i + 1][j + 1] -> dp[i + 1][j + 1] += dp[i][j + 1]

  2. d[i + 1][j] + 1 == d[i + 1][j + 1] -> dp[i + 1][j + 1] += dp[i][j + 1]

that means, if we came from 2 states we need to add both

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

The main problem of this problem is to understand the problem well. :P

There's 2 parts of this problem.

  1. Finding the shortest length of the string that contains the both name as sub-sequences.
  2. Finding the number of unique shortest string that contains the both name as sub-sequences.

For the 1st part answer is — ans=a.size() + b.size() — lcs(0,0);

For the 2nd part find the lcs string. If a[i]==b[j] go to call(i+1,j+1) else check which one is greater between lcs(i+1,j) and lcs(i,j+1). If lcs(i+1,j) is greater go to call(i+1,j), if lcs(i,j+1) is greater go to call(i,j+1) and if both are equal, then call(i+1,j)+cal(i,j+1).

Base Case: when you reach at the end of any string return 1;

Critical Case: when you are finding lcs(0,0) do memoization even for the base case. I mean if i==a.size() return dp[i][j]=0;

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

N is the length of the first string and M is the length of the second string. void Compute_Ways() { lli i,j;

rep(i,0,N+1)
{
    Ways[i][0]=1;
}

rep(i,0,M+1)
{
    Ways[0][i]=1;
}

rep(i,1,N+1)
{
    rep(j,1,M+1)
    {
        if(s[i-1]==s1[j-1])
        {
            Ways[i][j]=Ways[i-1][j-1];
        }
        else
        {
            if(LCS[i-1][j]==LCS[i][j-1])
            {
                Ways[i][j]=Ways[i-1][j]+Ways[i][j-1];
            }
            else
            {
                if(LCS[i-1][j]>LCS[i][j-1])
                Ways[i][j]=Ways[i-1][j];
                else
                Ways[i][j]=Ways[i][j-1];
            }
        }
    }
}

}

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain briefly why do we use the LCS to find ways?