EllysPlaylists
Member SRM 471 · 2009-12-03 · by espr1t
Problem Statement
She has chosen several songs from which she wants to compose a playlist. The names of these songs are given in
A playlist is a sequence containing exactly K song names from songs. Each song from songs can be included zero, one or more times into a playlist. For each song in her playlist (except the last one), Elly wants the transition from this song to the next one in the playlist to be smooth. She calls transition from one song to another smooth if the substring formed by the first three letters of the name of the new song is the same as the substring formed by the last three letters from the name of the previous song. For example valid smooth transitions are from "xxxabc" to "abcyyy", from "entersandman" to "maneater", or from "heavensalie" to "liebe". On the other hand invalid transitions are from "yyydefg" to "defgyyy", from "toxicity" to "citylights", from "fadetoblack" to "breakingthehabit", from "hello" to "lol" or from "abbccddd" to "bcda".
Elly wonders how many different playlists with exactly K songs she can make from the given songs, while respecting her wish to have smooth transition between each two consecutive ones. Since this number can be quite large, return its remainder when divided by 1,000,000,007. Two playlists are considered different if there is an index i such that the i-th songs in these playlists are different.
Constraints
- K will be between 1 and 1000, inclusive.
- songs will contain between 1 and 50 elements, inclusive.
- Each element of songs will contain between 3 and 20 characters, inclusive.
- Each element of songs will consist of lowercase Latin letters ('a'-'z') only.
- All elements of songs will be distinct.
Statement by TopCoder, Inc. — view the original on the archive.
{ "abcxxx", "xxxabc", "entersandman", "toxicity", "maneater", "heavensalie",
"liebe", "citylights", "fadetoblack", "breakingthehabit", "yyydefg", "defgyyy" }
2
Returns: 5
The possible pairs are {"abcxxx", "xxxabc"}, {"xxxabc", "abcxxx"}, {"entersandman", "maneater"}, {"heavensalie", "liebe"}, and {"defgyyy", "yyydefg"}. Note that the order of the songs is important.
{ "aaaaaa", "aaabcd", "bcdaaa" }
4
Returns: 13
One song can be used more than once in a playlist.
{ "aaa", "aaaa", "aaaaa" }
3
Returns: 27
Aaaaaaa...
{ "elly", "looks", "lovely" }
1
Returns: 3
Each song is a valid playlist.
{ "life", "universe", "everything" }
42
Returns: 0
No valid sequence of 42 songs exists.
{ "aaaaaaaaa", "aaabbbaaa", "aaacccaaa", "aaadddaaa", "aaaeeeaaa", "aaafffaaa" }
12
Returns: 176782322
The answer can be quite large, so don't forget to return only its remainder.
Submissions are judged against all 100 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EllysPlaylists with a public method int countPlaylists(vector<string> songs, int K) · 100 test cases · 2 s / 256 MB per case