OJ Board

Posted: **Mon Jan 02, 2006 10:38 pm**

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

Posted: **Tue Jan 03, 2006 4:39 am**

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

Posted: **Tue Jan 03, 2006 5:12 am**

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

Posted: **Tue Jan 03, 2006 5:22 am**

I have sent you a PM. Hope that helps.

Posted: **Tue Jan 03, 2006 7:27 am**

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!

Posted: **Tue Jan 03, 2006 7:34 am**

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.

Posted: **Tue Jan 03, 2006 10:53 am**

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]

Posted: **Tue Jan 03, 2006 11:39 pm**

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

Posted: **Wed Jan 04, 2006 3:53 am**

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

Posted: **Wed Jan 04, 2006 9:14 am**

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

Posted: **Tue Jan 10, 2006 10:26 am**

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.

Posted: **Thu Jan 12, 2006 1:53 pm**

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);
}

Posted: **Thu Jan 12, 2006 7:10 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

Posted: **Thu Jan 12, 2006 8:08 pm**

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

Posted: **Wed Jan 18, 2006 10:10 am**

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]

OJ Board

10981 - String Morphing

TLE

THX