TopCoder Statistics - Problem Statement

Problem Statement

You are playing a board game and have almost won. You have one large group of armies in one territory poised to eliminate your opponent, whose armies are scattered across three territories. To eliminate your opponent, you must reduce the number of armies your opponent controls to zero through a series of attacks. During an attack, your remaining armies attack one of your opponent's three territories from your starting territory. You may continue to make attacks as long as you have more than 1 army in your starting territory. During each attack, you may lose some armies, and your opponent may also lose some armies.

If, through a series of attacks, you are able to cause your opponent to lose all of his armies in one of his territories, you must move exactly one army into that territory from your starting territory. You may then continue to attack your opponent's other territories from your starting territory. The goal, of course, is to defeat all the armies in all three of your opponent's territories, and move a single army into each of them, while leaving at least one behind in your starting territory. For example, let's say that you had 10 armies and attacked a territory with only 3 armies. As you will see below, one possible outcome for this attack is that both you and your opponent lose a single army. Then, you have 9 armies left, and your opponent has 2 armies left in that territory. You may then attack him again, and a possible outcome is that your opponent loses both of his remaining armies. In this case, you must move one of your 9 armies into that territory, leaving you with 8. You may then move on to attacking your opponent's other territories.

The outcomes of the attacks are somewhat random, and there are different probabilities depending on the number of armies in your starting territory, and in the opponent's territory being attacked. The following table shows the probabilities of each of the potential outcomes. The outcome column contains two numbers. The first is the number of armies that you lose during the attack, and the second is the number of armies that your opponent loses during the attack. The probability column shows the probability of the given outcome for the specified numbers of armies in the two territories. For example, if you had more than 3 armies on your starting territory and attacked a territory that had only 1 army, you would have a 855 / 1296 probability of defeating that 1 army, and a 441 / 1296 probability of losing 1 of your armies. Any outcomes not listed have a probability of 0.

 attacking | defending |         |
 armies    | armies    | outcome | probability
-----------+-----------+---------+------------
 over 3    | over 1    | 2 - 0   | 2275 / 7776
 over 3    | over 1    | 1 - 1   | 2611 / 7776
 over 3    | over 1    | 0 - 2   | 2890 / 7776
 over 3    | 1         | 1 - 0   | 441 / 1296
 over 3    | 1         | 0 - 1   | 855 / 1296
 3         | over 1    | 2 - 0   | 581 / 1296
 3         | over 1    | 1 - 1   | 420 / 1296
 3         | over 1    | 0 - 2   | 295 / 1296
 3         | 1         | 1 - 0   | 91 / 216
 3         | 1         | 0 - 1   | 125 / 216
 2         | over 1    | 1 - 0   | 161 / 216
 2         | over 1    | 0 - 1   | 55 / 216
 2         | 1         | 1 - 0   | 21 / 36
 2         | 1         | 0 - 1   | 15 / 36

You are given an int, armies, indicating the number of armies you have to start with. You are also given a int[], opponent, with exactly three elements, containing the number of armies in your opponent's territories.

You are to return a double indicating the probability that you successfully defeat all of your opponent's armies, assuming that you always make the best decision as to which territory to attack each time.

Definition

Class:: Conquest
Method:: bestChance
Parameters:: int, int[]
Returns:: double
Method signature:: double bestChance(int armies, int[] opponent)
(be sure your method is public)

Notes

You may attack any one of your opponents territories that has armies remaining on it. You do not need to continue to attack a territory until your opponent's armies on that territory are eliminited. You could for example, attack territory 0, then territory 1, and then go back to territory 0.
Your solution must have an absolute or relative error of less than 1E-9.

Constraints

armies will be between 4 and 50, inclusive.
opponent will contain exactly 3 elements.
Each element of opponent will be between 1 and 20, inclusive.

Examples

4

{1, 1, 1}

Returns: 0.15907653892318244

You have 4 armies to start with and your opponent has 1 army in each of his three territories. Since you must move an army into each territory after defeating your opponent, your only hope is to not lose a single army in any of your attacks. First, you attack territory 0, and defeat that army without losing any of your own with a probability of 855 / 1296. You must move 1 army into that territory, so you then only have 3 armies to attack territory 1. You conquer this territory without loss with a probability of 125 / 216. Finally, you have only two armies left to attack territory 2, and you win with a probability of 15 / 36. From this, we find that the overall probability of conquering all three territories is 1603125 / 10077696, which is about 0.159.
10

{2, 2, 10}

Returns: 0.13552235780217273
30

{5, 5, 5}

Returns: 0.9857787020110442
5

{1,1,1}

Returns: 0.4365325355616998
50

{16,16,16}

Returns: 0.7305988362618165
4

{2,2,2}

Returns: 0.008975451446637736
4

{8,6,16}

Returns: 6.23383627729796E-8
7

{4,6,16}

Returns: 2.052395550665175E-4
7

{2,7,18}

Returns: 1.5195067943873136E-4
29

{19,8,16}

Returns: 0.11130965040400498
11

{1,16,15}

Returns: 0.0010747000577804454
45

{8,15,16}

Returns: 0.829539157368064
26

{14,14,19}

Returns: 0.024339854875629348
21

{10,20,13}

Returns: 0.010037963670491562
21

{3,7,9}

Returns: 0.6294691855152335
37

{2,4,1}

Returns: 0.9999983209491552
45

{5,2,1}

Returns: 0.9999999104361155
25

{15,11,3}

Returns: 0.36828866404051586
5

{19,18,10}

Returns: 5.623315192388467E-10
16

{14,1,14}

Returns: 0.04025533074335226
34

{10,5,9}

Returns: 0.9198047487632206
26

{7,7,14}

Returns: 0.46438471423762295
7

{15,10,8}

Returns: 1.2162938277826111E-5
30

{19,6,2}

Returns: 0.703841791620009
42

{15,18,13}

Returns: 0.499204461872644
50

{20,20,20}

Returns: 0.35710825665516377
34

{13,5,5}

Returns: 0.9366658399550893
24

{9,8,6}

Returns: 0.5904126187219203
50

{10,14,2}

Returns: 0.9976469231764389
16

{15,7,14}

Returns: 0.006460442552087359
23

{4,14,3}

Returns: 0.6385780173259248
50

{11,16,17}

Returns: 0.8339982255543399
38

{5,16,19}

Returns: 0.5489575671023345
19

{6,12,9}

Returns: 0.15368057790588058
14

{15,7,7}

Returns: 0.016071638827597445
11

{13,9,9}

Returns: 0.0014661325555503709
38

{13,7,10}

Returns: 0.8749130883822627
50

{4,2,7}

Returns: 0.9999984706569303
4

{12,12,13}

Returns: 4.6710317251921655E-9
36

{8,20,3}

Returns: 0.7926487027635862
45

{8,10,5}

Returns: 0.9967350791480352
33

{10,19,14}

Returns: 0.23308730599650923
45

{6,18,11}

Returns: 0.9116246557793081
21

{20,11,16}

Returns: 0.0037409018761809386
39

{6,8,8}

Returns: 0.9868205694027179
50

{20,20,20}

Returns: 0.35710825665516377
10

{2, 2, 10 }

Returns: 0.13552235780217273
30

{5, 5, 5 }

Returns: 0.9857787020110442
4

{1, 1, 1 }

Returns: 0.15907653892318244
5

{2, 3, 9 }

Returns: 0.0030354631337779396
12

{1, 4, 9 }

Returns: 0.2906081598325992
5

{2, 2, 10 }

Returns: 0.002310671871307599
19

{12, 12, 10 }

Returns: 0.03699429788001363
30

{6, 5, 6 }

Returns: 0.9695985064501025
5

{2, 3, 5 }

Returns: 0.01870592810594287

Statistics

Problem Statement for "Conquest"

Problem Statement

Definition

Notes

Constraints

Examples