TopCoder problem "CountryWar" used in SRM 288 (Division I Level Three)



Problem Statement

    

Your country has several army units. There are several other countries, each of which is considered to be either an enemy or neutral, and each of which has several army units of its own.

A war consists of a series of battles. Once you initiate war with a neighboring country, war will proceed until either country has no remaining army units. After defeating another country in war, you own their territory. That is, their territory is added to yours forming one new larger territory. You can only initiate war with a country that borders some part of the territory you already own.

In any single round of battle, exactly one of the two countries involved will lose an army unit. If country A attacks country B, where A and B have a and b army units, respectively, then the probability that B will lose an army unit during the battle is a2/(a2+a*b+b2), otherwise A will lose an army unit. Note that a and b correspond to the total number of units in countries A and B, respectively.

Your goal is to defeat all of the enemy nations. While it is not required that you defeat any of the neutral nations, doing so may be necessary in order to reach other enemy countries (see examples 2 and 3).

You are given a String[] armies, describing each country. Each element of armies is formatted as "type units borders" (quotes added for clarity). type is one of 'Y', 'E' or 'N', indicating if the country is yours, an enemy, or neutral. units is an integer indicating how many army units are held by that country. borders is a space delimited list of zero or more integers, indicating the zero-based indices of adjacent countries.

You are to return a double indicating the probability that you can defeat all of your enemy nations without all of your army units being lost, assuming that you choose your order of attack optimally.

 

Definition

    
Class:CountryWar
Method:defeatAll
Parameters:String[]
Returns:double
Method signature:double defeatAll(String[] armies)
(be sure your method is public)
    
 

Notes

-The graph described by the bordering countries does not necessarily represent a planar graph.
-The graph described by the countries is not necessarily a connected graph (see example 5).
-Return value must be within 1e-9 absolute or relative error of the actual result.
 

Constraints

-armies will contain between 1 and 15 elements, inclusive.
-Each element of armies will be formatted as "type units borders" (quotes added for clarity).
-Each type will be 'Y', 'E' or 'N'.
-Exactly one element of armies will be of type 'Y'.
-Each units will be an integer between 1 and 20, inclusive, with no leading zeros.
-Each number represented in borders will be an integer with no leading zeros, between 0 and n-1, inclusive, where n is the number of elements in armies.
-Within a single element of armies, the numbers represented in borders will contain no duplicates.
-The borders described will be symmetric (that is, if a borders b, then b borders a).
 

Examples

0)
    
{"Y 1 1",
 "E 1 0"}
Returns: 0.3333333333333333
Here, you and your enemy each have exactly one army. Using the formula, 12 / (12 + 1*1 + 12) = 1/3.
1)
    
{"Y 2 1",
 "E 1 0"}
Returns: 0.7142857142857142
Here, superior strength is an advantage. In the first round of battle, there is a 4/7 chance of our enemy losing his only army. In the 3/7 chance that we get to a second round of battle, there is a 1/3 chance of winning. Thus, our total chances of winning are 4/7 + 3/7 * 1/3 = 5/7.
2)
    
{"Y 1 1",
 "E 1 0 2",
 "N 1 1"}
Returns: 0.3333333333333333
Our first battle is against our enemy, which we have a 1/3 chance of winning. Since we are not required to defeat neutral countries, we do not need to continue after that.
3)
    
{"Y 1 1",
 "N 1 0 2",
 "E 1 1"}
Returns: 0.1111111111111111
Here, we again have three countries lined up in a row, but this time, we are forced to first attack the neutral country, so that we can get to the enemy. We have a 1/3 chance of winning each war, thus a 1/9 chance of successfully completing both.
4)
    
{"Y 2 1 2",
 "E 2 0 2",
 "E 1 0 1"}
Returns: 0.16250944822373392
There are two enemy nations to attack, so our task is to determine which order of attack is optimal.
5)
    
{"Y 1",
 "E 1"}
Returns: 0.0
There is no path connecting you with your enemy, therefore you cannot possibly attack (or defeat) them.
6)
    
{"Y 1"}
Returns: 1.0
There is only you, and nobody to defeat, so you're guaranteed to be successful.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9809&pm=6068

Writer:

timmac

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Dynamic Programming, Graph Theory, Search