The Discovery of the Millenium
All submissions for this problem are available.
Atlantis is said to be the most powerful empire to have ever existed in the world in all of its history. The natives had very advanced knowledge about the sciences, especially on storing and directing energy through crystals. It is said that when the people of Atlantis were corrupted with the lust for power and the greed of wealth, they tried to invade Athens but failed. Seeing this Zeus sank Atlantis to the bottom of the ocean to punish the people for their sins and misdoings. Before they went down, the Atlanteans hid their most valuable manuscripts in places of great importance, with one of them supposed to be the Sphinx at Giza.
Recently, a new room was discovered beneath the right paw of the sphinx and within this room the archaeologists found dozens of manuscripts. They were written in heighlogryphs all except one, which was surprisingly written in the English language. This manuscript may hold the key to unlock the secrets of Atlantis and usher in a new generation of prosperity.
Alas! Even though the manuscript uses letters of the english alphabet, the ordering is not what one would expect it to be. The script contained a short index, but the ordering of the items in the index was different from what one would expect if the characters were ordered the same way as in the English alphabet.
You are being given the chance of a lifetime now. To help the world unravel the long lost secrets of Atlantis you are to write a program to determine the collating sequence of the script. In particular, your program will take a set of strings that has been sorted according to a particular collating sequence and determine what that sequence is??
The First line consists of total no of test cases.
For each test case,the input consists of an ordered list of strings of uppercase letters, one string per line. Each string contains at most 20 characters. The end of the list is signalled by a line with the single character `#'. Not all letters are necessarily used, but the list will imply a complete ordering among those letters that are used.
Your output should be a single line containing uppercase letters in the order that specifies the collating sequence used to produce the input data file.
1 XWY ZX ZXY ZXW YWWX #
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.