10981 - String Morphing

TISARKER · Post by **TISARKER** » Fri Dec 30, 2005 7:29 am

Can anyone tell me why am I getting WA?

Delete Code

Please give me some tricky input and output.[/code]

ftomi · Post by **ftomi** » Fri Dec 30, 2005 3:20 pm

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 · Post by **tobby** » Fri Dec 30, 2005 4:22 pm

Could anyone talk about the idea to solve this problem? Is it DP? How?

tywok · Post by **tywok** » Fri Dec 30, 2005 8:30 pm

amazingly it can be solved backtracking! But of course, do a little bit of prunning

TISARKER · Post by **TISARKER** » Sat Dec 31, 2005 12:04 am

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

Rostislav · Post by **Rostislav** » Sat Dec 31, 2005 4:27 am

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 · Post by mf » Sat Dec 31, 2005 5:10 am

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 · Post by **RuanZheng** » Sat Dec 31, 2005 5:27 am

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 · Post by mf » Sat Dec 31, 2005 6:11 am

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 · Post by **tobby** » Sat Dec 31, 2005 6:22 am

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 · Post by **RuanZheng** » Sat Dec 31, 2005 7:17 am

thank you very much!
i know why i wrong

rayc · Post by **rayc** » Sat Dec 31, 2005 11:54 am

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 · Post by **ftomi** » Sat Dec 31, 2005 12:17 pm

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 · Post by **ftomi** » Sat Dec 31, 2005 2:18 pm

It seems my algorithm can't be fixed.

polone · Post by **polone** » Sun Jan 01, 2006 4:42 pm

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

OJ Board

10981 - String Morphing

10981 - String Morphing

Re: 10981-(String Morphing)Need Help

Re: 10981-(String Morphing)Need Help