PROBLEM STATEMENT
A contest is held where players are pitted against each other in a series of
1-on-1 matches. The results of each match can be player1 won, player1 lost, or
the players tied. Given just the list of match results, it is necessary to
rank the players based on THE RULES (see below) and return their names in
sorted order with the first player at index 0.
Match results are reported as "<player1> <status> <player2>".
<player1> and <player2> are the player's names.
<status> is one of the following "WON", "LOST", or "TIED" (without the double
quotes).
The process for sorting the players is as follows:
Initially all players are in a single unsorted group. Groups may get divided
into smaller groups. For any group that has two or more players in it, use the
rules listed below to divide it into two smaller groups. Continue dividing
groups until there is exactly 1 player in each group.
When choosing which rule to use, you must use the first rule that does not
apply to the entire group. Once a rule is found, the old group is replaced by
two new groups. All the players in the old group that meet the condition are
placed into the first new group, and the remaining players from the old group
are placed into the second new group. The players in the first new group are
now considered to be sorted before the players in the second new group.
THE RULES
Players are sorted before the remainder of their group if, when compared to the
other players in their group:
1) the players have the most wins.
2) the players have the most ties.
3) the players have the most wins vs (just players that have already been
sorted before this group).
4) the players have the most ties vs (just players that have already been
sorted before this group).
5) the players have the most wins vs (just the other players in this group).
6) the players have the most ties vs (just the other players in this group).
7) the players appear at the lowest index* in the results (as either player1
or player2).
8) the player is listed as player1 when both players appear at the same index.
DEFINITION
Class Name: OneOnOne
Method Name: sort
Parameters: String[]
Returns: String[]
Method signature (be sure your method is public): String[] sort(String[] results)
Each results String is in the format "<player1> <status> <player2>".
<player1> and <player2> consist solely of uppercase letters (A-Z) with at least
1 and at most 10 letters.
<status> is one of the following "WON", "LOST", or "TIED" (without the double
quotes).
The status indicates if <player1> won, lost, or tied the match.
returns a sorted String[] of player names with the first player at index 0.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
* results has between 1 and 12 elements, inclusive.
* Each results String has the format "<player1> <status> <player2>".
* <player1> is 1 to 10 uppercase letters (A-Z).
* <status> is either "WON", "LOST", or "TIED" (without the double quotes).
* <player2> is 1 to 10 uppercase letters (A-Z).
* players are identified by name. Two different players may NOT have the same
name.
* <player1> and <player2> must be different players.
Example 1:
results = {"A LOST B","A WON C","B LOST C"}
Our initial group is {A B C}
Checking rule 1, we find that A, B, and C all have 1 win, so we move on to the
next rule.
Checking rule 2, we find that A, B, and C all have 0 ties, so we move on to the
next rule.
Checking rule 3, we find that A, B, and C all have 0 wins vs (playes in groups
sorted before this group), since there aren't any groups before this one.
Checking rule 4, we find that A, B, and C all have 0 ties vs (playes in groups
sorted before this group), since there aren't any groups before this one.
Checking rule 5, we find that A, B, and C all have 1 win vs (the other players
in this group).
Checking rule 6, we find that A, B, and C all have 0 ties vs (the other players
in this group).
Checking rule 7, we find that A and B have a lowest index of 0, while C has a
lowest index of 1.
So we move A and B before C. Our new groups are {A B} {C}.
Starting over at rule 1 for group {A B}, we find A and B still have 1 win.
Checking rule 2, A and B still have 0 ties.
Checking rule 3, A and B have 0 wins vs just those players sorted before them
(since there aren't any groups before them).
Checking rule 4, A and B have 0 ties vs just those players sorted before them.
Checking rule 5, A has 0 wins vs other players in this group (namely B), while
B has 1 win.
So we move B before A (and the both remain before C) and have a new group
ordering of {B}{A}{C}.
Since there aren't any groups with two or more players, we return {"B","A","C"}
Example 2:
results = {
"WOW WON ZAP",
"ZAP WON BANG",
"POW TIED BANG",
"BANG LOST WOW",
"WOW TIED POW",
"POW LOST ZAP" }
The initial group is {BANG POW WOW ZAP}
Using rule 1 (wins), BANG has 0, POW has 0, WOW has 2, and ZAP has 2.
So WOW and ZAP are put into the first group and BANG and POW in the second,
giving {WOW ZAP}{BANG POW}.
At this point either group may be examined.
Looking at {WOW ZAP}, they both have 2 wins (rule 1), but for ties (rule 2) WOW
has 1 and ZAP has 0.
So the group is split with WOW in the first group and ZAP in the second, giving
{WOW}{ZAP}{BANG POW}.
Looking at {BANG POW}, both have 0 wins (rule 1), but for ties (rule 2) BANG
has 1 and POW has 2.
So the group is split with POW in the first group and BANG in the second,
giving {WOW}{ZAP}{POW}{BANG}.
All groups have only one player, so the return is {"WOW","ZAP","POW","BANG"}
Example 3:
results = {
"A WON B",
"B WON C",
"C WON D",
"D WON E",
"E WON A" }
The initial group is {A B C D E}
Rule 7 moves A and B before the rest - {A B}{C D E}
For the {A B} group, rule 1 results in {A}{B}{C D E}
For the {C D E} group, rule 3 applies to E and results in {A}{B}{E}{C D}
For the {C D} group, rule 3 now applies to D, so the final order is
{A}{B}{E}{D}{C}
return {"A","B","E","D","C"}
Example 4:
results = {
"A WON B",
"A WON C",
"A WON D",
"B TIED C",
"B WON D",
"C WON D" }
Start with {A B C D}
Rule 1: {A}{B C D} because A has 3 wins (vs 1 for B and C and 0 for D).
Rule 5: {A}{B C}{D} because B and C have 1 win vs (BCD) and D has 0.
Rule 7: {A}{B}{C}{D} because B appears at index 0 and C at index 1.
return {"A","B","C","D"}
Example 5:
results = {
"A WON B",
"A TIED C",
"A LOST D",
"B WON C",
"B TIED D",
"C WON D" }
Start with {A B C D}
Rule 7: {A B}{C D} because A and B are at index 0.
Rule 3: {A B}{D}{C} because D has 1 win vs (AB) and C has 0.
Rule 5: {A}{B}{D}{C} because A has 1 win vs (AB) and B has 0.
return {"A","B","D","C"}