PROBLEM STATEMENT
Political parties often form coalitions for strategic reasons. A party can
sympathize with another party, be neutral towards another party, or dislike
another party. Sympathies, dislikes, and neutralities are neither symmetric
nor transitive. If party A sympathizes with party B then that does not imply
that party B sympathizes with party A. Also, if party A sympathizes with party
B and party B sympathizes with party C, then that does not imply that party A
sympathizes with party C. A coalition that includes party P* can be formed
whenever:
1) there exists some sequence of parties P0,P1,P2,...,P(n-1),Pn such that for
n>=1 and 0<=x<n
Px sympathizes with P(x+1). A party may appear more than once in this
sequence; see example 3.
2) there are no dislikes among any of the parties within that sequence.
3) Party P* is one of the parties within that sequence.
Given a party, return the size of the largest coalition of which that party is
a member.
In other words, find the sequence with the most parties that contains the given
party and return the amount of parties that appear in that sequence.
DEFINITION:
Class: Parliament
Method: coalition
Parameters: String[] String
Returns: int
Method Signature (be sure your method is public): int coalition(String[]
stances, String party);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
-stances contains between 1 and 15 elements inclusive.
-Each element in stances is of the following format <Party>:<Symp>|<Dis> where:
<Party> is a String of characters ('a'-'z', 'A'-'Z', '0'-'9') whose length is
between 1 and 20 characters, inclusive.
<Symp> is a comma separated list of parties that <Party> sympathizes with.
Each party that appears in <Symp> must be defined within stances.
<Dis> is a comma separated list of parties that <Party> dislikes.
Each party that appears in <Dis> must be defined within stances.
-<Party> cannot appear in <Symp> or in <Dis>.
-A party may only appear once in <Symp>.
-A party may only appear once in <Dis>.
-A party may only be defined once in stances.
EXAMPLES
Example 1: stances = {"L:R|D","R:|","D:|L,R"}
This means that: L sympathizes with R and dislikes D
R is neutral towards every party
D sympathizes with no one, and dislikes L and R.
Possible coaltions:
L-R, the size of this coalition is 2 parties.
If party = L. return 2, the largest coalition that L is part of is a coalition
of 2 parties.
If party = R. return 2, the largest coalition that R is part of is a coalition
of 2 parties.
If party = D. return 1. D is in a coalition with itself.
Example 2: stances = {"A:B|","B:C,D|","C:|", "D:|"}
Possible coalitions:
A-B B-C B-D A-B-C A-B-D
Notice that C and D cannot be in a coalition together because there is no way
to get from C to D or from
D to C through sympathies
Largest Coalition Sympathies Sequence
If party = A return 3. A-B-C or A-B-D A,B,C or A-B-D
If party = B return 3. A-B-C or A-B-D A,B,C or A-B-D
If party = C return 3. A-B-C A,B,C
If party = D return 3. A-B-D A,B,D
Example 3: stances = {"A0:B1|", "B1:C2,D3,E4|", "C2:B1|", "D3:C2|", "E4:|A0"}
Largest Coalition Sympathies Sequence (others
may be possible)
If party = A0 return 4. A0-B1-C2-D3 A0,B1,D3,C2
If party = B1 return 4. A0-B1-C2-D3 A0,B1,D3,C2
If party = C2 return 4. A0-B1-C2-D3 A0,B1,D3,C2
If party = D3 return 4. A0-B1-C2-D3 A0,B1,D3,C2
If party = E4 return 4. B1-C2-D3-E4 B1,C2,B1,D3,C2,B1,E4
Example 4: stances = {"N:S|G", "C:S|R,L", "S:C,N|R,L",
"D:S,G|R,L","G:L,C|R,D,N", "R:L|D,C", "L:R|C,S,D"}
Largest Coalition Sympathies Sequence (others
may be possible)
If party = N return 4. D-S-N-C D,S,N,S,C
If party = C return 4. D-S-N-C D,S,N,S,C
If party = S return 4. D-S-N-C D,S,N,S,C
If party = G return 3. G-C-S G,C,S
If party = R return 2. R-L R,L
If party = L return 2. R-L L,R