IHWCTie
SRM 846 · 2023-05-22 · by misof
Problem Statement
This problem is inspired by the group stage of the Ice Hockey World Championship.
The cut from the group stage to the playoffs is one of the most interesting moments of the World Championship.
In this problem there is a group of N country teams, numbered from 0 to N-1. These teams are competing for four playoff spots.
In the group stage of the championship each of the N teams plays each of the other N-1 exactly once (for a total of N(N-1)/2 games). Each game can either be decided in regular time or in overtime. If a team wins a game in regular time, they get 3 points and their opponent gets 0. If there is a win in overtime, the winner gets 2 points and the loser gets 1 point. Ties are not possible, each game is played until there's a winner.
The final standings of the group is obtained by sorting the teams according to their total number of points. The first four teams in this order advance to the playoffs.
The situation that generates the most emotions is when the fourth and fifth team in the standings are tied on the number of points and additional tiebreakers must be used to decide who makes the playoffs and who does not.
You are given the number N. Show that for a group of N teams there can be a tie between the last advancing and first non-advancing team by constructing one possible set of results of individual matches.
Let P[i][j] be the number of points obtained by team i for the match with team j. (Additionally, we define that P[i][i] = 0 for all i.) Find any valid array P such that the team with the fourth biggest point total has the same number of points as the team with the fifth biggest point total.
Return a
Notes
- You may assume that a solution always exists. Any valid solution will be accepted.
- Other team(s) may also be tied on points with the teams in fourth and fifth.
Constraints
- N will be between 5 and 50, inclusive.
5 Returns: "0330000330000333000333000"
6 Returns: "002223303133100013123033102002000010"
Below are the values from the return value formatted as the two-dimensional array P. The zeros on the main diagonal have been replaced by dashes for better readability. The value P[i][j] is in row i, column j. -02223 3-3133 10-013 123-33 1020-2 00001- Here are the final standings for this group: 1. team 1: 13 points (3+3+1+3+3) 2. team 3: 12 points (1+2+3+3+3) 3. team 0: 9 points (0+2+2+2+3) 4. team 4: 5 points (1+0+2+0+2) 5. team 2: 5 points (1+0+0+1+3) 6. team 5: 1 point (0+0+0+0+1) As required, the teams in fourth and fifth place are tied: they have 5 points each.
7 Returns: "0333000003330000033300000333300003333000033330000"
8 Returns: "0333000000333000000333000000333030000330330000303330000033333330"
9 Returns: "033330000003333000000333300000033330000003333300000333330000033333000003333300000"
Submissions are judged against all 46 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class IHWCTie with a public method string construct(int N) · 46 test cases · 2 s / 256 MB per case