Problem Statement
There are a lot of programming contests in this world.
Let's determine who is the BestCoder of this year!
The BestCoder is the one who received the most winning points during the whole year.
If there are multiple coders with the most winnning points, each of them will be regarded as the BestCoder.
It is December 1 now, and you want to predict who can be the BestCoder.
There are N coders in question, numbered from 0 to N - 1. Coder j has received points[j] winning points by November.
There are M kinds of important contests, numbered from 0 to M - 1. For contest i, matches[i] matches will be held in December. In each match of contest i, the top wins[i] coders will receive 1 winning point and all other coders will not receive winning points. There will be no tie within each match.
The j-th character of participation[i] is 'Y' if coder j will participate in all matches of contest i, or 'N' if coder j will not participate in any matches of contest i. There are no other coders participating in these matches. That is, the number of participants in each match of contest i is equal to the number of 'Y's in participation[i].
Return a String containing exactly N characters, the j-th character of which is 'Y' if it is possible for coder j to be the BestCoder, or 'N' otherwise. Assume that any outcome is possible for each match that will be held in December. Note that all indices are 0-based.
There are N coders in question, numbered from 0 to N - 1. Coder j has received points[j] winning points by November.
There are M kinds of important contests, numbered from 0 to M - 1. For contest i, matches[i] matches will be held in December. In each match of contest i, the top wins[i] coders will receive 1 winning point and all other coders will not receive winning points. There will be no tie within each match.
The j-th character of participation[i] is 'Y' if coder j will participate in all matches of contest i, or 'N' if coder j will not participate in any matches of contest i. There are no other coders participating in these matches. That is, the number of participants in each match of contest i is equal to the number of 'Y's in participation[i].
Return a String containing exactly N characters, the j-th character of which is 'Y' if it is possible for coder j to be the BestCoder, or 'N' otherwise. Assume that any outcome is possible for each match that will be held in December. Note that all indices are 0-based.
Definition
- Class:
- BestCoder
- Method:
- getCandidates
- Parameters:
- int[], int[], int[], String[]
- Returns:
- String
- Method signature:
- String getCandidates(int[] points, int[] matches, int[] wins, String[] participation)
- (be sure your method is public)
Constraints
- N, the number of elements in points, will be between 1 and 40, inclusive.
- M, the number of elements in matches, will be between 1 and 40, inclusive.
- Each element of points will be between 0 and 1,000,000,000, inclusive.
- Each element of matches will be between 1 and 100,000, inclusive.
- wins will contain exactly M elements.
- participation will contain exactly M elements.
- Each element of participation will contain exactly N characters.
- Each character in participation will be either 'Y' or 'N'.
- For each index i, wins[i] will be between 1 and the number of 'Y's in participation[i], inclusive.
Examples
{ 100, 0 }{ 99 }{ 1 }{ "YY" }Returns: "YN"
Coder 1 cannot be the BestCoder because coder 0 has too many points.{ 100, 1 }{ 99 }{ 1 }{ "YY" }Returns: "YY"
There may be multiple BestCoders.{ 0, 0, 0, 0 }{ 1, 1, 1, 2, 4 }{ 1, 1, 1, 1, 2 }{ "YNNY", "NYNY", "NNYY", "YYNN", "YYYN" }Returns: "YYYN"
Even if coder 3 wins contest 0, 1 and 2, there will be at least one coder with more than 3 points.{ 0, 0, 0, 0 }{ 1, 1, 1, 3, 3 }{ 1, 1, 1, 1, 2 }{ "YNNY", "NYNY", "NNYY", "YYNN", "YYYN" }Returns: "YYYY"
{ 0, 1000, 1000, 0, 0 }{ 1000 }{ 4 }{ "YYYYY" }Returns: "NYYNN"
{ 15465466, 608464477, 573461315, 456712390, 604614195, 218862942, 429423028, 608461797, 168384368, 608458671, 435251868, 168932629, 604992710, 84214059, 608453838, 583789503, 608451926, 608460335, 608458313, 608460778, 608455485, 608452786, 526658116, 608454687, 608453193, 608465287, 140381886, 329938488, 79705761, 608454659, 521602091 }{ 1598, 2163, 2619, 212, 2417, 1051, 199, 1418, 1923, 155, 925, 753, 1265, 1306, 2161, 773, 845, 422, 423, 2369, 851 }{ 2, 3, 1, 11, 11, 4, 2, 27, 15, 11, 1, 7, 19, 17, 6, 1, 16, 7, 4, 9, 15 }{ "YNNNYYYNYYNYNNNNYYNNYNYYNNYYNNN", "YNNNNYNYNNNYNNYNNNYNNNNYNYNNNYY", "NNNNYNNNNNNYNNNNNNNNNNNNNNNNNNN", "YNNYYYNYNYYNNNYNNNYNNNYYYNNYYNY", "YNYNYYYNYNNNNNNYYYNNNYYNYYYNYYN", "NYNYNNYNNNNYNNNNYYNNYNNYNNNNNNN", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYNYYYYNYYYYYYYYYY", "YYYYNYNNYNYNYNYNYYNNNYNYYNNYYYY", "YNNYNYYYYYNYYYNNNYYYNYYYYYYYNYY", "YNYYYYNNNNNNYNNYNYNNYNYNYNNNNNY", "NNYNNYNYNYYNNNNYNNNNNNNYYNYYYNY", "YYNYNNYNYYYYYNYYYNNYYYYNYNYYNYY", "NYYNNNYYNNYNYYYYYNNYYNNYNNYYYNY", "NNNNNNNNYNNNNNNNNNYNNYYNYNNNYNN", "YNYNYYNNYYYNNYYNNYNYNYYNNNYNYNY", "NNYNYYYYNNNNYYNNYYYNYNYNNNYYYYN", "YNNNNYYYNYNNYNNNNNNNNNNNYNYNNYY", "NYYNYNNYYNNNNYNYNYNYYNNNYYNNNNY", "YNNNNNNYNNNYNNYYYNNNYYNNNNNNNNY", "YYYNYYYYYYYYYYYYNYYNYYYYYYYYYYN" }Returns: "NYNNNNNYNYNNNNYNYYYYYYNNYYNNNYN"
Back to all problems