TopCoder problem "ColorfulBalls" used in TCO08 Semifinal 2 (Division I Level Three)



Problem Statement

    

We have a bag that contains N balls of different colors. In each turn we pick two balls from the bag, one after another, and paint the second one with the first one's color. After the paint dries, we put both balls back into the bag and shuffle its contents.

You are given a String colors describing the initial colors. More precisely, each character in colors corresponds to a single ball. Balls represented by equal characters have the same color.

Return the expected number of turns until all the balls have the same color.

 

Definition

    
Class:ColorfulBalls
Method:expectedStepCount
Parameters:String
Returns:double
Method signature:double expectedStepCount(String colors)
(be sure your method is public)
    
 

Notes

-The returned value must be accurate to within a relative or absolute value of 1E-9.
 

Constraints

-colors will contain between 1 and 24 characters, inclusive.
-Each character in colors will be an uppercase letter ('A'-'Z').
 

Examples

0)
    
"AB"
Returns: 1.0
In the first turn we will paint one ball with the other's color, and we are done.
1)
    
"Q"
Returns: 0.0
If there is just a single ball, all balls already have the same color, and thus the correct answer is zero.
2)
    
"AAAAAAA"
Returns: 0.0
All balls already have the same color.
3)
    
"ZCZ"
Returns: 3.0
4)
    
"KLM"
Returns: 4.0
After the first turn we are sure to get a situation that's similar to the one in the previous example.
5)
    
"AAABB"
Returns: 11.666666666666668

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12016&pm=8782

Writer:

misof

Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming, Math