10441 - Catenyms

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10441 - Catenyms

Post by WanBa »

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


thanx in advance
WanBa
destiny conditioned by past

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. »

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

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

10441 - Eulerian path - easy, but lexicographically not...

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

Post by 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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Can you?

Post by Dmytro Chernysh »

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:

Post by anupam »

yes i faced the same problem in 3 or more problems. plese any1 help us. :oops:
"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

Post by 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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

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:

Post by anupam »

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:

Post by dwyak »

Look at this case:
1
3
aabba
aabb
ba

What's the correct answer?

aabb.ba.aabba
or
aabba.aabb.ba

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

Post by 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
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

Testing

Post by rbuchan »

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

Post by Der-Johng Sun »

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
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
New poster
Posts: 2
Joined: Sat Jan 06, 2007 2:04 pm
Location: Switzerland
Contact:

10441 - What means "lexicographically least compound&qu

Post by 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! :D

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

Post by 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 8)

Post Reply

Return to “Volume 104 (10400-10499)”