310 - L--system

[little joey]

You got me there, never thought of it that way

Wished all problems would confirm to standard mathematical practice the way this problem does

[junbin]

There are four errors. The answer for the first case is "NO", the answer for the last YES should be NO, the answer for the second and sixth from the end should be YES.

For instance, for the second last case:
a -> baaabbababbaaa
b -> ababbaaaa

with starting string aabbbabab, we can get to aabab by just applying the b-rule once.

Sorry to bother you again..

Can you explain to me why for the first case the answer is NO?


aabaabaaaaab
babaaa
abababab
bbbbb


If I use the forward mapping method:

Consider the start string:
abababab

We just consider the last 2 letters: ab

these will map to

aabaabaaaaabb

Then we consider the last 3 letters: abb

these will map to

aabaabaaaaabbb

and so on.

After 4 mappings, the last few characters will be:

aabaabaaaaabbbbb

And clearly, the last 5 letters are the target (z) string "bbbbb".


If we consider the forward mapping,

we start with the target string : bbbbb

this can be revsered mapped to: abbbb

which can then be mapped to: abbb
and then to: abb
and finally to: ab

Since ab is a subset of the start string "abababab", therefore, this is a solution.

Either way, the answer should be "YES".

Am I correct or did I understand the question wrongly?

[Per]

Ah! Now (after having spent 20 minutes patching what I thought was a bug in my solution) I remember! I'm sorry to say that I have (unwillingly) tricked you.

The thing I thought not completely obvious from the problem statement (that I had forgotten) is that you apply both the a-rule and the b-rule at the same time. Thus, for your last example, we get

aba... -> aabaabaaaaabbabaaaaabaabaaaaab...

and so on, which never leads to more than two consecutive b's (since we must apply the rules to every character of the string). Or doing the reverse mapping, there simply is no way to get to bbbbb with the rules given.

[junbin]

Ah! Now (after having spent 20 minutes patching what I thought was a bug in my solution) I remember! I'm sorry to say that I have (unwillingly) tricked you.

The thing I thought not completely obvious from the problem statement (that I had forgotten) is that you apply both the a-rule and the b-rule at the same time. Thus, for your last example, we get

aba... -> aabaabaaaaabbabaaaaabaabaaaaab...

and so on, which never leads to more than two consecutive b's (since we must apply the rules to every character of the string). Or doing the reverse mapping, there simply is no way to get to bbbbb with the rules given.

Thank you so very much for your help! With that simple little line, I realised that my understanding of the problem was completely wrong.

Anyway, I redid my code and got AC.

[jerda]

Hi!
I try to solved problem number 310. I'm using binary tree. I'm proceding in this way:

a -> aa
b -> bb
W = ab
Z = aaabb

Code: Select all

                                          ab
                                        /     \
                                 aab        abb
                                 /    \            /    \
                    aaaab   aabb   aabb  abbbb
ecc ecc.

I derive at right simbols b and at left simbols a.
My problem is search one condition to stop the tree, because if the algoritmic never find the string it's loop;
Thanks
jerda

[jerda]

Please help me !!!!!!!!!!

[mf]

Search for past discussions of this problem:

The thing I thought not completely obvious from the problem statement [...] is that you apply both the a-rule and the b-rule at the same time

[jerda]

I see the old post but i don't find the condition to stop the algoritmic
please help me!!!

[mf]

Well, I think that the quoted text shows that your whole binary tree thing doesn't correspond to the correct interpretation of the problem. You don't get to choose whether to expand just a's or just b's at each step -- you expand every letter.

Don't ask me to help you with stopping conditions. I've solved this problem quite differently (sort of KMP + dynamic programming).

[wahab]

Can anyone tell what is the correct output for this problem for the following input:


baabbbbaabaaaaa
aabbababbbaaa
b
abb

according to what is written in this thread

a --> baabbbbaabaaaaa
b --> aabbababbbaaa
start --> b
z --> aab



so starting with


b


and applying one Direct derivation


b --> aabbababbbaaa


we get


aabbababbbaaa


and since

abb

is a substring of the current string then the output should be


YES



but according to the judge solution in this link it is problem c it get

NO

i think the judge start from the goal and use DP it go back to the start string but i dont know why it get

NO

in that test case but i think that there is something missing in the problem text

[mf]

Can anyone tell what is the correct output for this problem for the following input:

baabbbbaabaaaaa
aabbababbbaaa
b
abb

My accepted program says "YES".

but according to the judge solution in this link it is problem c it get
NO

That's not this judge's solution. It gets WA.

[wahab]

i got this solution from the ACM problem set archive http://www.acm.inf.ethz.ch/ProblemSetArchive.html and i thought that i did not understand the problem statement correctly anyway thank you maybe there was a problem in the judge solution in the contest itself and they corrected here.

Thanks again

[sclo]

The stopping conditions are similar to something like dfs.

[free]

hi, i use BFS to solve this problem. since the max length is not longer than 15, than we can record all the states, also, we must record the length of the string,(because the w string may be shorter than the goal string).
In this way, i use vis[maxstate][15+2],(maxstate=70000).
But i always get TLE, i am puzzing. Could someone tell me how to faster my code with BFS.

Code: Select all

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
#define sqr(x) ((x) * (x))
#define abs(x) ((x) > 0 ? (x) : -(x))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define fill(x, y) memset((x), (y), sizeof(x))
#define PI 3.141592653589793238463

const int maxlen=30;
const int maxhash=70000;
const int maxstate=70000;
char u[maxlen], v[maxlen], goal[maxlen];
char st[maxstate][maxlen];
int goal_len, xxx;

bool vis[16][maxstate];
int hash(char *buf)
{
    int val=0;
    int len=strlen(buf);
    for (int i=0;i<=strlen(buf)-1;i++) if (buf[i]=='a') val=val+(1<<(len-1-i));
    return val;
}

bool try_to_insert(char *buf)
{
    int h=hash(buf);
    int len=strlen(buf);
    if (vis[len][h]) return false;
    vis[len][h]=true;
    return true;
}

void bfs()
{
    int front=1, rear=1;
    while (front <= rear)
    {
        char tmp[maxlen]="\0";
        strcpy(tmp,st[front]);
        for (int i=0;i<=strlen(tmp)-1;i++) 
            if (tmp[i]=='a')
            {
                char buf[maxlen]="\0";
                strncpy(buf,tmp,i);
                strcat(buf,u);
                strcat(buf,tmp+i+1);
//                if (strstr(buf,goal)!=NULL) { printf("YES\n"); return; }
                if (strlen(buf)<=goal_len)
                {
                    if (try_to_insert(buf))
                    {
                        rear++;
                        strcpy(st[rear],buf);
                        if (vis[goal_len][xxx]) { printf("YES\n"); return; }
                    }
                }
                else 
                {
                    for (int j=0;j<=strlen(buf)-goal_len;j++)
                    {
                        char buf2[maxlen]="\0";
                        strncpy(buf2,buf+j,goal_len);
                        if (try_to_insert(buf2))
                        {
                            rear++;
                            strcpy(st[rear],buf2);
                            if (vis[goal_len][xxx]) { printf("YES\n"); return; }
                        }
                    }
                }
            }
            else if (tmp[i]=='b')
            {
                char buf[maxlen]="\0";
                strncpy(buf,tmp,i);
                strcat(buf,v);
                strcat(buf,tmp+i+1);
//                if (strstr(buf,goal)!=NULL) { printf("YES\n"); return; }
                if (strlen(buf)<=goal_len)
                {
                    if (try_to_insert(buf))
                    {
                        rear++;
                        strcpy(st[rear],buf);
                        if (vis[goal_len][xxx]) { printf("YES\n"); return; }
                    }
                }
                else 
                {
                    for (int j=0;j<=strlen(buf)-goal_len;j++)
                    {
                        char buf2[maxlen]="\0";
                        strncpy(buf2,buf+j,goal_len);
                        if (try_to_insert(buf2))
                        {
                            rear++;
                            strcpy(st[rear],buf2);
                            if (vis[goal_len][xxx]) { printf("YES\n"); return; }
                        }
                    }
                }
            }
        front++;
    }
//    if (vis[goal_len][xxx]) printf("YES\n");
//    else printf("NO\n");
    printf("rear=%d\n",rear);
    printf("NO\n");
}

int main()
{
    freopen("yy2.in","r",stdin);
    freopen("yy.out","w",stdout);
    while (gets(u)!=NULL)    
    {
        gets(v); gets(st[1]); gets(goal);
        goal_len=strlen(goal);
        xxx=0;
        for (int i=0;i<=goal_len-1;i++) if (goal[i]=='a') xxx=xxx+(1<<(goal_len-1-i));
        if (strstr(st[1],goal)!=NULL) printf("YES\n");
        else
        {
            fill(vis,false);
            try_to_insert(st[1]);
            bfs();
        }
    }
    return 0;
}

[sofiazoe]

I used BFS to solve this.But its givin WA. I don't know why. I've tried lots of input (including loops,disconnected network). All is correct. But Still having WA. Plz some one help. .................