10441 - Catenyms

[WanBa]

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


thanx in advance
WanBa

[Whinii F.]

Try modeling it as an Euler cycle problem.
(Euler circuit? cycle? I don't know which is the right one. )

[Dmytro Chernysh]

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 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]

Can you give a bit bigger hint?
By the way, a simple sorting doen't fit for some reasons...

[anupam]

yes i faced the same problem in 3 or more problems. plese any1 help us.

[Per]

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]

thanks per. it really helps:-))

[anupam]

yes, got 1 problem ac.
thanks again.

[dwyak]

Look at this case:
1
3
aabba
aabb
ba

What's the correct answer?

aabb.ba.aabba
or
aabba.aabb.ba

[Per]

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]

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

[Der-Johng Sun]

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

Answer:

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

[Mattia]

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!

[Mattia]

Ok I found the Answer by myself looking around in the Web and my Program has been accepted by the Online judge!

Thanks anyway