Connection Status:
Competition Arena > ShuffledPlaylist

ShuffledPlaylist

SRM 443 · 2009-06-23 · by gojira_tc

SRM 443 · 2009-06-23 · by gojira_tc · Dynamic Programming, Math
Class Name: ShuffledPlaylist
Return Type: int
Method Name: count
Arg Types: (vector<string>, vector<string>, int, int)
Problem Statement

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.

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)
{"0 3,1 2,0 2"}
{"YY","YY"}
2
4
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}.

1)
{"0 3,1 2,0 2"}
{"YN","NY"}
2
4
Returns: 5

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

2)
{"0 9",",1 8,","2 3,2 5"}
{"YYY","NYY","NNY"}
5
9
Returns: 7

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

3)
{"5 4,6 2,7 7,2 1,1 3,6 3,2 1,0 3,7 6,5 8,6 4,5 4,6 ",
"5,4 9,0 4,1 4,6 4,3 1,2 1,6 5,2 4,7 7,6 7,5 1,5 8,",
"1 8,7 3,1 1,3 5,0 3,4 4,5 8,6 7,5 7,7 7,5 1,7 6,1 ",
"9,3 1,3 8,6 8,5 2,6 2,2 3,7 5,4 2,7 9,6 3,4 6,5 5,",
"4 6,7 4,1 5,3 7,3 3,3 3,5 9,0 9,4 3,1 1,2 1,0 4,1 ",
"8,6 1,5 8,7 1,6 6,6 9,4 1,6 2,7 5,6 6,1 7,1 7,7 2,",
"0 3,6 1,4 5,0 1,4 3,4 1,4 3,1 2,5 6,1 4,0 6,6 1,3 ",
"4,5 2,5 5,3 9,1 4,1 8,7 5,5 1,4 3,4 6,7 9,5 3,1 8,",
"6 1,3 7,5 5,6 9,6 4,6 6,5 4,7 5,4 ","7,4 4,3 7,7 5,0",
" 3,3 4,0 6,6 1,2 7,7 3,2 1,6 6,",
"0 2,4 5,2 4,2 1,0 8,0 7,4 2,5 9,0 6,2 1,7 8,3 1,7 ",
"9,0 2,4 4,5 1,6 4,3 2,4 7,4 7,6 6,7 6,2 6,1 7,2 4,",
"0 8,4 6,7 1,5 5,1 3,6 9,6 7,7 9,0 6,5 3,1 2,5 9,5 ",
"7,6 9,6 7,4 9,4 8,0 1,4 6,0 7,4 4,5 1,2 1,7 1,2 1,",
"4 2,1 8,4"," 2,2 2,1 3,5 5,0"," 9,7 7,7 3",
",6 8,5 1,5 9,5 9,2 1,0 6,7 5,5 2,4 4,","4 7,6 4,2 7",
",1 4,7 ","4,7 1,7 9,6 4,4 ","1,7 8",",1"," 1,2 9,1 1",
",4"," 4,6 ","5,4 8,3 6,2 5,1 3,1 ","2,6 7,3 5,0 6",",1 ",
"6,2"," ","1,2"," 8,","5"," ","7",",2 ","4"}
{"YYNNNNYNN","YYYNYNYYN","YNYNNYNNY","NNNYNYNNN","YYNNYYNNN",
"NYYNYYNYN","NNNYNNYYN","YYNYYNNYY","NNYNNYYYY"}
41
901001009
Returns: 318813055
4)
{"0"," ","7",",0 8,0 9,0 2",",","0"," ","1"}
{"Y"}
1
100
Returns: 300667430

Submissions are judged against all 105 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ShuffledPlaylist with a public method int count(vector<string> songs, vector<string> transitions, int minLength, int maxLength) · 105 test cases · 2 s / 256 MB per case

Submitting as anonymous