TRIP - Trip

Alice and Bob want to go on holiday. Each of them has drawn up a list of cities to be visited in turn. A list may contain a city more than once. As they want to travel together, they have to agree upon a common route. No one wants to change the order of the cities on his list or add other cities. Therefore they have no choice but to remove some cities from the list. Of course the common route is to involve as much sight-seeing in cities as possible. There are exactly 26 cities in the region. Therefore they are encoded on the lists as lower case letters from 'a' to 'z'.


The first line of input contains a number T <= 10 that indicates the number of test cases to follow. Each test case consists of two lines; the first line is the list of Alice, the second line is the list of Bob. Each list consists of 1 to 80 lower case letters.


The output for each test case should contain all different trips exactly once that meet the conditions described above. There is at least one such trip, but never more than 1000 different ones. You should order the trips in lexicographic order. Print one blank line between the output of different test cases.






hide comments
minhthai: 2016-02-23 16:53:35

in java, lcs + recursion is the right way but you also have to ignore unnecessary cases and use StringBuilder. At least, that worked for me :)

(Tjandra Satria Gunawan)(曾毅昆): 2015-08-25 18:52:31

Got AC with unusual trick (need a lot of memory), although I don't know how to solve this problem using the usual way :p

Mitch Schwartz: 2014-07-09 02:58:01

@Jens Stimpfle: Thanks for the notification. I don't have time/motivation to verify your claim at the moment. It is a somewhat similar situation to TWINSNOW, although not exactly the same. (I think your claim has more credibility because of your submission history and your way of writing the comment, but I'd still rather not take action at this point.) Thanks for your understanding.

Last edit: 2014-07-09 02:59:46
Jens Stimpfle: 2014-06-28 01:06:18

It seems that the master solution to this problem is wrong. I couldn't get my own solution to be accepted. But the first other solution I found with a search engine was accepted although it is obviously wrong (fails to properly reset between test cases).

Hemant Kumar Singh: 2014-01-20 13:31:38

In the sample output
This doesn't makes sense. It has two aa in the end. Why would anyone like to have the same city consecutively on their list?

Paritosh Aggarwal: 2013-01-16 17:41:56

TLE :| I am using LCS + Recursion to generate all the strings. I tried memoizing the recursion as well. Any ideas anybody?

manish sharma: 2012-01-17 15:49:05

my answer is getting TLE...please suggest me some way ...I used the LCS code

Vipul Modi: 2011-12-06 11:17:33

python is best for this one :)

Prashant: 2011-05-22 19:42:22

my answer is correct but getting TLE . Please suggest another algo.

Adrian Kuegel: 2011-02-07 09:29:54

It refers to the trips counted without duplicates ("but never more than 1000 different ones").

Added by:Adrian Kuegel
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:own problem, used in CEOI 2003