TopCoder problem "ShuffledPlaylist" used in SRM 443 (Division I Level Three)

Problem Statement

I love music and listen to it all the time. I have a huge amount of songs and often it's easy just to listen to them shuffled rather than to choose a song every time. But I listen to different genres of music and some of them are incompatible (for example, it's quite uncomfortable if some calm classic track is succeeded by a loud noisy song). So I wrote a program which performs the shuffled playback according to some rules.

Speaking formally, I have defined several genres and ascribed each of the songs to one specific genre. I have also defined which genres are compatible, i.e. can be listened to in immediate succession and which are not. The j-th character of the i-th element of String[] transitions is 'Y' if a song of genre i can be succeeded by a song of genre j, and is 'N' otherwise. My program works in the following way: it randomly chooses the first song to play. When the track finishes, the next song is chosen from the set of all songs of compatible genre(s), and so on. The same song may be played several times and it might even happen that the same song is played several times in a row.

You're given String[] songs. Concatenate the elements of songs to obtain a list of the songs. The list will be formatted as a comma-separated list of space-separated pairs of integers, the first of them denoting the genre of the song and the second one denoting its length in minutes. Count the number of different song sequences which might be played using my program and are between minLength and maxLength (both inclusive) minutes long, and return it modulo 600,921,647.

Definition

Class:	ShuffledPlaylist
Method:	count
Parameters:	String[], String[], int, int
Returns:	int
Method signature:	int count(String[] songs, String[] transitions, int minLength, int maxLength)
(be sure your method is public)

Constraints

transitions will contain exactly n elements, where n is between 1 and 9, inclusive.

Each element of transitions will contain exactly n characters.

transitions will contain only 'N' and 'Y' characters.

For each i between 0 and n-1, the i-th character of the i-th element of transitions will be 'Y'.

songs will contain between 1 and 50 elements, inclusive.

Each element of songs will contain between 1 and 50 characters, inclusive.

The concatenation of the elements of songs will be a comma-separated list of space-separated pairs of integers.

The first integer of each pair will be between 0 and n-1, inclusive, with no extra leading zeroes.

The second integer of each pair will be between 1 and 9, inclusive, with no leading zeroes.

minLength will be between 1 and 1,000,000,000, inclusive.

maxLength will be between minLength and 1,000,000,000, inclusive.

Examples

{"0 3,1 2,0 2"}

{"YY","YY"}

Returns: 7

If we enumerate the songs from 0 to 2, then the 7 possible song sequences are: {0},{1},{2},{1,1},{1,2},{2,1},{2,2}.

{"0 3,1 2,0 2"}

{"YN","NY"}

Returns: 5

This time, the genres are incompatible, so the sequences {1,2} and {2,1} are not allowed any more.

{"0 9",",1 8,","2 3,2 5"}

{"YYY","NYY","NNY"}

Returns: 7

The sequences are: {0},{1},{2,2},{2,2,2},{3},{2,3},{3,2}.

{"0 8,","5 6,2"," 2,2 3,6 8,5 8,5 3,0 6,0 7,6 5,3 2",
",0 9,2 3,3 4,5 4,3 3,3 3,2 8,2 9,5 7,2 8,0 1,5 9,1",
" 8,2 9,1 6,3 6,2 6,0 4,6 3,1 5,2 7,4 5,3 3,0",
" 5,6 1,5 6,4 8,5 9,1 4,2 9,5 6,5 6,0 8,3 5,4 6,0 3",
",4 2,5 6,6 2,4 3,1 3,6 3,0 8,2 8,3 7,4 2,0 7,0 2,1",
" 3,4 7,6 3,6 4,3 9,0 2,0 7,0 8,6 4,1 3,2 5,0 6,5 4",
",3 2,3 2,1 5,2 1,5 2,4 8,0 5,1"," ","7,2 6,5 7",",",
"6 9,5 5,","4 2",",4"," 9,0 5,4 8,6 5,5 9,5 8,3 ","2",
",5 ","6,2 3,0 7,1 7,","2 1,0 4",",2 9",",","3"," ","4"}

{"YYYYYYY","YYYYYYY","YYYYYYY","YYYYYYY","YYYYYYY","YYYYYYY","YYYYYYY"}

Returns: 348387817

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10486

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13751&pm=10486

Writer:

gojira_tc

Testers:

PabloGilberto , Yarin , ivan_metelsky

Problem categories:

Dynamic Programming, Math