310 - L--system

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Jan 26, 2004 7:35 pm

You got me there, never thought of it that way :)

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

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Tue Jan 27, 2004 7:14 am

Per wrote: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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Tue Jan 27, 2004 8:47 am

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
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Tue Jan 27, 2004 3:54 pm

Per wrote: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
New poster
Posts: 3
Joined: Mon Jan 15, 2007 6:02 pm

problem 310

Post by jerda » Mon Jan 15, 2007 6:45 pm

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
New poster
Posts: 3
Joined: Mon Jan 15, 2007 6:02 pm

Post by jerda » Tue Jan 16, 2007 5:27 pm

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Jan 16, 2007 5:47 pm

Search for past discussions of this problem:
Per wrote: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
New poster
Posts: 3
Joined: Mon Jan 15, 2007 6:02 pm

Post by jerda » Tue Jan 16, 2007 10:03 pm

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Jan 16, 2007 10:54 pm

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
New poster
Posts: 7
Joined: Tue Apr 17, 2007 1:18 am
Location: Egypt
Contact:

Post by wahab » Tue Apr 17, 2007 1:38 am

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Apr 17, 2007 1:55 am

wahab wrote: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
New poster
Posts: 7
Joined: Tue Apr 17, 2007 1:18 am
Location: Egypt
Contact:

Post by wahab » Tue Apr 17, 2007 2:06 am

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Jul 09, 2007 8:40 am

The stopping conditions are similar to something like dfs.

free
New poster
Posts: 6
Joined: Fri Aug 13, 2010 8:35 am
Location: China

problem 310, i got TLE

Post by free » Tue Sep 28, 2010 2:43 pm

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
New poster
Posts: 1
Joined: Tue Jan 21, 2014 2:34 pm

Re: problem 310

Post by sofiazoe » Tue Jan 21, 2014 2:43 pm

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. ................. :)
Our HP2-E31 design tutorials offers easy to follow program to help you learn how to create elegant website designs. Download the 100-101 dumps guide and 1z0-054 tutorial to get inspiration for your web project.and more visit HP Good Luck.

Post Reply

Return to “Volume 3 (300-399)”