I checked my program but found no big mistakes. Could anyone come into help?
#include <fstream.h>
#include <string.h>

#define fin cin

bool flag[65536];
char u[20],v[20],w[20],z[20];
int tar,lz,lw;

int str2int(char *s,int len)
{
int i,ans(1);
for (i=0;i<len;i++)
if (s=='a')
ans = ans<<1;
else
ans = (ans<<1)+1;
return ans;
}

void dfs(int state,int len)
{
char ww[300]="";
if (flag[state]) return;
flag[state] = true;
if (flag[tar]) return;

int i,l;
for (i=1;i<=len;i++)
if (state&(1<<(len-i)))
strcat(ww,v);
else
strcat(ww,u);
l = strlen(ww);
if (l<=lz)
dfs(str2int(ww,l),l);
else
for (i=0;i<=l-lz;i++)
dfs(str2int(ww+i,lz),lz);
}

void crash()
{
int *p = 0;
*p = 0;
}

int main()
{
int i;
for (;;) {
fin.getline(u,20);
fin.getline(v,20);
fin.getline(w,20);
fin.getline(z,20);
if (fin.fail()) break;

memset(flag,0,sizeof(flag));
lw = strlen(w);
lz = strlen(z);
tar = str2int(z,strlen(z));

if (lw<=lz)
dfs(str2int(w,lw),lw);
else
for (i=0;i<=lw-lz;i++)
dfs(str2int(w+i,lz),lz);
if (flag[tar])
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}

Try:
aabaabaaaaab
babaaa
abababab
bbbbb
Your answer is NO, judge is YES. If you change 4 times the letter 'a', you get a huge word. The las 5 characters on that word are "bbbbb".
Anyway, judge's output was wrong, we've changed it tonight, we're rejudging all submissions...
Carlos.

But I couldn't agree with you.
I read the problem carefully, I think you must change all the letter in every step. ("Direct derivation from string u1 to u2 consists of replacing each occurrence of the symbol x in u1 by the string on the right side of the production for that symbol. ")
I got some materials about L-System, which support my opionion.

So you must change 'a' and 'b' at the same time.
so the answer is NO

Hello,
i've got a problem with this task too.
this is my alghoritm:
the maximal word length is the length of the sequence, which we have to find in all D0L words. If i add new word to a queue, and it's longer than maximal length, i add word consisting of m (m=maximal length) first characters of this word, than m characters starting from second and so on. Every entry in the queue has two values : the length of the word (becouse starting word may be shorter than m) and the word. In other array of booleans i check every word, if it occurs - as before, i use two values - length and word (interpreted as binary number), and i check it in 2 dimensional array. And i use BFS to find all the words. Here's my program:
[pascal]
const
max=70000;
mot:array[0..16]of longint=(1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536);
var
h,t,v,l,q,d1,d2,d,ds,a,dl,b,spr :longint;
cg1,cg2,cg,cgs :array[0..20]of char;
xxx :array[0..300]of boolean;
czy :array[0..max,0..15]of boolean;
kol :array[0..max] of record
d:longint;
c:array[0..15]of boolean
end;
zam1,zam2 :array[0..15]of boolean;

procedure add(dlug:longint);
begin
if ds<dlug then
begin
l:=0;
for v:=1 to ds-1 do
if xxx[v] then
l:=l shl 1+1
else
l:=l shl 1;
for v:=ds to dlug do
begin
if xxx[v] then
l:=(l shl 1+1) mod mot[ds]
else
l:=(l shl 1) mod mot[ds];
if not czy[l,ds] then
begin
czy[l,ds]:=true;
t:=t+1;
kol[t].d:=ds;
for q:=1 to ds do
kol[t].c[q]:=xxx[v-ds+q]
end
end
end
else
begin
l:=0;
for v:=1 to dlug do
if xxx[v] then
l:=l shl 1+1
else
l:=l shl 1;
if not czy[l,dlug] then
begin
czy[l,dlug]:=true;
t:=t+1;
kol[t].d:=dlug;
for q:=1 to dlug do
kol[t].c[q]:=xxx[q]
end
end
end;

begin

while (not eof) and (not eoln) do
begin
d1:=0;
while not eoln do
begin
d1:=d1+1;
read(cg1[d1])
end;
readln;
d2:=0;
while not eoln do
begin
d2:=d2+1;
read(cg2[d2])
end;
readln;
d:=0;
while not eoln do
begin
d:=d+1;
read(cg[d])
end;
readln;
ds:=0;
while not eoln do
begin
ds:=ds+1;
read(cgs[ds])
end;
readln;

for a:=1 to d1 do
case cg1[a] of
'a':zam1[a]:=true;
'b':zam1[a]:=false
end;
for a:=1 to d2 do
case cg2[a] of
'a':zam2[a]:=true;
'b':zam2[a]:=false
end;

h:=1;
t:=0;

for a:=0 to max do
for b:=0 to 15 do
czy[a,b]:=false;

for a:=1 to d do
case cg[a] of
'a':xxx[a]:=true;
'b':xxx[a]:=false
end;
add(d);

while h<=t do
begin
dl:=0;
for a:=1 to kol[h].d do
if kol[h].c[a] then
for b:=1 to d1 do
begin
dl:=dl+1;
xxx[dl]:=zam1
end
else
begin
dl:=dl+1;
xxx[dl]:=kol[h].c[a]
end;
add(dl);

dl:=0;
for a:=1 to kol[h].d do
if not kol[h].c[a] then
for b:=1 to d2 do
begin
dl:=dl+1;
xxx[dl]:=zam2
end
else
begin
dl:=dl+1;
xxx[dl]:=kol[h].c[a]
end;
add(dl);
h:=h+1
end;

for a:=1 to ds do
case cgs[a] of
'a':xxx[a]:=true;
'b':xxx[a]:=false
end;
spr:=0;
for a:=1 to ds do
if xxx[a] then
spr:=spr shl 1+1
else
spr:=spr shl 1;
if czy[spr,ds] then
writeln('YES')
else
writeln('NO')
end;
end.
[/pascal]
I would be thankful for every help. Best regards,
FilipEK

I've tried solving this question a few different ways and all of them failed.

The obvious brute force way (take the start string and then do a permutation of different mappings) took too long and required too much memory.

Then I tried the reverse mapping from z to w and that seems to work for all my test cases, but the judge gave me WA.

Can someone please tell me if there are any special cases/notes I should keep an eye out for?

Things I've already taken note of:
1) After all the reverse mappings, z' may not be w. As long as z' is a subset of w, then it is an answer.
2) Every occurance of a mapped character has to be reverse mapped.

eg:

A = BBB
B = AAA
Z = AAAABBB

cannot be mapped to:

BABBB (mapping first 3 A's to B)
or
ABBBB (mapping last 3 A's to B)

because the last 3 B's have to be revseed mapped as well

I've also found some sample test data.. can someone with an AC program please run the data through their program and tell me their results? Thanks!

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.

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.

Thanks for your help.. but just another quick question..

Is my algorithm even correct? Or do I really have to use the brute force (with pruning of course) method of using the starting string and doing the mappings until I find (or don't find) the answer?

And if I use the brute force method, how would I know when to stop mapping?

I did it the other way around. That is, I started with the target string and try to apply the rules backwards (backtracking as necessary) until I reach the starting string. (I think this is how your second approach worked, or did I misunderstand it?)

It seems pretty fast, I'm still in the top 10 despite somewhat bad coding.

One thing you may or may not have noticed (I for one don't think it is completely obvious from the statement): when we apply one of the two rules, we apply it to every occurance of 'a'/'b' at once. I.e. if we have

A -> BAB
B -> ABA
Z = ABAB

it can be transformed into BABBBABB using the a-rule, or AABAAABA using the b-rule, but not, for instance, BABBAB.

Per wrote:I did it the other way around. That is, I started with the target string and try to apply the rules backwards (backtracking as necessary) until I reach the starting string. (I think this is how your second approach worked, or did I misunderstand it?)

It seems pretty fast, I'm still in the top 10 despite somewhat bad coding.

One thing you may or may not have noticed (I for one don't think it is completely obvious from the statement): when we apply one of the two rules, we apply it to every occurance of 'a'/'b' at once. I.e. if we have

A -> BAB
B -> ABA
Z = ABAB

it can be transformed into BABBBABB using the a-rule, or AABAAABA using the b-rule, but not, for instance, BABBAB.

What is exactly what I did.. however, for some reasons, my code gets the wrong answer for some test cases. :p

Just a quick confirmation:

a = aaaaab
b = bbbba
w = aba
target = aaab

Starting from the target, we have aaab

doing a reverse map of a once,

we simply get

a

and since a is a subset of w, we can conclude that the answer is YES. Is this more or less correct?

There is no way to produce 'a' starting from 'a', because the language consists of only one string: 'b'. The answer should be NO, but the judge want's us to produce YES.

I think the problem text should be adjusted. This might sound like academic hair cleaving, but there are enough problems in the set where that attitude is the only way to get AC.

There is no way to produce 'a' starting from 'a', because the language consists of only one string: 'b'. The answer should be NO, but the judge want's us to produce YES.

I think the problem text should be adjusted. This might sound like academic hair cleaving, but there are enough problems in the set where that attitude is the only way to get AC.

I assume you used the reverse mapping method Per and I discussed... can I check with you:

Just a quick confirmation:

a = aaaaab
b = bbbba
w = aba
target = aaab

Starting from the target, we have aaab

doing a reverse map of a once,

we simply get

a

So.. if after all the reverse mapping we get a subset of the original starting string, is this a YES?

Of course, doing the reverse mapping from aaab, we also get aaab again (since aaab -> aaabbbba by the b mapping), but that's not very interesting since we've already seen it.

little joey wrote:Thanks guys, I finaly got accepted after having only WAs more than a year ago. But I think it's based on the wrong grounds.

The language of the D0L system consists of all strings which can be derived from the starting string w by a sequence of the direct derivations.

And nowhere in the text it is stated that the starting string also belongs to the language!

Well, that depends if you consider the empty sequence a sequence or not.
I think that by standard mathematical practice, the empty sequence should be considered a sequence.