PROBLEM STATEMENT
You recently purchased a CD player from Bob's Bargain Barn. As you don't like listening to songs
from your CDs in the same order every day, you were very interested in the "Random" button on the
CD player. According to the instruction manual, if the CD player has n songs, the "Random"
feature works as follows:
Randomly select a permutation of the n songs.
Play the songs in order from that permutation.
Go to step 1.
Based on this algorithm, for 3 songs you could legally obtain "ABCCAB" and "BCABCA", but not
"AABBCC".
You are not sure if you trust Bob's Bargain Barn, so you want to figure out if the CD player is
broken or not. However, as luck would have it, your sister had started listening to the CD, so
you don't know when the next permutation begins. This means that the list "BBAC" could be an
acceptable list, if the first B was the last song in the first permutation, and the second B
started the second permutation.
You will be given a vector songlist containing the list of songs that you heard. Each
distinct character in songlist represents a single distinct song. This should be concatenated to
form one string. You will also be given n, the number of songs on your CD. If the entire
songlist could have been generated using the above algorithm, return the earliest 0-based index in
songlist where a new permutation began. If there are multiple valid indices that could be the
start of a permutation, return the smallest of these. If the songlist could not have been
generated by the algorithm described above, return -1. See the examples for clarification.
DEFINITION
Class:CDPlayer
Method:isRandom
Parameters:vector , int
Returns:int
Method signature:int isRandom(vector songlist, int n)
CONSTRAINTS
-songlist will contain between 1 and 50 elements, inclusive.
-Each element of songlist will contain between 1 and 50 characters, inclusive.
-Each character in songlist will be one of the first n uppercase letters ('A'-'Z').
-n will be between 1 and 26, inclusive.
EXAMPLES
0)
{"BBAC"}
3
Returns: 1
The example from the problem statement. The first song cannot be the start of a permutation,
since "BBA" is not a permutation of "ABC". However, if the permutation starts at song 1, then
"??B" and "BAC" are both valid.
1)
{"BACAB",
"BCA"}
3
Returns: 2
Index 0 is illegal because the second set of songs "ABB" is illegal. Similarly, index 1 can't be
a legal start ("BBC" is illegal). Index 2 works though, since "?BA", "CAB", "BCA" could be
generated by the algorithm.
2)
{"AAACBACBACBACBACBACBACB"}
3
Returns: -1
Even though all of the songs starting at index 2 work, the "?AA" that would have preceded it could
not have been generated; thus, the CD player is broken.
3)
{"ABCDEABDECBAECDEDACB"}
5
Returns: 0
4)
{"ABCABCABCABCABCABCABC",
"ABCABCABCABCABCABCABC"}
22
Returns: -1
5)
{"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA"}
1
Returns: 0
6)
{"ADEF"}
12
Returns: 0
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.