TopCoder problem "CarrotBoxes" used in SRM 495 (Division I Level Two)



Problem Statement

    There are N boxes numbered 0 through N-1. Every box except for one contains carrots, but Rabbit Hanako does not know which box is the empty one. Each box has the same probability of being empty.



Hanako wants to find the empty box without opening it. Fortunately, she has some clues. Some of the boxes contain information about the content of other boxes, and she knows which boxes contain such information. You are given a String[] information, where the j-th character of the i-th element is 'Y' if opening the i-th box will reveal whether or not the j-th box contains carrots, or 'N' if the i-th box contains no such information.



Return the probability that she can find the empty box without opening it, assuming she behaves optimally.
 

Definition

    
Class:CarrotBoxes
Method:theProbability
Parameters:String[]
Returns:double
Method signature:double theProbability(String[] information)
(be sure your method is public)
    
 

Constraints

-information will contain between 1 and 50 elements, inclusive.
-Each element of information will contain exactly N characters, where N is the number of elements of information.
-The i-th character of the i-th element of information will be 'Y'.
-Each character in information will be 'Y' or 'N'.
 

Examples

0)
    
{"YYYYY",
 "NYNNN",
 "NNYNN",
 "NNNYN",
 "NNNNY"}

Returns: 0.8
The optimal strategy is opening box 0 first. If box 0 contains carrots, she can find the empty box without opening it because box 0 contains information about all boxes. It happens with probability 0.8.
1)
    
{"YNNNN",
 "NYNNN",
 "NNYNN",
 "NNNYN",
 "NNNNY"}
Returns: 0.2
No box contains information about other boxes, so she can find the empty box without opening it only when she opens all other boxes. It happens with probability 0.2.
2)
    
{"Y"}
Returns: 1.0
Since there is only one box, she knows that the only box is empty.
3)
    
{"YNNNN",
 "YYNNN",
 "YNYNN",
 "NNNYY",
 "NNNYY"}

Returns: 0.6
4)
    
{"YYYNNNYN",
 "NYNNNNYN",
 "NNYNNNNN",
 "NYNYNNNN",
 "YNNNYNNY",
 "NNYNNYNN",
 "NNNNYNYN",
 "NNYNNNNY"}

Returns: 0.875
5)
    
{"YNNNNNNNNYNNNNNNNNNN",
 "NYNNNNNNNNNNNNNNNNNN",
 "NNYNNNNNNNYNNNNNYNNN",
 "NNNYNYNNNNNNNNYNNNNN",
 "NNNNYNNNNNNNNNYNNNNY",
 "NNNNNYNNNNNNNNNNNNNY",
 "NNNNYNYNYNNNNNNNNNNN",
 "NNNNNNNYNNNYYNNNNNNN",
 "NNNNNNNNYNNNNNNNNNNN",
 "YNNNNNNNNYNNNNNYNNNN",
 "NNNNNNNNNNYNNNNNNNNN",
 "NYNNNNNNNNNYNNNNNNNN",
 "NNNNNNNYNNNNYNNNNNNN",
 "NNNNNNNNNNNNNYNNNYNN",
 "NNNNNNNNNNNYNNYNNNYN",
 "NYNNNNNNNNNNNNNYNNNN",
 "NNYNNNNNNNNNNNNNYNNN",
 "NNNNNNNNNNNNNYNYNYNN",
 "NNNNNNNNYNYNNNNNNNYY",
 "NNNYNNNNNNNNNNNNNNNY"}
Returns: 0.75

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14424&pm=11304

Writer:

rng_58

Testers:

PabloGilberto , ivan_metelsky , soul-net

Problem categories:

Graph Theory