Connection Status:
Competition Arena > RoundRobin

RoundRobin

SRM 140 · 2003-03-26 · by Yarin

SRM 140 · 2003-03-26 · by Yarin
Class Name: RoundRobin
Return Type: int[]
Method Name: order
Arg Types: (vector<string>)
Problem Statement

Problem Statement

In a Round Robin tournament everyone plays everyone else exactly once. The only valid results will be a win, a draw or a loss. A win is awarded with 2 points, a draw 1 point and a loss 0 points. Given a table containing all the results in the tournament, you are to determine the placement of each player.

The crosstable will be given as a String[], where character i in element j (both zero based) is the result of player j against player i. The character can be either '2' (player j won against player i), '1' (draw) or '0' (player j lost against player i). Of course, a player doesn't play against himself, so character i in element i will always be a '-'.

For example, the crosstable in a tournament with three players can look like this:

{"-02",
 "2-1",
 "01-"}

In this tournament, player 0 lost against player 1 and won against player 2, player 1 won against player 0 and drew against player 2 while player 2 lost against player 0 and drew against player 1.

A point group is a set of players with the same total points. The first point group is the set of players with the highest total points, etc. If a tournament has 6 players, getting 7, 2, 4, 5, 7, and 5 points respectively, there are four point groups: the first point group consists of player 0 and 4, the second of player 3 and 5, the third of player 2 and the fourth of player 1.

To determine the placement of the players, the following sorting keys are used (in this order):

  1. Highest points against all players.
  2. Highest points against all players except those in the last point group.
  3. Highest points against all players except those in the last two point groups.
  4. ...
  5. Highest points against all players in the first point group.
  6. Lowest player index.

Create a class RoundRobin which contains the method order which takes as input a String[] results and returns a int[] containing the placement of the players in the tournament. The first element in the return value should be the winner of the tournament, etc. The first player is considered to be number 0, the second number 1, and so on.

Constraints

  • results will contain between 1 and 50 elements, inclusive.
  • Each element in results will contain the same number of characters as the number of elements in results.
  • Each element in results will only contain the characters '-', '0', '1' and '2'.
  • Character i in element i in results will be a '-', and no other character in results will be a '-'.
  • If character i in element j in results is '0', then character j in element i in results is '2'.
  • If character i in element j in results is '2', then character j in element i in results is '0'.
  • If character i in element j in results is '1', then character j in element i in results is '1'.
Examples
0)
{"-21112",
 "0-2221",
 "10-022",
 "102-01",
 "1002-2",
 "01010-"}
Returns: { 1,  0,  2,  4,  3,  5 }

The points for the 6 players are 7, 7, 5, 4, 5 and 2 respectively. We thus have 4 point groups (we denote them 2p, 4p, 5p, 7p). To separate player 0 and 1 who both got 7 points against all other opponents, we check how much they got against all players in the point groups 4p, 5p and 7p. Player 0 got 5 points and player 1 got 6 points against those, so player 1 is placed before player 0. To separate player 2 and 4 who both got 5 points, we repeat the procedure. Against those in point groups 4p, 5p and 7p they both got 3 points, so they're still tied. Against those in point groups 5p and 7p, player 2 got 3 points while player 4 only got 1 point, so player 2 is placed before player 4. Thus the ordering becomes 1, 0, 2, 4, 3, 5.

1)
{"-2110",
 "0-211",
 "10-12",
 "111-1",
 "2101-"}
Returns: { 0,  1,  2,  3,  4 }

All players got 4 points, so everyone is in the same point group. Thus the only way of separating the players is by player index.

2)
{"-1102121",
 "1-010200",
 "12-00100",
 "212-2201",
 "0220-011",
 "10102-11",
 "022211-0",
 "1221112-"}
Returns: { 3,  7,  0,  6,  5,  4,  1,  2 }
3)
{"-12122111001121",
 "1-1012210221111",
 "01-010002021210",
 "122-22001100121",
 "0110-1121112112",
 "00201-111102122",
 "102211-12000111",
 "1122011-0011111",
 "12011102-212102",
 "202111220-11012",
 "2002122111-0002",
 "11120021012-100",
 "110111111221-01",
 "0110101121222-0",
 "11210011000212-"}
Returns: { 8,  1,  0,  9,  4,  3,  12,  10,  13,  5,  6,  7,  11,  14,  2 }
4)
{"-"}
Returns: { 0 }

Only a single player is possible.

Submissions are judged against all 58 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RoundRobin with a public method vector<int> order(vector<string> results) · 58 test cases · 2 s / 256 MB per case

Submitting as anonymous