Connection Status:
Competition Arena > CDPlayer

CDPlayer

SRM 343 · 2007-03-22 · by connect4

SRM 343 · 2007-03-22 · by connect4 · Brute Force
Class Name: CDPlayer
Return Type: int
Method Name: isRandom
Arg Types: (vector<string>, int)
Problem Statement

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.

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

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

Coding Area

Language: C++17 · define a public class CDPlayer with a public method int isRandom(vector<string> songlist, int n) · 126 test cases · 2 s / 256 MB per case

Submitting as anonymous