EllysPlaylists
Member SRM 471 · 2009-12-03 · by espr1t
Member SRM 471 · 2009-12-03 · by espr1t · Dynamic Programming, String Manipulation
Problem Statement
Problem Statement
Elly is great fan of consistency. She would like to have order in even the simplest things in life â like listening to music.
She has chosen several songs from which she wants to compose a playlist. The names of these songs are given inString[] songs, where each element is the name of a single song. Each name is unique and consists of at least three lowercase Latin letters.
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.
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.
Examples
0)
{ "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.
1)
{ "aaaaaa", "aaabcd", "bcdaaa" }
4
Returns: 13
One song can be used more than once in a playlist.
2)
{ "aaa", "aaaa", "aaaaa" }
3
Returns: 27
Aaaaaaa...
3)
{ "elly", "looks", "lovely" }
1
Returns: 3
Each song is a valid playlist.
4)
{ "life", "universe", "everything" }
42
Returns: 0
No valid sequence of 42 songs exists.
5)
{ "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.
Coding Area
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