TopCoder problem "Horoscope" used in SRM 275 (Division I Level Two)



Problem Statement

    Recently, you went to a fair where one of the attractions was an oracle who would give you your horoscope for the next several days. She wasn't very precise though; all she would say is whether you would have a Good ('G') or Bad ('B') day on a particular day. Besides not being very precise, she was very inconsistent: she could be right AT MOST R times in a row, and she could be wrong AT MOST W times in a row.



Create a class Horoscope, which contains a method maxGoodDays. The method takes a String[] predictions, an int R and an int W as input. The elements of predictions are strings containing only the characters 'G' or 'B', indicating whether your horoscope for that day was predicted to be good or bad. (Note that you should concatenate the elements of predictions and consider the entire string the predictions). The method should return the maximum number of Good days that you can experience given the predictions, and values for R and W.
 

Definition

    
Class:Horoscope
Method:maxGoodDays
Parameters:String[], int, int
Returns:int
Method signature:int maxGoodDays(String[] predictions, int R, int W)
(be sure your method is public)
    
 

Constraints

-predictions will contain between 1 and 50 elements inclusive.
-Each element of predictions will contain between 1 and 50 characters inclusive.
-Each element of predictions will contain only the characters 'G' or 'B'.
-R will be between 1 and 50 inclusive.
-W will be between 1 and 50 inclusive.
 

Examples

0)
    
{"GGGG"}
4
1
Returns: 4
Since R is 4, the oracle can be Right for all 4 predicted days. In this case, the maximum number of good days you would experience is 4.
1)
    
{"GGGG"}
2
2
Returns: 3
Here, the oracle can't be Right for all 4 days. One way of achieving 3 Good days (which is the maximum possible in this case) is for the oracles predictions to be Right, Wrong, Right, Right for the 4 days respectively. Thus, the return value here is 3.
2)
    
{"GBGBBB"}
3
4
Returns: 6
3)
    
{"GGGBBBGBGGGB", "GGBBBBBBBBBGBGBGBGBGBGBGBGBBBBBBBBBBBBBBGGGG", "G"}
4
35
Returns: 56

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8072&pm=5909

Writer:

NeverMore

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Dynamic Programming