TopCoder problem "CoinGame" used in SRM 287 (Division I Level Three)



Problem Statement

    

Two players play a simple game with a coin.

Given is a set S. Each element of S is a sequence of heads and tails, and all the sequences have the same length.

The first player starts the game by choosing a sequence from S. Then the second player chooses a different sequence from S. A fair coin is then thrown repeatedly until one of the chosen sequences appears as a set of consecutive throws. The player that has chosen this sequence wins.

You are given a String[] sequences containing the allowed sequences encoded as strings of 'H's and 'T's ('H' represents a head, 'T' represents a tail). Return the probability that the first player will win this game, given that both players play optimally.

 

Definition

    
Class:CoinGame
Method:bestProbability
Parameters:String[]
Returns:double
Method signature:double bestProbability(String[] sequences)
(be sure your method is public)
    
 

Notes

-The returned value must be accurate to 1e-9 relative or absolute.
 

Constraints

-sequences contains between 2 and 50 elements, inclusive.
-Each element of sequences contains only uppercase 'H' and uppercase 'T' characters.
-Each element of sequences contains between 1 and 10 characters, inclusive.
-Each element of sequences contains the same number of characters.
-No two elements in sequences are equal.
 

Examples

0)
    
{"H", "T"}
Returns: 0.5
This game is as simple as it gets. The first player picks a head or a tail, then they flip a coin and look at the outcome. Each player has a 50% chance of winning this game.
1)
    
{"HHHHHHHHH", "TTTTTTTTT"}
Returns: 0.5000000000000011
Almost the same game, but quite a bit longer.
2)
    
{"HH", "HT"}
Returns: 0.5
This is another example of a fair game. Once a head occurs for the first time, the next throw decides which sequence will appear first.
3)
    
{"TTT", "HTT"}
Returns: 0.875

In this game, choice matters. The only way TTT can appear before HTT is if it appears in the first three throws. Otherwise the triplet we encounter immediately before seeing TTT for the first time is always HTT. Thus in all other cases HTT appears before TTT.

The first player knows this and he chooses HTT, which gives him a 7/8 chance of winning the game.

4)
    
{"HHH", "HHT", "HTH", "HTT", "THH", "THT", "TTH", "TTT"}
Returns: 0.33333333333333337
This game contains a wonderful paradox: being the first player is not always good.
5)
    
{"TTHTTHTTH", "HTTHTHHTT", "TTHHHHTHT", "TTTTTHTTT", "HHTTHTHHT"}
Returns: 0.5019379844961235

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9808&pm=6005

Writer:

misof

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Math