310  Lsystem
Moderator: Board moderators

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Sorry to bother you again..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 brule once.
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?
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 arule and the brule 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.
The thing I thought not completely obvious from the problem statement (that I had forgotten) is that you apply both the arule and the brule 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.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 arule and the brule 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.
Anyway, I redid my code and got AC.
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
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
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.
My problem is search one condition to stop the tree, because if the algoritmic never find the string it's loop;
Thanks
jerda
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 arule and the brule at the same time
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).
Don't ask me to help you with stopping conditions. I've solved this problem quite differently (sort of KMP + dynamic programming).
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
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
My accepted program says "YES".wahab wrote:Can anyone tell what is the correct output for this problem for the following input:
baabbbbaabaaaaa
aabbababbbaaa
b
abb
That's not this judge's solution. It gets WA.but according to the judge solution in this link it is problem c it get
NO
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
Thanks again
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.
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<<(len1i));
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_len1;i++) if (goal[i]=='a') xxx=xxx+(1<<(goal_len1i));
if (strstr(st[1],goal)!=NULL) printf("YES\n");
else
{
fill(vis,false);
try_to_insert(st[1]);
bfs();
}
}
return 0;
}
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 HP2E31 design tutorials offers easy to follow program to help you learn how to create elegant website designs. Download the 100101 dumps guide and 1z0054 tutorial to get inspiration for your web project.and more visit HP Good Luck.