## 10441 - Catenyms

Moderator: Board moderators

WanBa
New poster
Posts: 14
Joined: Mon Apr 28, 2003 11:21 am

### 10441 - Catenyms

any Superman can certify this problem is that format?
pls, give me some hint ! !

WanBa
destiny conditioned by past

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
Try modeling it as an Euler cycle problem.
(Euler circuit? cycle? I don't know which is the right one. )
JongMan @ Yonsei

Dmytro Chernysh
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...

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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?

Dmytro Chernysh
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...

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
yes i faced the same problem in 3 or more problems. plese any1 help us.
"Everything should be made simple, but not always simpler"

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Ok, an example. Consider the graph consisiting of four nodes and the five edges

Code: Select all

``````from to label
1 2 A
2 3 A
3 4 A
3 2 B
2 3 B``````
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 1-A-2-A-3-A-4 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 3-B-2-B-3 and add it to our path, so that we have 1-A-2-A-3-B-2-B-3-A-4 which is the answer.

Hope this helps.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
thanks per. it really helps:-))
"Everything should be made simple, but not always simpler"

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
yes, got 1 problem ac.
thanks again.
"Everything should be made simple, but not always simpler"

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:
Look at this case:
1
3
aabba
aabb
ba

aabb.ba.aabba
or
aabba.aabb.ba

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
The answer is aabb.ba.aabba since '.' (by the ASCII ordering) is less than 'a'. But incidentally, note that the edge "aabb" is also lexicographically less than the edge "aabba".

rbuchan
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

### Testing

Keep getting wrong answer, any test data? I have ran it on several things and works for each case.

Der-Johng Sun
New poster
Posts: 7
Joined: Tue Dec 09, 2003 5:48 am
Location: Taiwan

### Re: Testing

rbuchan wrote:Keep getting wrong answer, any test data? I have ran it on several things and works for each case.
Try this.
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
da
3
aabba
aabb
ba
4
ab
ac
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
***
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

Mattia
New poster
Posts: 2
Joined: Sat Jan 06, 2007 2:04 pm
Location: Switzerland
Contact:

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

Thanks!

Mattia
New poster
Posts: 2
Joined: Sat Jan 06, 2007 2:04 pm
Location: Switzerland
Contact:
Ok I found the Answer by myself looking around in the Web and my Program has been accepted by the Online judge!

Thanks anyway