## 10981 - String Morphing

Moderator: Board moderators

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Contact:

### 10981 - String Morphing

Can anyone tell me why am I getting WA?

Code: Select all

``Delete Code``
Please give me some tricky input and output.[/code]
Last edited by TISARKER on Sat Dec 31, 2005 12:12 am, edited 2 times in total.
Mr. Arithmetic logic Unit

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

### Re: 10981-(String Morphing)Need Help

Try this input:

Code: Select all

``````1
bacbabccbcaacccaacbbabacbababcbbabcbabbabcbabbabcabcabaaccabacbabccbcaacccaacbbabacbababcbbabcbabbaa
c``````
Your prgram make a step that is wrong:

Code: Select all

``````ccbaa
acaa``````
I hope it helps!

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
Could anyone talk about the idea to solve this problem? Is it DP? How?

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am
amazingly it can be solved backtracking! But of course, do a little bit of prunning
Impossible is nothing

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Contact:

### Re: 10981-(String Morphing)Need Help

ftomi wrote:Try this input:

Code: Select all

``````1
bacbabccbcaacccaacbbabacbababcbbabcbabbabcbabbabcabcabaaccabacbabccbcaacccaacbbabacbababcbbabcbabbaa
c``````
Your prgram make a step that is wrong:

Code: Select all

``````ccbaa
acaa``````
I hope it helps!
I edited my code . But again WA.
Following code is after After editing

Code: Select all

``````#include<stdio.h>
#include<string.h>
#define type long
#define range 105
char x[range][range],s[range],ch[10]="**ab*c";
type dp[range][range],prime[3]={2,3,5},len[range],ptr=0;
struct xx { type left[3],right[3]; }A,B,C;

void INI()
{
A.left[0]=2; A.right[0]=5; A.left[1]=3; A.right[1]=5; A.left[2]=5; A.right[2]=2;
B.left[0]=2; B.right[0]=2; B.left[1]=2; B.right[1]=3; B.left[2]=3; B.right[2]=3;
C.left[0]=3; C.right[0]=2; C.left[1]=5; C.right[1]=3; C.left[2]=5; C.right[2]=5;
}

void ini(type n)
{
type i,j;
for(i=0;i<n;i++)for(j=0;j<n;j++)dp[i][j]=-1;
for(i=0;i<n;i++){ x[i][n-i]=0; len[i]=0; }
}

type merge(type n1,type n2)
{
if(n1%n2==0)return n1; n1*=n2;
if(n1%4==0)n1/=2; if(n1%9==0)n1/=3; if(n1%25==0)n1/=5;
return n1;
}

type call(type n1,type n2)
{
type sum=1;
if((n1%5==0)&&(n2%2==0))sum*=2;
else if(((n1%2==0)||(n1%3==0))&&(n2%5==0))sum*=2;
if((n1%3==0)&&(n2%3==0))sum*=3;
else if((n1%2==0)&&((n2%2==0)||(n2%3==0)))sum*=3;
if((n1%3==0)&&(n2%2==0))sum*=5;
else if((n1%5==0)&&((n2%3==0)||(n2%5==0)))sum*=5;
return sum;
}

type memo(type i,type j)
{
if(dp[i][j]!=-1)return dp[i][j];
if(i==j) { dp[i][j]=prime[s[i]-97]; return dp[i][j]; }
type k,sum=1,v1,v2;
for(k=j-1;k>=i;k--)
{
v1=memo(i,k); v2=memo(k+1,j);
v1=call(v1,v2); sum=merge(sum,v1);
if(sum==30)break;
}
dp[i][j]=sum;
return dp[i][j];
}

void copy(type i1,type i2,type j,type j2,type n,type d)
{
type j1;
for(;i1<i2;i1++)
for(j1=j;j1<=j2;j1++)
{
x[i1][len[i1]]=s[j1]; len[i1]++;
}
for(i1++;n>1;n--,i1++) { x[i1][len[i1]]=ch[d]; len[i1]++; }
}

void set(type i,type j,type d,type line)
{
type k,l; xx Z;
if(i==j) { x[line][len[line]]=s[i]; len[line]++; return  ; }

if(d==2)Z=A;else if(d==3)Z=B; else if(d==5)Z=C;
for(k=j-1;k>=i;k--)for(l=0;l<3;l++)
{
if(dp[i][k]%Z.left[l]!=0)continue; if(dp[k+1][j]%Z.right[l]!=0)continue;
set(i,k,Z.left[l],line);
copy(line,line+k-i,k+1,j,j-k,Z.left[l]);
set(k+1,j,Z.right[l],line+k-i);
line+=j-i;
x[line][len[line]]=ch[d]; len[line]++;
return;
}
}

void main()
{
type i,t,len,d,sig=0;
char ch[5];
//clrscr();
//freopen("E:\\input.cpp","r",stdin);
//freopen("E:\\myput.cpp","w",stdout);
INI();
scanf("%ld",&t);
while(t>0)
{
if(sig==1)printf("\n"); sig=1;
t--; scanf("%s%s",s,ch); len=strlen(s); d=prime[ch[0]-97]; ini(len);
if(memo(0,len-1)%d!=0){ printf("None exist!\n"); continue; }
set(0,len-1,d,0);
for(i=0;i<len;i++)printf("%s\n",&x[i][0]);
}
}
``````
Mr. Arithmetic logic Unit

Rostislav
New poster
Posts: 21
Joined: Sun Oct 05, 2003 11:19 am
Location: Bulgaria, Shoumen
Contact:
TISARKER maybe you should try backtrack.
But I want to ask people who got AC, is there another way to solve this task?

Rostislav

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
I've used DP. IMO, the *real* problem is to cope with the requirement, that the leftmost pair of characters is always merged.

I couldn't get the obvious cubic algorithm to handle this. I got accepted with O(n^4) algo: for each morphing step, run the O(n^3) DP to find which pair of characters should be merged. With some opts, it gave me the first place in the ranklist!

Btw, does anybody know O(n^3) algorithm? What's the complexity of author's solution?

RuanZheng
New poster
Posts: 4
Joined: Fri Dec 30, 2005 5:16 pm
i also use DP but got many WA...
here is my code
could someone give me some tricky test data
i am nearly crazy!

Code: Select all

``````#include <iostream>
#include <cstring>
#define N 120
using namespace std;

char str[N],ans;
int s[N][N][3],from[N][N][3],l[N][N][3],r[N][N][3],n;
int table[3][3]={{1,1,0},{2,1,0},{0,2,2}};

void Divide(int left, int right, int ans)
{
if(left==right) return;

Divide(left,from[left][right][ans],l[left][right][ans]);
Divide(from[left][right][ans]+1,right,r[left][right][ans]);

int count=0,ll,lx,rr,rx;
for(int i=left;i<=right;++i)
{
if(str[i]!=' ')
{
++count;
if(count==1)
{
ll=str[i]-'a';
lx=i;
}
else if(count==2)
{
rr=str[i]-'a';
rx=i;
}
}
}

{
str[rx]=' ';
str[lx]=table[ll][rr]+'a';
for(int i=0;i<n;++i)
{
if(str[i]!=' ')
{
cout<<str[i];
}
}
cout<<endl;
return;
}

}

void Cal()
{
n=strlen(str);
if(n==1)
{
if(str[0]==ans) cout<<str<<endl;
else cout<<"None exist!"<<endl;
return;
}
for(int i=0;i<N;++i)
{
for(int j=0;j<N;++j)
{
for(int k=0;k<3;++k)
{
s[i][j][k]=0;
from[i][j][k]=0;
l[i][j][k]=r[i][j][k]=0;
}
}
}

for(int i=0;i<n;++i)
{
s[i][i][str[i]-'a']=1;
}

for(int len=2;len<=n;++len)
{
for(int i=0;i+len-1<n;++i)
{
int j=i+len-1;
for(int k=j-1;k>=i;--k)
{
for(int l1=0;l1<3;++l1)
{
for(int l2=0;l2<3;++l2)
{
if(s[i][k][l1]&&s[k+1][j][l2])
{
int ans=table[l1][l2];
if(s[i][j][ans]==0)
{
s[i][j][ans]=1;
from[i][j][ans]=k;
l[i][j][ans]=l1;
r[i][j][ans]=l2;
}
}
}
}
}
}
}
if(s[0][n-1][ans-'a']==0)
{
cout<<"None exist!"<<endl;
return;
}
cout<<str<<endl;
Divide(0,n-1,ans-'a');
}

int main()
{
int NumOfCase;
cin>>NumOfCase;
while(NumOfCase--)
{
cin>>str>>ans;
Cal();
if(NumOfCase)
{
cout<<endl;
}
}
return 0;
}

``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Here's a few tests.

Code: Select all

``````5
baaac
a
bbbaa
b
abcaa
b
aacab
c
ababc
b
``````
Output:

Code: Select all

``````baaac
caac
aac
bc
a

bbbaa
bbaa
baa
bb
b

abcaa
bcaa
aaa
ab
b

aacab
bcab
bab
cb
c

ababc
babc
baa
bb
b
``````

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
I also used the O(n^4) algorithm by mf and got accepted. I found that bottom-up DP is rather slow for the problem. Top-down DP works better.

RuanZheng
New poster
Posts: 4
Joined: Fri Dec 30, 2005 5:16 pm
thank you very much!
i know why i wrong

rayc
New poster
Posts: 2
Joined: Thu Dec 29, 2005 11:16 am
Location: Hong Kong
mf wrote:I've used DP. IMO, the *real* problem is to cope with the requirement, that the leftmost pair of characters is always merged.

I couldn't get the obvious cubic algorithm to handle this. I got accepted with O(n^4) algo: for each morphing step, run the O(n^3) DP to find which pair of characters should be merged. With some opts, it gave me the first place in the ranklist!

Btw, does anybody know O(n^3) algorithm? What's the complexity of author's solution?
tobby wrote:I also used the O(n^4) algorithm by mf and got accepted. I found that bottom-up DP is rather slow for the problem. Top-down DP works better.
The author's solution is exactly what you r doing
a top-down DP with O(n^4) complexity

I wonder (and actually one of my friends too) there should be a O(n^3) solution. The timelimit, even during contest time, should accept O(n^4) top-down DP solutions (not sure if bottom-up works as well).

Hope these helps

(Thanks my friend for suggesting the top-down approach when I was designing this task)

Raymond

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
I think there is an O(n^3) algorithm. (mine) But at the moment it has some bugs. And now it's TLE. (but it's definilty O(n^3). To be more precise O(m^3*n^3) where m is the number of different letters in the alphabet that is == 3)

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
It seems my algorithm can't be fixed.

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan
I used a n^4 dp but got tle
I think it must has to be speed up
but i can't

here's my code:

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char dp[301][301][3];
int dp1[301][301][3];
int s[3][3]={{1,1,0},{2,1,0},{0,2,2}};
char asd[301];
char zxc[301];
int qq,tt;
inline bool check(int l,int r,int t)
{
if(dp[l][r][t]!=2)
return dp[l][r][t];
int i,j,k;
if(l==r)
{
if(asd[l]-97==t)
dp[l][r][t]=1;
else
dp[l][r][t]=0;
return dp[l][r][t];
}
dp[l][r][t]=0;
dp1[l][r][t]=2147483647;
for(i=l+1;i<=r;i++)
{
for(j=0;j<3;j++)
{
if(check(l,i-1,j)==0)
continue;
for(k=0;k<3;k++)
{
if(s[j][k]!=t)
continue;
if(check(i,r,k)==1)
{
dp[l][r][t]=1;
dp1[l][r][t]=dp1[i][r][k];
if(dp1[l][r][t]>dp1[l][i-1][j])
dp1[l][r][t]=dp1[l][i-1][j];
}
}
}
}
if(r==l+1 && dp[l][r][t]==1)
dp1[l][r][t]=l;
return dp[l][r][t];
}
int main()
{
int ttt;
int n,i,j,k;
int lon;
char qwe;
scanf("%d",&ttt);
for(;ttt>0;ttt--)
{
cin>>asd>>qwe;
lon=strlen(asd);
for(i=0;i<lon;i++)
for(j=0;j<lon;j++)
for(k=0;k<3;k++)
dp[i][j][k]=2;
if(check(0,lon-1,qwe-97)==0)
{
printf("None exist!\n");
goto aa;
}
printf("%s\n",asd);
for(n=1;n<lon;n++)
{
for(i=0;i<=lon-n;i++)
{
for(j=0;j<=lon-n;j++)
{
for(k=0;k<3;k++)
{
dp[i][j][k]=2;
dp1[i][j][k]=2147483647;
}
}
}
qq=200;
check(0,lon-n,qwe-97);
qq=dp1[0][lon-n][qwe-97];
tt=s[asd[qq]-97][asd[qq+1]-97];
asd[qq]=tt+97;
for(i=qq+1;i<lon-n;i++)
asd[i]=asd[i+1];
asd[lon-n]='\0';
printf("%s\n",asd);
}
aa:     if(ttt>1)
printf("\n");
}
return 0;
}
``````
hoping sb give me some suggestion
sorry for my bad coding style