SongsList
TCCC07 Semi 2 · 2007-07-30 · by ivan_metelsky
Problem Statement
You are given a
You wish to arrange all the songs into a list sorted in lexicographical order. Each song can be included in the list in one of the following 6 formats: "BAND ALBUM SONG", "BAND SONG ALBUM", "ALBUM BAND SONG", "ALBUM SONG BAND", "SONG BAND ALBUM", "SONG ALBUM BAND". Different songs in the list can have different formats. In other words, the format chosen for a song does not depend on the formats chosen for other songs in the list. Determine all possible 0-indexed positions of the song represented by songs[0] in the list. Return a
Notes
- A String A comes before a String B lexicographically if A is a proper prefix of B, or if A has a smaller character at the first position where the characters differ. Note that the space character (' ') is lexicographically smaller than the letters 'A'-'Z'.
Constraints
- songs will contain between 1 and 50 elements, inclusive.
- Each element of songs will contain between 5 and 50 characters, inclusive.
- Each element of songs will be in the format "BAND ALBUM SONG" (quotes for clarity), where BAND, ALBUM and SONG are non-empty sequences of lowercase letters ('a'-'z').
- The following property will hold for every pair of distinct songs S1 and S2 in songs: Write S1 in all 6 possible formats. Then, write S2 in all 6 possible formats. There will be no overlap between these two lists (overlap within each list is permitted). For example, songs cannot contain both "a b c" and "c b a" because "c b a" can be written as "a b c" (in "SONG ALBUM BAND" format).
{ "beatles help yesterday",
"queen innuendo showmustgoon",
"eagles hotelcalifornia hotelcalifornia" }
Returns: {0, 1, 2 }
If we write all the songs in the format "BAND ALBUM SONG", then the song from songs[0] will get position 0 and the list will be the following: "beatles help yesterday" "eagles hotelcalifornia hotelcalifornia" "queen innuendo showmustgoon" If we want to put "yesterday" in position 1, we can write it in the format "ALBUM BAND SONG" to get the following list: "eagles hotelcalifornia hotelcalifornia" "help beatles yesterday" "queen innuendo showmustgoon" And if we want to put "yesterday" in position 2, we can write it in the format "SONG BAND ALBUM" to get the following list: "eagles hotelcalifornia hotelcalifornia" "queen innuendo showmustgoon" "yesterday beatles help"
{ "a a a",
"b b b",
"c c c" }
Returns: {0 }
{ "b e h",
"i i i",
"g g g",
"f f f",
"d d d",
"c c c",
"a a a" }
Returns: {1, 3, 5 }
{"xfmvwqv tbyngsbvxraqiugkklz pvzgdrspixwyuutgakxrdd","dtjonfwjgnbxnqkb gjr klxiserjliaroahobtvwfdwzgwjsd","sfcvvrhqujtyhldjo kgquknyeonmhtxeg gudsdsiolbeekcz","pvajkvzypxgrvhrnpdstotwhvqyljcr awhcn dyxghxtmcmhu","euzwbjnrkehzvffpiyb jsi zlcgvgnavnqilvleeaxhwykuue","ugtuyzqlf s cnesajkzbxenogmmhwxbkupybxsfhqcqnwqson","kngzutbklosz oybkvompdn lcgdtlfcjdalupjwlozjsbtabc","fazkd mqdboeonmn zcuijznbkbvgotsbnjnygiwkivajkarvn","plk eghxxdcongbdqszvyxmabavtcyukzsqgbpefmhvroywp u","bvxnvzs qmvukgyaqlazoqbnyxpq bszxdfzoppadnllmdofzd","pfe ubrnzorvtvdococmroyloa kpekqyiggyjiiloadqijrgj","cezdgtza qlundayhvovktgwlwmu zprhqfijndhxxvtgfsgdc","dwelaxbpgqzpllggfdczcdrj kb ijmthndkottqhulyxhpvtj","tkykdzoaxujtbarxmqnqrxfxiovqub q ssylbxjwxmkpgzcgu","qpuzrlxuc vmnisetenjgrixv ygxqfqiokapsqqrmyhoxochi","wbzr eisjpmjtgcqpxwryessrpubpeedi wptrwfbpdjvkdmku","xtuohqzfdcmedosggqbjeql ovyopvqviplvisxhhsnd gggxr","anaclxoptraerezbaz hqu wwpyfvvkdgkhmfabopfjwaqgxbd","xcwbgjbdpduhvoe xvgficdjizoayvmsmsocpyfbrvpfg ulxt","fkbgyrjukcsujohnqfnzcfx ujyl xqsvdfybflfkschbmkcrk","wrabqelb iqrywzlk haaoeqvshwtqkxekhswxywaqhqmqlyop","mzwmmjozv gbhpdujl unnmegawghyfkcxpdofqreqrazbhqum","bgawhftqagjchvb jsbw kkwuernqepgstbbacyblhtwrhiwnk","xdqtrohqcmblcnvyxkrtghiyrgkrwgkufbvpqnlen cxvicw v","houransaibicqsfjrzlxrcdjigiszgkolrnrgfwvlp ve xhiv","nkjuouzwrmkupwwt qbuzgjgcujejz abobwkrazkaapcsghhr","opzdrlki vzwgnklnyhw gqlciwprkonyvaafkjdfuusrayths","ringnmoixhjockoqkvdjz ctpfskgchmeqt hymdizxhuikswb","rhgkokmvhuvndpevoeap epdcdvvelppdnqhbezj kvqprtzha","ta cwugiycbijasenxqlbexijjiberbrdsn wjzwdkcduoldyb","qwrfvundbjmicmoiifiyq zj zjnbyxfpquimklyeymtwhfebp","jffsyoyylgztykdjae nipcpfivrbuyltmfnrzczkt fbikfqz","nzonrllqhdhss niprhfczmjnrqywx ljigzypzgyasfzvwzgw","wtatnvoqlyrnfpz pizelkseyzznxajsiavmscglwref vteel","enkdccoxe nbznrxkjmzvgwznouipdokrngihhoqpdlrmwrj n","sadccvzjqncvqcpyaydrtfqs mvt gzsbofrcnmjfwxyxjboms","nfykmfmwojdpnfitwlmhdeffuinghxncbcukexf cmuzfv rup","hkmhsscuwnbpcj jflkgastspaks zroowleeflwdvizxdsiel","ygbvzypugfrxqekfskpwmhnvzfxaouzuwpsbxvd lv hlurrzd","s qkibxnxxnpcsiznus arpfqvylkvjmfagfbzgmohufnkzgcs","yclgboktsyfancfrzxo khbgtklpodcqkamte ciahxkdndhni","lj shtmqksytbjqsetrtuuwaqhumpv tvqlabxfengttwjdzhc","rpntnzozencgqdyfgezbpcykuwiwhr sriciwomiiavmwlzu e","ywhuodkkgucqzhtntmgrpflwedshejzedr ipdsqqwjd oexww","jypgoskstciktq eluslly zlwvjgoufahkpfdtfqilxnolyta","wfsiqqarykqt mwtqockyebpabbkmytggwvf pldrshbcaovfj","kedwrckzjmrobqjlyc pjiiwiex gyfjfsjeyjfjgspsdczcbp","gemabtgehwtorpxenbmra epdyxqrdplfzczpwdcerr rfhzws","wlfxhpspecxk xtojl yakxwhxfwrwpmeuivmiisprtewdyjst","nauo fgganuhimtjyrvhkhvtatrjqacnudlefnuyporv bisci"}
Returns: {10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49 }
{"b ababbaababbbababbabaaabbbbbbabbbbabbaaab bbababa","babababababababbbbbbbbb ababbaaaaabaababbbbaaba ba","ababbbbaabaabaaabababbaabbaaababbabbbb ab aabbabbb","abbaaaabaaaabbaababaabaabba bbbbbbaabbbaaaaaa baaa","bbaaaa baaaabaa bababbaabbaaaaabaaababababaaababaa","aba aaaaabbaaaabbababaabaaaaabbaaaaaaaaabbbba babb","aaaaaabbabbbaba bbbaaabbaaaaaaabbaababb bababbbaaa","abb bababa bbababbbabbbbbabbaaabaababbaababaaabbba","babbbaabbabaaabbb bababaaabbabbbbbaabaaabaaaa aaab","baabababbbaabaaaaabbbbbaabbbbaa bbb baabbbaaabaaba","aab babbbbabbabababbbaaababbaabbbaaaabba abaababab","bbbbaaa baabaabbbabaaabba babaabaaaaababbbbaabbbaa","aaabab baaaabbbaab baabaaabbbabbabbbbbbbabababbaab","aabbbbbaabaaababbaaaaaabbabbbbba bbbbba aaaaababaa","aa aaabaababb ababaaaaabbaababbaaaaaababbabababbaa","abaabbaaaaaaababaaaaaaaabbaaaaabababbaab abbab aaa","babaaabb aabaaaaabaaaaaaabbbabbabbbbabbaabaa abbab","abbabaaabbbbabbbbaabbababaabbab bbbababaa bbbaaaaa","baaa abbbbaabbabbbbbbbbaabbbb bababbaababbbbbbabab","baabaababbbbaaaababbb abbba aaaababbbbbaabbbbabaaa","aaaaabbbaabaaaabb abbbaabaaaba baabbaabbbabbaabbab","bbaaaabbbbbbbaaaaabbb a bababbbbabbbabbbbbabbbbabb","bbbbb babbbbbabababbaabaabaaaaaabbabbaaaba baabaaa","babbaaababaab aabababbabbababbabbbaababbbbaa babbb","babaaaaaabbababab bba baabaabbbaaaaabbbbabbaaabaab","abbbbbaaaaaaabababababbbabaaaaabbb b baabbbabbbaba","abbaaaabba baabaaababbbbaaaabbaaaab aabbaabaaabbaa","babbba aabbbabaa aabbbbabbbbbababbabbaabbababbbabb","aabababaabbabbbabbbbabbb baabaaaa babaabbabaaaabaa","ababbaaaa babbaaababaaaaaabba baaaababababbababbaa","aabaaaabbbbbbaaababbaabbbabbabbaaab aaabbba abaaab","bbbaa babaabbabaababbabbaabbaaa bbababaaabaabbabab","baaaabababa abaaaaaabaaaaaababbabbbaabaabaaa abaab","baba bbb aabbbbabbabbaabaaabababaabaabbaaabbbabbab","aabaaabaabaaaabaaababaaaaababb baba aaaabbabaabaab","aababbaabbabbaba bba bbaaaababbbbababbaabbbababbaa","aaaaabbbaabaabb bbabbaababababbaaaabbbaaabba abaaa","babbaabbbbbababaabbaab baaaabaaaaa baabbbaaabbbaaa","bbaababaabbabbbbababbaaabaaaabbbbabb baaab babaaba","aaaaaa bbabbaaaaaaabababbbabbabbbba ababbaaabbaaaa","b babbbababaa aaabaabaaabbabbababbaaabbaabbbbabbbb","babbbaabbaaaababbaab abbbbabbbababaababbabaa abaaa","abba bbbaabaaabaaabbbbabbbbababbb aabbbabaaaaabbba","baaba ababbabbabbabbabbbaab bbbbbabbbbaabaaaaabbaa","ababbababababbaabbaabaaaabaaabbbbbbaab ababba abba","abababaaaa aabbaaaabaababbabababbaaaaa aabaaaaaaba","aba bbbbaaaaabbaa aaaabaaaabbabbaaabaabbbbbabaabbb","baaabba aabaaaa baaababbbbabbbabbbaabbaabbaabbbaab","aaaabaa baaaaabbaaaabababbbbbbbaaaabaabbbabab aaab","babaaba aaabbabbbaaabbabaaabb abbaabbbabbbaaababab"}
Returns: {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49 }
Submissions are judged against all 100 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SongsList with a public method vector<int> getPositions(vector<string> songs) · 100 test cases · 2 s / 256 MB per case