10981 - String Morphing

Moderator: Board moderators

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru
could someone please explain the dynamic programing idea? i'm finding hard to understand the cyk algorithm. thx in advance

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
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
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru
thank you for answering, now i got the idea but how can it be modified to meet the problem requirements?

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
I have sent you a PM. Hope that helps.

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru
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
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
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,target;
char brac,SEQ;
int possible;
int mul;

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

mul=1;
mul=1;
mul=0;
mul=2;
mul=1;
mul=0;
mul=0;
mul=2;
mul=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';
strcat(brac[i][i][source[i]-'a'],"()");
}
}

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

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';
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';
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;
int len=strlen(source);
int i,OK,tlen,j;
c='\0';
strcpy(temp,SEQ);

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

for(j=0;j<tlen;j++)
{
printf("%c",c);
strcat(temp,c);
j+=3;
OK=1;
}
{
strcat(temp,c);
}
else
{
strcat(temp,c);
}
printf("\n");
}
}

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

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

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

len=strlen(word);

for(i=0;i<len;i++)
if(word[i]=='(' && word[i+1]==')')
{
cnt++;
c=source[cnt];
strcat(SEQ,c);
i++;
}
else
{
c=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]
Self judging is the best judging!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

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;
int P;
int tabla={{1,1,0},{2,1,0},{0,2,2}};
void f(char s,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,target;
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-'a';
f(s,c);
if(!T[n-1][c])
puts("None exist!");
else
{
puts(s);
if(n>1)
{
x=P[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[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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
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
Self judging is the best judging!

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
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.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

KvaLe
New poster
Posts: 30
Joined: Sun May 01, 2005 7:45 pm

TLE

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 ;
int l, r, p, P;

node () { l = r = -1, P = p = 0; s  = '\0'; }
};

int root, m;
char ch, s , f ;
node tree ;

int find (int r, char s ) {
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 ) {
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 , int P, int len) {
if (! len || find (root, s)) return;
int i, j, k = insert (root, P, s);
char ns ;
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  = ch, s  = '\0';
if ((i = find (root, s)) == 0) printf ("None exist!");
else print (i);
}
exit (0);
}
``````
Giorgi Lekveishvili

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
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
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

KvaLe
New poster
Posts: 30
Joined: Sun May 01, 2005 7:45 pm

THX

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

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india
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]