Get Time

   Problem Statement  

 Problem Statement for RockPaperScissors

Problem Statement


Rock-paper-scissors is a famous hand game played by two people. In this game, each of the players forms one of three possible hand gestures: rock, paper, or scissors. Both players do so at the same time, and they show their gesture to the opponent. The result of the game is determined by the two gestures shown. If they are the same, the game is a draw. Otherwise, the winning player is determined by the following rules:

  • Rock defeats scissors.
  • Scissors defeat paper.
  • Paper defeats rock.

In this problem, you are going to play rock-paper-scissors against a bag of dice. There are N dice in the bag. Each dice has some faces that show a picture of a rock, others with a picture of paper, and the remaining faces show scissors. On the outside, all dice look the same, so you cannot distinguish between them. However, on the inside each die can be biased in a different way. That is, if you roll a particular die, the probability of getting each of the three gestures is not necessarily uniform.

Your game will take N turns. The game starts with all N dice inside the bag. In each turn, you first choose a gesture you want to play. Then you choose a random die from the bag and roll it to generate your opponent's move. The die is then thrown away. (Hence, after all N turns are over, the bag will be empty, and you played against each die exactly once.)

The games you play against the dice are scored as follows:

  • For each win you get 3 points.
  • For each draw you get 1 point.
  • For each loss you get 0 points.

You are given three int[]s: rockProb, paperProb, and scissorsProb. For each i, when die number i is cast, the probability that it will choose rock is rockProb[i] / 300.0. Similarly, paperProb[i] / 300.0 and scissorsProb[i] / 300.0 are the probabilities of getting paper and scissors on die i.

Your task is to find the strategy for this game that maximizes the expected total number of points you get. Compute and return the best possible expected score.



Parameters:int[], int[], int[]
Method signature:double bestScore(int[] rockProb, int[] paperProb, int[] scissorsProb)
(be sure your method is public)


-Your return value must have a relative or an absolute error of less than 1e-9.


-rockProb will contain between 1 and 50 elements, inclusive.
-paperProb and scissorsProb will each contain the same number of elements as rockProb.
-Each element of rockProb, paperProb and scissorsProb will be between 0 and 300, inclusive.
-For each i, rockProb[i]+paperProb[i]+scissorsProb[i] will be exactly 300.


{100, 100, 100}
{100, 100, 100}
{100, 100, 100}
Returns: 3.999999999999999
In this case, all the given dice are uniform. Therefore, your strategy does not matter. In each turn, your expected score is 3*(1/3) + 1*(1/3) + 0*(1/3) = 4/3. The total expected score is therefore 3 * 4/3 = 4.
Returns: 3.0
There is only one die, and it always shows rock. You should choose paper and you are guaranteed to win and score 3 points.
{300, 0,   0}
{0,   300, 0}
{0,   0,   300}
Returns: 6.333333333333332
In your first turn the probability of seeing each gesture is the same. Thus regardless of your choice, your expected score for this turn is 4/3. However, in the second turn you already know which die has been removed from the bag. This helps you play better. For example, if the first die showed rock, you know that only paper and scissors are left. The optimal strategy in this situation is to choose scissors: with probability 1/2 you win, and with probability 1/2 you draw. Thus the expected score for the second turn is 3*(1/2) + 1*(1/2) = 2. In the third turn you know what to play to win. The expected total score is 4/3 + 2 + 3 = 6.333333333.
{100,  0}
{200, 100}
{0,   200}
Returns: 3.7222222222222223
Returns: 149.00000000000003

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 579 Round 1 - Division I, Level Three