TopCoder problem "BestJob" used in TCHS SRM 56 (Division I Level Three)



Problem Statement

    

Some time ago, you asked n people a set of m questions about the history of your country, and you wrote down their answers. Every question had two possible answers - "yes" or "no". You divided all the people into three groups. People in the first group always gave correct answers to all the questions. People in the second group always gave wrong answers to all the questions. People in the third group gave you at least one correct answer and at least one wrong answer.

Now you want to analyze the gathered data, but unfortunately, you completely forgot which people belong to each of the three groups, and you forgot the correct answers to the questions as well. However, you're absolutely certain that there were exactly k1 people in the first group, k2 people in the second group and n - k1 - k2 people in the third group. Using this information along with the people's answers, you should be able to either restore the correct answers to the questions or determine that you made an error when noting down people's answers.

The answers that you wrote down are given in the String[] answers, where the j-th character of the i-th element is the answer given to the j-th question by the i-th person. 'N' means "no" and 'Y' means "yes". Return a String containing exactly m characters, where the i-th character is the correct answer for the i-th question ('N' for "no" and 'Y' for "yes"). If there are multiple possible Strings, return the one among them that comes first alphabetically. If there are no such Strings, return the empty String instead.

 

Definition

    
Class:BestJob
Method:didIMadeMistake
Parameters:int, int, String[]
Returns:String
Method signature:String didIMadeMistake(int k1, int k2, String[] answers)
(be sure your method is public)
    
 

Notes

-The alphabetically earliest of two Strings is the one with the alphabetically earlier character at the first position at which they differ.
 

Constraints

-answers will contain between 1 and 50 elements, inclusive.
-k1 will be between 0 and n, inclusive, where n is the number of elements in answers.
-k2 will be between 0 and n - k1, inclusive, where n is the number of elements in answers.
-All elements of answers will have the same length.
-Each element of answers will contain between 1 and 50 characters, inclusive.
-Each element of answers will contain only characters 'Y' and 'N'.
 

Examples

0)
    
2
0
{"YY", "YY"}
Returns: "YY"
Here we certainly know that both people answered all questions correctly. So the correct string of answers is "YY".
1)
    
0
0
{"YN", "YY"}
Returns: ""
If correct answers were "YY" or "YN", there would be one person in the first group. If correct answers were "NN" or "NY", there would be one person in the second group. Therefore, you've certainly made an error.
2)
    
1
1
{"YNN", "NYN", "NNN", "NNY"}
Returns: ""
It's possible to have 1 people from the first group and 0 people from the second one, or 1 people from the second group and 0 people from the first one. However it's impossible to have 1 people from each of these groups.
3)
    
1
0
{"N"}
Returns: "N"
4)
    
0
0
{"NYNYNYNYN", "NNYNYNYYN", "YNYNYNYYN", "NYYNYYNYN", "NNYNYNYNY"}
Returns: "NNNNNNNNN"

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13525&pm=9987

Writer:

DStepanenko

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Dynamic Programming, Simple Search, Iteration, Simulation