310 - L--system

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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

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

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
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
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

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
I see the old post but i don't find the condition to stop the algoritmic

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

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

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.