PROBLEM STATEMENT
The members of Congress are selecting one of several proposed bills, and you
are to write a method to predict which bill will win.
Each member has an ordering of which bills he prefers over other bills, and the
preferences of each Congressman are listed in the elements of the String[].
For example, if the possible bills are 'A', 'B', and 'C', and a certain
Congressman prefers 'C' the most, followed by 'A', and likes 'B' the least, his
entry in the String[] will be "CAB".
The String represents the agenda, or the order in which the bills are voted.
If the agenda has only one character, that character automatically represents
the winning bill. Otherwise, the first 2 characters of the String are the
first pair to be voted upon, the winner of that vote is paired against the 3rd
element of the String, etc. So if the String is "CADB", then Congress first
votes between bills 'C' and 'A'. If 'C' wins, the next vote will be between
'C' and 'D'. If 'D' wins that vote, the final vote will be between 'D' and
'B', and the winner of that vote is the Congress's final selection.
In addition, each Congressman knows the preferences of each other Congressman,
and the Congressmen vote strategically. In other words, they may not always
vote for the bill they prefer, if they believe that voting for their least
favorite bill will ultimately cause a final selection which they prefer. See
the examples.
Write a method getWinner which returns the winning bill, given the agenda and
the preferences of the Congressmen.
DEFINITION
Class: Congress
Method Name: getWinner
Parameters: String[] String
Returns: char
Method signature (be sure your method is public): char getWinner(String[]
preferences, String agenda);
NOTES
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- agenda contains between 1 and 50 characters, inclusive
- preferences contains an odd number of elements between 1 and 49, inclusive
- each element of preferences contains between 1 and 50 characters, inclusive
- agenda, and each element of preferences, contains only lowercase and
uppercase alphabetic characters ('a'-'z' and 'A'-'Z')
- each character appearing in agenda appears exactly once in each element of
preferences
- no character will appear more than once in an element of preferences
- characters appearing in an element of preferences need not appear in agenda,
and characters in agenda may be repeated
EXAMPLE
Suppose preferences = { "ABC", "BCA", "CAB" }, and agenda = "ABC". Then the
first vote is between 'A' and 'B', and the winner of that vote faces off
against 'C'.
Suppose 'A' wins the initial vote between 'A' and 'B'. Then the agenda for
the rest of the voting becomes "AC", so since a majority of Congressmen prefer
'C' to 'A', 'C' will be the overall winner. Similarly, if 'B' wins the initial
vote, the agenda for the rest of the voting is "BC", so since a majority prefer
'B' to 'C', 'B' will be the overall winner.
So when choosing between 'A' and 'B', the Congressmen know that voting for
'A' is essentially choosing 'C' as the overall winner, and voting for 'B' is
essentially choosing 'B' as the overall winner. So since a majority of
congressmen prefer 'B' to 'C', 'B' will be the group's choice.
More examples:
If preferences = { "ABDC", "CADB", "DBCA" } and agenda = "ACD", then getWinner
returns 'A'
If preferences = { "ABDC", "CADB", "DBCA" } and agenda = "BCD", then getWinner
returns 'D'
If preferences = { "ABDC", "CADB", "DBCA" } and agenda = "ABCD", then getWinner
returns 'A'
If preferences = { "Kxyz", "Kyzx", "Kzxy", "Kzxy", "Kzxy" } and agenda =
"xyzxyz", then getWinner returns 'z'
If preferences = { "G" } and agenda = "G", then getWinner returns 'G'