TopCoder problem "TheTournament" used in SRM 279 (Division II Level Two)



Problem Statement

    

You were hired to manage a forthcoming tournament. Each player will play against each of all the other players. According to the rules, the matches can be played in any order, but the audience will want to know the current leader at any point in time.

You will be given a String[] matches. All elements of matches will be in the form "playerA defeats playerB" (quotes for clarity only). Your method should return the leader after this set of matches. The leader is a player who has played at least one match and has the highest ratio of winning matches to total matches played. In case of a tie, return the player whose name comes first lexicographically. The players' names are case sensitive (i.e. uppercase letters are lexicographically earlier than lowercase letters).

 

Definition

    
Class:TheTournament
Method:findLeader
Parameters:String[]
Returns:String
Method signature:String findLeader(String[] matches)
(be sure your method is public)
    
 

Constraints

-matches will contain between 1 and 50 elements inclusive.
-Each element of matches will be in the form "playerA defeats playerB".
-In each element of matches playerA will differ from playerB.
-There will not be two elements of matches with the same players.
-Each playerA and playerB will contain between 1 and 20 letters ('A'-'Z', 'a'-'z'), inclusive.
 

Examples

0)
    
{"Ted defeats Kate", "Kate defeats Billy", "Ted defeats Billy"}
Returns: "Ted"
Ted wins all his games, but Kate and Billy have at least one defeat.
1)
    
{"Ted defeats Kate", "Kate defeats Billy", "Billy defeats Ted"}
Returns: "Billy"
All players have a 1/2 ratio of wins to total matches, so we should return the player whose name comes first lexicographically.
2)
    
{"Ted defeats Kate", "Kate defeats Billy", "Ted defeats Billy", "Tommy defeats Ted"}
Returns: "Tommy"
Tommy's ratio is 1/1, Kate's and Billy's ratio is 1/2 and Ted's ratio is 1/3. So, Tommy's ratio is the best.
3)
    
{"B defeats BA", "B defeats BB", "BC defeats B", "A defeats AB",
 "A defeats AC", "A defeats AD", "A defeats AE", "AF defeats A",
 "AG defeats A", "AB defeats AF", "AC defeats AG", "BB defeats BC"}
Returns: "A"
4)
    
{"defeats defeats def", "defeats defeats defe", "defe defeats ded", "defeat defeats defeats"}
Returns: "defeat"

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8076&pm=4649

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

String Parsing