Felix Halim .NET  
Google 

Conquest

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 vector , 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, vector
Returns: double
Method signature: double bestChance(int armies, vector 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 have have an 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

0)

    
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.

1)

    
10
{2, 2, 10}
Returns: 0.13552235780217273

2)

    
30
{5, 5, 5}
Returns: 0.9857787020110442

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)2003, TopCoder, Inc. All rights reserved.


© Felix Halim 2009 (Loaded in 0.00218 secs)