Felix Halim .NET  
University Experience
IOI 2002 Yong In, Korea
ACM ICPC Regional Manila 2003
ACM ICPC Regional Manila 2004
ACM ICPC Regional Manila 2005
ACM ICPC Regional Kaohsiung 2006
ACM ICPC Regional Singapore 2007
ACM ICPC Regional Jakarta 2008 (ext)
ACM ICPC Regional Jakarta 2009 (ext)
ACM ICPC Regional Jakarta 2010
ACM ICPC Regional Jakarta 2012  Problem H
ACM ICPC Regional Jakarta 2013  Problem J (new!)
ACM ICPC World Final Tokyo 2007
Google India Code Jam 2005
Google India Code Jam 2006
Indonesia National Contest 2007
Indonesia National Contest 2008
Indonesia National Contest 2010
Facebook Hacker Cup 2011


ConquestProblem StatementYou 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 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. DefinitionClass: ConquestMethod: bestChance Parameters: int, vector Returns: double Method signature: double bestChance(int armies, vector (be sure your method is public) Notes
Constraints
Examples0) 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. 