Problem Statement |
| |
The Total Conquest soccer league is about to begin its season ending tournament next week. The tournament will be a single elimination tournament, meaning that a team that loses is immediately eliminated from the tournament. To set up the tournament, each team will be assigned a unique seed prior to the start of the tournament (starting from 0); the number of teams in the tournament will be a power of 2. The following algorithm in pseudocode is then used to determine pairings:
SetSeeds(String[] Teams)
{
LET N = the number of teams left
IF(N==1)
The tournament is over
ELSE
Pair all teams such that their seeds sum to N-1.
Assume the lower seeded team wins each game.
Call SetSeeds(Winners)
}
For example, in an 8 team tournament, the first round games would be between 0-7, 1-6, 2-5, and 3-4. In the second round, the games would be between 0-3 and 1-2, with the winners meeting in the final.
Due to the format of the tournament, it is possible for a second round game to be played before all first round games have finished; a game may be started as long as both teams have advanced to the correct round. In the above tournament, for instance, if teams 0 and 3 win their opening round games, they may play their second round game prior to the game between 2-5.
You have been given a list of the teams in the tournament; you should concatenate the elements of teams to form a single space separated list of teams in the tournament with no leading or trailing spaces. You also will be given games; this should be concatenated to form a single space separated list representing the games played. Each game will be represented by two words; the first will be the name of the winning team, and the second will be the team that lost that game. The games may be listed in any order, but all games that have been played in the tournament so far will be listed.
You know that all games played in the tournament will be won by the team with the lower numbered seed. Assign the seeds to teams consistent with the games played; if there is more than one way to do this, select the lexicographically first among them (see Notes). Return a String[] containing the same number of elements as seeds; the i-th element in the return should correspond to the team name of the team that has been assigned seed seeds[i]. If the games listed in games do not represent a valid set of games in a tournament, return an empty String[].
|
| |
Definition |
| | | Class: | TournamentSeeding | | Method: | getSeeds | | Parameters: | String[], String[], int[] | | Returns: | String[] | | Method signature: | String[] getSeeds(String[] teams, String[] games, int[] seeds) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | An assignment of teams A is lexicographically earlier than B if, for some seed i, A[i] < B[i], and for all seeds j < i, A[j]=B[j]. |
| - | When comparing two Strings, digits ('0'-'9') come before letters. |
| - | A String C is less than D if C is a prefix of D, or if, for some character at index i, C[i] < D[i], and for all j < i, C[j]=D[j]. |
| |
Constraints |
| - | teams will contain between 1 and 50 elements, inclusive. |
| - | Each element of teams will contain between 1 and 50 characters, inclusive. |
| - | teams will contain only uppercase letters ('A'-'Z'), digits ('0'-'9') and spaces (' '). |
| - | The number of teams listed in teams will be a non-negative power of 2. |
| - | There will be no duplicate team names in teams. |
| - | teams will be formatted as described in the statement. |
| - | Each name in teams will contain between 1 and 20 characters, inclusive. |
| - | games will contain between 0 and 50 elements, inclusive. |
| - | Each element of games will contain between 1 and 50 characters, inclusive. |
| - | When concatenated, games will contain a single space separated list of names from teams, with no leading or trailing spaces. |
| - | When concatenated, games will contain an even number of team names. |
| - | No team will play against itself in games. |
| - | There will be no repeated game listed in games. |
| - | seeds will contain between 1 and 50 elements, inclusive. |
| - | Each element of seeds will be between 0 and N-1, inclusive, where N is the number of teams in teams. |
| |
Examples |
| 0) | |
| | {"CELTICS ", "LAKER", "S SPURS PISTONS"} | {"CELTICS LAKERS CELTICS PISTONS LAKERS SPURS"} | {0, 1, 2, 3} |
| Returns: {"CELTICS", "LAKERS", "SPURS", "PISTONS" } | | The final rounds of the 2008 NBA playoffs. The first round games were CELTICS-PISTONS and LAKERS-SPURS, and the CELTICS beat the LAKERS in the final. |
|
|
| 1) | |
| | {"GIANTS PATRIOTS CHARGERS PACKERS"} | {"PATRIOTS CHARGERS"} | {3, 2, 1, 0} |
| Returns: {"PACKERS", "CHARGERS", "PATRIOTS", "GIANTS" } | Here is an incomplete tournament with only one game played. There are several possible seedings, but the lexicographically earliest seeding is:
0) GIANTS
1) PATRIOTS
2) CHARGERS
3) PACKERS
|
|
|
| 2) | |
| | {"REDSOX PHILLIES METS DODGER",
"S ORIOLES BLUEJAYS CUBS AN",
"GELS"} | {"METS ANGELS",
" METS CU",
"BS ORIO",
"LES ANGELS"} | {0, 1, 2, 3, 4, 5, 5, 5} |
| Returns: { } | | In a single elimination tournament, it is impossible for the ANGELS to lose twice. |
|
|
| 3) | |
| | {"REDSOX PHILLIES METS DODGER",
"S ORIOLES BLUEJAYS CUBS AN",
"GELS"} | {"METS ANGELS",
" METS CU",
"BS CU",
"BS DODGERS REDSOX PHILLIES"} | {0, 1, 2, 3, 4, 5, 6, 7} |
| Returns:
{"BLUEJAYS",
"METS",
"CUBS",
"REDSOX",
"PHILLIES",
"DODGERS",
"ANGELS",
"ORIOLES" } | | In this tournament, the second round game between the METS and CUBS was played before the BLUEJAYS-ORIOLES game from the first round. |
|
|
| 4) | |
| | {"A B C D E F 8 H I 3 9 L 4 N O P"} | {"P A B H D C D E E N"} | {0, 2, 0, 0, 3, 4, 7, 2} |
| Returns: {"3", "8", "3", "3", "D", "E", "P", "8" } | | Note that the same seed may be requested multiple times. |
|
|
| 5) | |
| | {"A B C D E F G H"} | {"A B C D A C E F"} | {0, 1, 2, 3, 4, 5, 6, 7} |
| Returns: {"A", "E", "G", "C", "D", "H", "F", "B" } | |
|
| 6) | |
| | {"NEWYORKISLANDERS"} | {} | {0} |
| Returns: {"NEWYORKISLANDERS" } | |
|