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

DailyByte
New poster
Posts: 4
Joined: Sat Jul 20, 2002 12:54 pm

310 L-system I got WA for so many times!

Post by DailyByte » Thu Aug 22, 2002 11:37 am

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

User avatar
Carlos
System administrator
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Location: Valladolid, Spain
Contact:

Judge's

Post by Carlos » Fri Aug 23, 2002 12:04 am

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.

DailyByte
New poster
Posts: 4
Joined: Sat Jul 20, 2002 12:54 pm

Post by DailyByte » Fri Aug 23, 2002 6:12 pm

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

User avatar
filipek
New poster
Posts: 9
Joined: Sat Jun 22, 2002 12:16 pm
Location: Poland
Contact:

Post by filipek » Fri Dec 13, 2002 7:50 pm

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

Pedrinho UFPE
New poster
Posts: 15
Joined: Tue Sep 10, 2002 1:56 am
Location: Brasil
Contact:

What's the correct meaning of this problem?

Post by Pedrinho UFPE » Sat Jun 21, 2003 5:53 am

Do we must to change all the letters every step, or no?
Please.. I cant get Accepted.
I've done what DailyBite've done.. are we correct?

Thank you VERY much!
Interested

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

310 - L--system

Post by junbin » Sat Jan 24, 2004 5:53 am

Hi!

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!


Sample data:

Code: Select all

aabaabaaaaab
babaaa
abababab
bbbbb
babaabaabaaabaa
bbbbabbaaaabab
abbaabbb
aaaaba
baabbbbaabaaaaa
aabbababbbaaa
b
abb
bbaa
babbbaaaabb
abaababba
ba
babaaab
abbbaaaaabbb
bbabbbbbbbba
bbbbbabbaaa
a
baaba
ab
bbbbababbbbbb
babbbbaab
bababb
bbabaababbab
baababbb
ab
bbabbbaaaabaaba
aabbbabaaaaabba
bbbaaabbabab
b
bbbbbabba
abaaaababa
aaababab
abaababbaabaaab
abbaabb
aabbb
aabbb
abbabbbabb
aabbbbbab
abaaabaa
ab
aaababbb
aabaaaa
aaaabb
aaaaba
baabbbbbbaaaba
aaa
abaabb
aaabbaa
abaab
bb
baa
bbbabaabab
aaaaaabba
ba
baa
bbaababb
abbaaaabbbaabb
bbaaabbbbaab
abaabbbaaaabaa
babbaaaaaaa
bbaaaabbababbba
bbabbab
b
baaabbaaa
baaabbababbaaa
ababbaaaa
aabbbabab
aabab
aaabbbbaa
ababbb
bba
bbbabaaaa



Sample output:

Code: Select all

YES
YES
YES
YES
NO
NO
NO
NO
NO
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Sat Jan 24, 2004 9:24 pm

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.

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

Post by junbin » Mon Jan 26, 2004 3:21 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.
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?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Jan 26, 2004 9:29 am

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.

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

Post by junbin » Mon Jan 26, 2004 9:41 am

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?

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

Post by little joey » Mon Jan 26, 2004 2:40 pm

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!

So, in my interpretation, junbin's 10th case should produce NO (as my WA program did) in stead of YES (as my AC program does).

A more simple case:

Code: Select all

b
b
a
a
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.

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

Post by junbin » Mon Jan 26, 2004 3:45 pm

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!

So, in my interpretation, junbin's 10th case should produce NO (as my WA program did) in stead of YES (as my AC program does).

A more simple case:

Code: Select all

b
b
a
a
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?

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

Post by little joey » Mon Jan 26, 2004 4:20 pm

junbin wrote:I assume you used the reverse mapping method Per and I discussed... can I check with you:
No, I use the forward method, so I guess Per can better explain it.

In the forward method w='aba' -> 'aaaaab'+'bbbba'+'aaaaab' of which 'aaab' is a substring, quite simple.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Jan 26, 2004 6:44 pm

junbin: yes, more or less correct. :)

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.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Jan 26, 2004 6:50 pm

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.

Post Reply

Return to “Volume 3 (300-399)”