10981 - String Morphing

[trulo17]

could someone please explain the dynamic programing idea? i'm finding hard to understand the cyk algorithm. thx in advance

[tobby]

This question is similar to matrix chain multiplication. Let me say a bit about the algorithm mentioned in wikipedia. The state is [i, j, c], this means if we can morph characters from ith to i+j-1th position to become character c. For example, if the string is 'abcabc', then [2, 4, 'b'] is if we can morph 'bcab' to 'b'.

[trulo17]

thank you for answering, now i got the idea but how can it be modified to meet the problem requirements?

[tobby]

I have sent you a PM. Hope that helps.

[trulo17]

thanks for the help tobby, now i get the right outputs for all tests inputs in the forum, but i'm getting tle with my O(n^4) algorithm (i think time limit is too strict for this problem, and in fact, for many others in this judge). I'll try to improve it later. Keep posting!

[tobby]

I don't know but my O(n^4) needs only 0.1 sec, so it is not that strict. Maybe the previous posts in this topic may help.

[shanto86]

well i implimented n^3 code, but it is getting TLE bcoz of string operation. i used "string" it was much slow than normal C char operation like: strcat, strcpy. but when i used C char opt, it also got TLE. is there any other trick to get it into N^3?

[code]#include<stdio.h>
#include<string.h>
#include<ctype.h>

char source[200],target[5];
char brac[120][120][3][500],SEQ[500];
int possible[120][120][3];
int mul[3][3];

void INIT()
{
int len,i,j,a;

mul[0][0]=1;
mul[0][1]=1;
mul[0][2]=0;
mul[1][0]=2;
mul[1][1]=1;
mul[1][2]=0;
mul[2][0]=0;
mul[2][1]=2;
mul[2][2]=2;

len=strlen(source);

for(i=0;i<len;i++)
for(j=0;j<len;j++)
for(a=0;a<3;a++)
possible[i][j][a]=-1;

for(i=0;i<len;i++)
{
possible[i][i][source[i]-'a']=0;
brac[i][i][source[i]-'a'][0]='\0';
strcat(brac[i][i][source[i]-'a'],"()");
}
}

void DP()
{
int len,l,i,j,k,a,b,c;
char temp[500];

len=strlen(source);

for(l=2;l<=len;l++)
{
for(i=0;i<=len-l;i++)
{
j=i+l-1;

for(k=i;k<j;k++)
{
//Concat [i][k] AND [k][j]

for(a=0;a<3;a++)
for(b=0;b<3;b++)
if(possible[i][k][a]==0 && possible[k+1][j][b]==0)
{
c=mul[a][b];

if(possible[i][j][c]==0)
{
temp[0]='\0';
strcat(temp,"(");
strcat(temp,brac[i][k][a]);
strcat(temp,brac[k+1][j][b]);
strcat(temp,")");

if(strcmp(temp,brac[i][j][c])<0)
strcpy(brac[i][j][c],temp);
}
else if(possible[i][j][c]==-1)
{
brac[i][j][c][0]='\0';
strcat(brac[i][j][c],"(");
strcat(brac[i][j][c],brac[i][k][a]);
strcat(brac[i][j][c],brac[k+1][j][b]);
strcat(brac[i][j][c],")");

possible[i][j][c]=0;
}
}
}
}
}
}

void ANS()
{
char temp[500];
char head[500],c[2];
int len=strlen(source);
int i,OK,tlen,j;
c[1]='\0';
strcpy(temp,SEQ);

printf("%s\n",source);
for(i=1;i<len;i++)
{
strcpy(head,temp);
temp[0]='\0';
OK=0;

tlen=strlen(head);

for(j=0;j<tlen;j++)
if(!OK && head[j]=='(' && isalpha(head[j+1]) && isalpha(head[j+2]) && head[j+3]==')')
{
c[0]=mul[head[j+1]-'a'][head[j+2]-'a']+'a';
printf("%c",c[0]);
strcat(temp,c);
j+=3;
OK=1;
}
else if(isalpha(head[j]))
{
c[0]=head[j];
strcat(temp,c);
printf("%c",head[j]);
}
else
{
c[0]=head[j];
strcat(temp,c);
}
printf("\n");
}
}


void PURIFY()
{
int len=strlen(source);

if(possible[0][len-1][target[0]-'a']==-1)
{
printf("\n");
return;
}

char word[500],c[2];
c[1]='\0';
strcpy(word,brac[0][len-1][target[0]-'a']);
SEQ[0]='\0';
int cnt=-1,i;

len=strlen(word);

for(i=0;i<len;i++)
if(word[i]=='(' && word[i+1]==')')
{
cnt++;
c[0]=source[cnt];
strcat(SEQ,c);
i++;
}
else
{
c[0]=word[i];
strcat(SEQ,c);
}
}

int main()
{
int n;
int OK=0;

scanf("%d",&n);

while(n--)
{
if(OK)
printf("\n");
OK=1;

scanf("%s",source);
scanf("%s",target);

INIT();

DP();

PURIFY();

ANS();
}

return 0;
}[/code]

[mf]

Strictly speaking, your code is O(n^4), because strcpy(), strcat() and strcmp() are linear in the size of their inputs.

One trick that I've used is this: at each step, find (with an additional O(n^3) DP), what is the longest prefix of the string, such that after multiplying the characters in it from left to right, the resulting string still can be morphed to the target character.

All tests in judge's input are such, that this trick reduces the original string to a string of most 12 characters! This explains, why backtracking solutions gets accepted...

[trulo17]

Code: Select all

#include<cstdio>
#include<iostream>
#include<deque>
#include<cctype>
#include<cstdlib>
#include<vector>
#include<map>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<set>
#include<sstream>
#include<cmath>
#define inf 2000000000
using namespace std;
bool T[100][100][3];
int P[100][100][3];
int tabla[3][3]={{1,1,0},{2,1,0},{0,2,2}};
void f(char s[101],int t)
{
    int i,j,k,c1,c2,n=strlen(s);
    for(i=0;i<n;++i)
        for(j=i;j<n;++j)
            for(c1=0;c1<3;++c1)
            {    
                T[i][j][c1]=false;
                P[i][j][c1]=inf;
            }
    for(i=0;i<n;++i)
        T[i][i][s[i]-'a']=true;
    for(i=n-2;i>-1;--i)
        for(c1=0;c1<3;++c1)
            for(c2=0;c2<3;++c2)
                if(T[i][i][c1]&&T[i+1][i+1][c2])
                {
                    T[i][i+1][tabla[c1][c2]]=true;
                    P[i][i+1][tabla[c1][c2]]=i;
                }
    for(i=n-3;i>-1;--i)
        for(j=i+2;j<n;++j)
            for(k=i;k<j;++k)
                for(c1=0;c1<3;++c1)
                    for(c2=0;c2<3;++c2)
                        if(T[i][k][c1]&&T[k+1][j][c2])
                        {
                            T[i][j][tabla[c1][c2]]=true;
                            P[i][j][tabla[c1][c2]]=min(P[i][j][tabla[c1][c2]],min(P[i][k][c1],P[k+1][j][c2]));
                        }
}
int main()
{
    int N,test;
    int i,j,n,n2,c,x;
    char s[101],target[2];
    scanf("%d",&N);
    for(test=0;test<N;++test)
    {
        if(test!=0)
            putchar('\n');
        scanf("%s%s",s,target);
        n=strlen(s);
        n2=n-1;
        c=target[0]-'a';
        f(s,c);
        if(!T[0][n-1][c])
            puts("None exist!");
        else
        {
            puts(s);
            if(n>1)
            {
                x=P[0][n-1][c];
                for(s[x]='a'+tabla[s[x]-'a'][s[x+1]-'a'],j=x+1;j<n2;++j)
                    s[j]=s[j+1];
                s[j]='\0';
                puts(s);
            }
            for(i=2;i<n;++i)
            {
                f(s,c);
                x=P[0][n-i][c];
                --n2;
                for(s[x]='a'+tabla[s[x]-'a'][s[x+1]-'a'],j=x+1;j<n2;++j)
                    s[j]=s[j+1];
                s[j]='\0';
               puts(s);
            }
        }
    }
}

this is my code. I don't know if i'm doing what you people are saying. I would appreciate any suggestion.Thx in advance

[shanto86]

mf, can u plz describe ur N^4 algo? and what is ur prefix idea? u mean say for a fixed length l, the same subsequence u will not clculate more than once? to do so what do u use to compare? STL map?

and what is the pruning idea in bktrk soln?

Mahbub

[ayon]

well, i used backtracking and got accepted in 0.242 sec. it's not so fast as DP solution, but fast enough for being accepted. the pruning idea is very simple here. i used BST. every time i found a string i searched if the string is already in the BST. if already in the BST i pruned. otherwise inserted in the BST and go forward. a good hash table also help for the searching, i guess. hash table or BST, whatever you feel comfort to use. but by using BST, after every input, dont forget to free the whole BST. i guess, who are not good enough in DP(like me), backtracking will help in this problem.

[KvaLe]

ayon I used your algorithm and got TLE. Here is my code, if u find there any bug please post here:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

class node {
  public:
    char s [100];
    int l, r, p, P;
    
    node () { l = r = -1, P = p = 0; s [0] = '\0'; }
};

int root, m;
char ch, s [100], f [100][100];
node tree [100000];

int find (int r, char s [100]) {
  if (r < 1) return 0;
  switch (strcmp (s, tree [r].s)) {
    case -1: return find (tree [r].l, s);
    case 0: return r;
    case 1: return find (tree [r].r, s);
  }
}

int insert (int r, int P, char s [100]) {
  if (! r) {
    strcpy (tree [root = ++m].s, s);
    return m;
  }
  switch (strcmp (s, tree [r].s)) {
    case -1:
      if (tree [r].l != -1) return insert (tree [r].l, P, s);
      else {
        strcpy (tree [++m].s, s);
        tree [r].l = m, tree [m].p = r, tree [m].P = P;
      }
      break;
    case 1:
      if (tree [r].r != -1) return insert (tree [r].r, P, s);
      else {
        strcpy (tree [++m].s, s);
        tree [r].r = m, tree [m].p = r, tree [m].P = P;
      }
      break;
  }
  return m;
}

void rec (char s [100], int P, int len) {
  if (! len || find (root, s)) return;
  int i, j, k = insert (root, P, s);
  char ns [100];
  for (i = 1; i < len; i++) {
    ns [i-1] = f [s [i-1]][s [i]];
    for (j = i+1; j < len; j++) ns [j-1] = s [j];
    ns [len-1] = '\0';
    rec (ns, k, len-1);
    ns [i-1] = s [i-1];
  }
}

void print (int r) {
  if (r < 1) return;
  print (tree [r].P);
  printf ("%s\n", tree [r].s);
}

int main (void) {
  f ['a']['a'] = 'b', f ['a']['b'] = 'b', f ['a']['c'] = 'a';
  f ['b']['a'] = 'c', f ['b']['b'] = 'b', f ['b']['c'] = 'a';
  f ['c']['a'] = 'a', f ['c']['b'] = 'c', f ['c']['c'] = 'c';
  int i, j, t;
  bool q = 0;
  for (scanf ("%d", &t); t--; ) {
    if (q) printf ("\n");
    else q = 1;
    scanf ("%s", &s);
    scanf (" %c", &ch);
    root = m = 0;
    for (i = 0; i < 100000; i++) tree [i] = node ();
    rec (s, 0, strlen (s));
    s [0] = ch, s [1] = '\0';
    if ((i = find (root, s)) == 0) printf ("None exist!");
    else print (i);
  }
  exit (0);
}

[ayon]

see the code below

Code: Select all

#include <stdio.h>
#include <string.h>

void main()
{  
   printf("%d\n", strcmp("abc", "abe"));   
   printf("%d\n", strcmp("abc", "abcA"));   
}

the output is -2 and -65, because strcmp return the difference between the 1st unmatched character of the two strings. here 'c'-'e' = -2 and '\0'-'A' = -65. so in your find() and insert() function,

Code: Select all

switch(strcmp(,))
{
	case -1:
   case 0:
   case 1:
}

is not ok. thanks

[KvaLe]

Thanks, I'll fix it. I got AC with DP, but in 7 sec. How can I impove it?

[ranjit]

mf, you said you can find out what characters need to be merged in O(n^3) dp at every step. Can you please explain how to do that? If you use dp similar to CYK algorithm, then it need not be correct for finding out the characters to merge. because if you use dp[i,j] = function(dp[i,k],dp[k+1,j]), we still dont know the order in which characters are merged in dp[i,k]