Connection Status:
Competition Arena > GuitarConcert

GuitarConcert

SRM 366 · 2007-09-18 · by jthread

SRM 366 · 2007-09-18 · by jthread · Search
Class Name: GuitarConcert
Return Type: String[]
Method Name: buyGuitars
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

You are a guitar player and you want to play a concert. Unfortunately, you don't have any good guitars left, so you need to buy some new guitars. You are given a String[] guitarNames, the i-th element of which is the name of the i-th guitar that is available for purchase.


You have a list of songs that you would like to play at the concert. Certain songs cannot be played with certain guitars because they will sound weird, so you might not be able to play the entire concert with just one guitar. You are given a String[] guitarSongs, where the j-th character of the i-th element is 'Y' if the j-th song can be played on the i-th guitar, and 'N' otherwise.


You want your concert to be as long as possible, so your main goal is to play as many of the songs as possible (you can only play each song at most once). You also want to save your money, so you want to buy the least number of guitars required to play that maximum number of songs. Return a String[] containing the names of the guitars you should buy in alphabetical order. If there are multiple possible return values, return the one among them that comes first lexicographically. A String[] s1 comes before String[] s2 lexicographically if s1[i] comes before s2[i] alphabetically, where i is the first position at which they differ.

Constraints

  • guitarNames will contain between 1 and 10 elements, inclusive.
  • guitarSongs will contain the same number of elements as guitarNames.
  • Each element of guitarSongs will contain between 1 and 50 characters, inclusive.
  • Each element of guitarSongs will contain the same number of characters.
  • Each element of guitarSongs will contain only the uppercase letters 'Y' or 'N'.
  • Each element of guitarNames will contain between 2 and 50 characters, inclusive.
  • Each element of guitarNames will contain only uppercase letters ('A' - 'Z').
  • All elements of guitarNames will be distinct.
Examples
0)
{"GIBSON","FENDER", "TAYLOR"}
{"YNYYN", "NNNYY", "YYYYY"}
Returns: {"TAYLOR" }

You can play all the songs on the TAYLOR guitar.

1)
{"GIBSON", "CRAFTER", "FENDER", "TAYLOR"}
{"YYYNN", "NNNYY", "YYNNY", "YNNNN"}
Returns: {"CRAFTER", "GIBSON" }

You can play all the songs, but you need 2 guitars to do it.

2)
{"AB", "AA", "BA"}
{"YN", "YN", "NN"}
Returns: {"AA" }

You can only play the first song, so you buy guitar AA because it comes before AB alphabetically.

3)
{"FENDER", "GIBSON", "CRAFTER", "EPIPHONE", "BCRICH"}
{"YYNNYNN", "YYYNYNN", "NNNNNYY", "NNYNNNN", "NNNYNNN"}
Returns: {"BCRICH", "CRAFTER", "GIBSON" }
4)
{"XSWLEJGJFPJTAPNEVYLNVIBGPARTRGSZVMFTJOFAPVKVNCQAJA","JDIROLNQTU","FHV","MFTURTGHJYLLFWDIHZMSXDMUH","YYZCFHNVLFMVPSHZMRGDWMGYDBHUAQPZRRLHHQKICQXN","SFKPJZSCYTTZXTNSXOUJICOUBIW"}
{"YYNYNYYN","YYNYYYYY","YYYYYNNN","NYNYNYNN","YNNNYNNY","NNNNYNNY"}
Returns: {"FHV", "JDIROLNQTU" }

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

Coding Area

Language: C++17 · define a public class GuitarConcert with a public method vector<string> buyGuitars(vector<string> guitarNames, vector<string> guitarSongs) · 74 test cases · 2 s / 256 MB per case

Submitting as anonymous