## 10981 - String Morphing

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
This is how I'm doing it:

Code: Select all

``````/*
*  which() -- determines the leftmost pair of characters, which can be
*  multiplied, such that the character 'dst' still can be obtained from
*  the resulting string.
*
*  Returns the offset of the first character in the pair, or -1 if
*  the character 'dst' can't be obtained from the initial string.
*/
int which(int src[], int n, int dst)
{
int can[16][16][4], first[16][16][4];

/*
*  can[offs][len][chr] = can the substring src[offs .. offs+len-1] be
*  morphed to character chr?
*
*  If so, then first[offs][len][chr] = the smallest possible offset, at
*  which the first multiplication may occur.
*/

for (int i = 0; i < n; i++)
for (int j = 0; j < 3; j++)
can[i][1][j] = (j == src[i]);

first[0][n][dst] = -1;
for (int offs = n - 1; offs >= 0; offs--)
for (int len = 2; offs + len <= n; len++) {
for (int c = 0; c < 3; c++)
can[offs][len][c] = 0;

for (int k=1;k<len;k++) for(int c1=0;c1<3;c1++) for(int c2=0;c2<3;c2++) {
if (!can[offs][k][c1] || !can[offs+k][len-k][c2])
continue;

int f, c = mul[c1][c2];
if (k > 1)
f = first[offs][k][c1];
else if (len - k > 1)
f = first[offs+k][len-k][c2];
else
f = offs;

if (!can[offs][len][c] || f < first[offs][len][c]) {
can[offs][len][c] = 1;
first[offs][len][c] = f;
}
}
}

return first[0][n][dst];
}
``````

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
this N^4 code makes TLE. i think this looks same as mf's code (the function part)

Code: Select all

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

int array[200],target;
int ok[200][200][3];
int p[200][200][3];
int mul[5][5];

int POSSIBLE(int sz)
{
int i,j,c,c1,c2,len,k,first;

for(i=0;i<sz;i++)
for(j=0;j<3;j++)
ok[i][i][j]=(array[i]==j);

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

ok[i][j][0]=ok[i][j][1]=ok[i][j][2]=0;

for(k=i;k<j;k++)
for(c1=0;c1<3;c1++) if(ok[i][k][c1])
for(c2=0;c2<3;c2++) if(ok[k+1][j][c2])
{
c=mul[c1][c2];

if(k-i+1>1)
first=p[i][k][c1];
else if(j-k>1)
first=p[k+1][j][c2];
else
first=i;

if(ok[i][j][c]==0 || p[i][j][c]>first)
{
p[i][j][c]=first;
ok[i][j][c]=1;
}

}
}

if(ok[0][sz-1][target]==0) return -1;
return p[0][sz-1][target];
}

int main()
{
int ks,n,i,x,now,j;
char word[300];
char yy[10];

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;

scanf("%d",&ks);

while(ks--)
{
scanf("%s%s",word,yy);
n=strlen(word);
target=yy[0]-'a';

for(i=0;i<n;i++) array[i]=word[i]-'a';

x=POSSIBLE(n);

if(x==-1)
{
printf("None exist!\n");
if(ks) printf("\n");
continue;
}

printf("%s\n",word);

now=n;
for(i=2;i<=n;i++)
{
now--;
array[x]=mul[array[x]][array[x+1]];
word[x]=array[x]+'a';
for(j=x+1;j<now;j++)
{
array[j]=array[j+1];
word[j]=array[j]+'a';
}

word[j]=0;

printf("%s\n",word);

x=POSSIBLE(now);
}

if(ks) printf("\n");

}

return 0;
}
``````
Self judging is the best judging!