TopCoder problem "CDPlayer" used in SRM 343 (Division I Level One , Division II Level Two)



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:

  1. Randomly select a permutation of the n songs.
  2. Play the songs in order from that permutation.
  3. 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 String[] 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:String[], int
Returns:int
Method signature:int isRandom(String[] songlist, int n)
(be sure your method is public)
    
 

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

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10667&pm=7476

Writer:

connect4

Testers:

PabloGilberto , brett1479 , Olexiy , lovro

Problem categories:

Brute Force