10441  Catenyms
Moderator: Board moderators
10441  Catenyms
any Superman can certify this problem is that format?
pls, give me some hint ! !
thanx in advance
WanBa
pls, give me some hint ! !
thanx in advance
WanBa
destiny conditioned by past

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am
10441  Eulerian path  easy, but lexicographically not...
Can somebody help me with 10441? It's very easy to build Eulerian path,
but it isn't so easy to build the first one lexicographically...
but it isn't so easy to build the first one lexicographically...
A small hint:
It can be done exactly the same way as usual Eulerian path. You just have to be careful about:
1) How you choose among the edges going out from a node.
2) Where in the partial path you insert cycles.
Now, how should you do these two things so that in every step, the partial path you've built is always the lexicographically smallest?
It can be done exactly the same way as usual Eulerian path. You just have to be careful about:
1) How you choose among the edges going out from a node.
2) Where in the partial path you insert cycles.
Now, how should you do these two things so that in every step, the partial path you've built is always the lexicographically smallest?

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am
Can you?
Can you give a bit bigger hint?
By the way, a simple sorting doen't fit for some reasons...
By the way, a simple sorting doen't fit for some reasons...
Ok, an example. Consider the graph consisiting of four nodes and the five edges
The Eulerian path must begin at node 1. We will first choose the edge 1>2 since it's the only edge from 1, but when we're at node 2, we have two choices. Since we want the lexicographically smallest path, we naturally choose the lexicographically smallest edge, i.e. the one labelled A. Same thing from 3, so that we now have a path 1A2A3A4 and are at a dead end.
We then start finding cycles to add to the path. Since any cycle we add is bound to be lexicographically greater than what we already have, we should traverse the partial path backwards and add cycles. So we begin with 4, from which no cycle can be added. We then reach 3, which has outgoing nodes left. We there find the cycle 3B2B3 and add it to our path, so that we have 1A2A3B2B3A4 which is the answer.
Hope this helps.
Code: Select all
from to label
1 2 A
2 3 A
3 4 A
3 2 B
2 3 B
We then start finding cycles to add to the path. Since any cycle we add is bound to be lexicographically greater than what we already have, we should traverse the partial path backwards and add cycles. So we begin with 4, from which no cycle can be added. We then reach 3, which has outgoing nodes left. We there find the cycle 3B2B3 and add it to our path, so that we have 1A2A3B2B3A4 which is the answer.
Hope this helps.
Testing
Keep getting wrong answer, any test data? I have ran it on several things and works for each case.

 New poster
 Posts: 7
 Joined: Tue Dec 09, 2003 5:48 am
 Location: Taiwan
Re: Testing
Try this.rbuchan wrote:Keep getting wrong answer, any test data? I have ran it on several things and works for each case.
Answer:13
19
raloha
arachnid
dog
gopher
rat
tiger
aloha
raloha
arachnid
dog
gopher
rat
tiger
aloha
arachnid
dog
gopher
rat
tiger
3
oak
maple
elm
6
ab
ba
bc
ca
ad
da
3
aabba
aabb
ba
4
ab
ac
ad
ae
2
abc
cba
7
ab
bc
cd
ce
ea
ac
da
21
bc
d
dc
bd
ca
ac
a
aa
aaa
aaaa
aaaaa
b
bb
bbb
bbbb
abbbb
c
cc
cac
cccc
cccca
17
ca
ac
a
aa
aaa
aaaa
aaaaa
b
bb
bbb
bbbb
abbbb
c
cc
cac
cccc
cccca
16
ac
a
aa
aaa
aaaa
aaaaa
b
bb
bbb
bbbb
abbbb
c
cc
cac
cccc
cccca
10
ab
bc
cd
de
ed
dc
cb
ba
bd
db
10
mo
om
ke
eo
eam
mae
em
me
ok
ok
20
eb
bc
cb
be
ab
ba
cd
dc
ef
fe
eb
bc
cb
be
ab
ba
cd
dc
ef
fe
aloha.aloha.arachnid.dog.gopher.raloha.arachnid.dog.gopher.raloha.arachnid.dog.gopher.rat.tiger.rat.tiger.rat.tiger
***
ba.ab.bc.ca.ad.da
aabb.ba.aabba
***
abc.cba
ab.bc.cd.da.ac.ce.ea
b.bb.bbb.bbbb.bc.c.ca.a.aa.aaa.aaaa.aaaaa.abbbb.bd.d.dc.cac.cc.cccc.cccca.ac
c.ca.a.aa.aaa.aaaa.aaaaa.ac.cac.cc.cccc.cccca.abbbb.b.bb.bbb.bbbb
a.aa.aaa.aaaa.aaaaa.ac.c.cac.cc.cccc.cccca.abbbb.b.bb.bbb.bbbb
ab.bc.cb.bd.dc.cd.de.ed.db.ba
ok.ke.eam.mae.em.me.eo.om.mo.ok
ab.ba.ab.bc.cb.bc.cd.dc.cd.dc.cb.be.eb.be.ef.fe.ef.fe.eb.ba
10441  What means "lexicographically least compound&qu
Hi, first of all I'm new on the Forum, so Hallo to everybody!
I had a question about the Catenyms Problem: when it says "Give the lexicographically least compound" Catenyms, what is with it meant?
I thinked that every Word sholud be converted into its Ascii Code and the give the Catenyms with Words with Ascii code smaller as possible first, but then I saw some Output Examples and i think I haven't understood the correct Request.
I wrote a C++ Code whic perfectly works for what i mean, but with some ouputs examples my Catenyms has a different order, because I didn't understand the "Lex. least Compound" concept.
For example:
aabba
aabb
ba
should give me aabb.ba.aabba (why not ba.aabb.aabba ?)
Maybe sholud I start (if possible) always to the "smallest" letter, and then "with Euler Path) always point to the smallest letter?
Please explain me what is the real asked Problem!
Thanks!
I had a question about the Catenyms Problem: when it says "Give the lexicographically least compound" Catenyms, what is with it meant?
I thinked that every Word sholud be converted into its Ascii Code and the give the Catenyms with Words with Ascii code smaller as possible first, but then I saw some Output Examples and i think I haven't understood the correct Request.
I wrote a C++ Code whic perfectly works for what i mean, but with some ouputs examples my Catenyms has a different order, because I didn't understand the "Lex. least Compound" concept.
For example:
aabba
aabb
ba
should give me aabb.ba.aabba (why not ba.aabb.aabba ?)
Maybe sholud I start (if possible) always to the "smallest" letter, and then "with Euler Path) always point to the smallest letter?
Please explain me what is the real asked Problem!
Thanks!