TopCoder problem "NoMo" used in TCO '03 Semifinals 3 (Division I Level Two)



Problem Statement

    Football announcers are always pontificating about the importance of momentum. Of course, whenever the team that doesn't have the momentum does something good, the explanation is that the momentum has shifted. We want to do a study of football games to determine how big a role momentum actually plays.

We define the "m-factor" to be the number of scores that immediately follow a score by the same team minus the number of scores that immediately follow a score by the opponent. So if "ABBAAAAAB" were the sequence of scores in a game between teams A and B, then the m-factor would be 5 - 3 = 2. (The 5 comes from one time that a score by B was immediately followed by another score by B and four times that a score by A was immediately followed by a score by A. Similarly, the 3 comes from the one BA and the two AB's that occur.)

But we have to be careful. A high m-factor will naturally occur if one team is just a lot better than the other. If only one team scores, no score will follow a score by the opponent. So to judge whether momentum played an important role, we have to compare the m-factor for a game to the random m-factor for the given number of scores by the two teams. For a game with n scores, the random m-factor is defined to be the average of the n! m-factors corresponding to the n! (not necessarily distinct) permutations of the scores. For example, the random m-factor of the game "ABA" is the average of the 6 m-factors corresponding to "ABA", "AAB", "BAA", "BAA", "AAB", "ABA".

Create a class NoMo that contains a method momentum that is given a String game giving the sequence of scores by teams A and B and that returns the m-factor for the game minus the random m-factor for that number of scores by A and B.

 

Definition

    
Class:NoMo
Method:momentum
Parameters:String
Returns:double
Method signature:double momentum(String game)
(be sure your method is public)
    
 

Notes

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

Constraints

-game will contain between 0 and 25 characters inclusive.
-Each character in game will be 'A' or 'B'.
 

Examples

0)
    
"AAAAAAA"
Returns: 0.0
The m-factor is 6, but so is the random m-factor for 7 scores against 0 scores.
1)
    
"AAB"
Returns: 0.6666666666666666
The m-factor for this game is 0. The six permutations with their m-factors are: AAB = 0, AAB = 0, ABA = -2, ABA = -2, BAA = 0, BAA = 0 so the random m-factor for 2 scores against 1 is -4/6. Thus we return 0 - (-4/6) = .6666666... So momentum played a positive role in this game.
2)
    
"AAABBBBB"
Returns: 5.5
3)
    
""
Returns: 0.0
4)
    
"ABABABABABABABABABABABABA"
Returns: -23.04

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4708&pm=1912

Writer:

dgoodman

Testers:

lbackstrom , schveiguy , vorthys

Problem categories:

Brute Force