Connection Status:
Competition Arena > UnfinishedTournament

UnfinishedTournament

SRM 724 · 2017-11-27 · by cgy4ever

SRM 724 · 2017-11-27 · by cgy4ever · Dynamic Programming, Graph Theory
Class Name: UnfinishedTournament
Return Type: String[]
Method Name: construct
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

A tournament is being played. There are n participants, numbered 0 through n-1. The tournament is a single round-robin tournament. In other words, each player is supposed to play each other player exactly once. There are no ties, each match will be won by one of the two players.

Some games may have already been played. You are given the information about the current state of the tournament in the String[] G. For each x and y, if x won the game against y, we have G[x][y] = 'W' and G[y][x] = 'L'. For the games that haven't been played yet we have G[x][y] = G[y][x] = '?'.

The winning rate of a player is the percentage of games they won. In particular, at the end of the tournament the winning rate of a player can be computed as the number of games they won divided by n-1.

The variance of a sequence is the average square distance of an element of the sequence from the mean of the sequence. Formally, suppose you have a sequence s[0], ..., s[n-1]. Then:
  • The mean of this sequence is mu(s) = ( s[0] + ... + s[n-1] ) / n.
  • The variance of this sequence is var(s) = ( (s[0]-mu(s))^2 + ... + (s[n-1]-mu(s))^2 ) / n.

Let r[0], ..., r[n-1] be the sequence of the winning rates of our n players at the end of the tournament. You are given a int x. Let v = x / 10^6. Your task is to find out whether var(r) can be very close to v. More precisely, your task is to find one possible way to fill in the results of all the remaining matches in such a way that at the end of the tournament abs( var(r) - v ) will be less than or equal to 0.02. If there is no such tournament, return {}. If there are multiple solutions, find any one of them and return it in the same format in which G is given.

Constraints

  • n will be between 2 and 20, inclusive.
  • G will contain exactly n elements.
  • Each element in G will contain exactly n characters.
  • Each character in G will be one of {'W', 'L', '?', '-'}.
  • For each i, G[i][i] = '-'.
  • For each i != j: {G[i][j], G[j][i]} = {'W', 'L'} or G[i][j] = G[j][i] = '?'.
  • x will be between 0 and 1,000,000, inclusive.
Examples
0)
{"-??",
 "?-?",
 "??-"}
20000
Returns: {"-WL", "L-W", "WL-" }

As x = 20000, we have v = 0.02. In other words, we want the variance to be in the closed interval [0, 0.04]. The sample output shown above corresponds to a tournament in which each player has one win: 0 defeated 1, 1 defeated 2, and 2 defeated 0. For this tournament the winning rates of the three players are {0.5, 0.5, 0.5}. The variance of this sequence is 0, which is still within the desired interval.

1)
{"-??",
 "?-?",
 "??-"}
166666
Returns: {"-WW", "L-W", "LL-" }

This time we want to have winning rates such that their variance is around v = 0.166666. The sample output describes a tournament in which the winning rates are r = {1, 0.5, 0} and thus var(r) = 1/6.

2)
{"-??",
 "?-?",
 "??-"}
100000
Returns: { }

For a tournament with three players the only two possible variances are those shown in Examples 0 and 1. There is no combination of results that would produce a variance in the interval [0.08, 0.12].

3)
{"-LW?",
 "W-??",
 "L?-W",
 "??L-"}
70000
Returns: {"-LWW", "W-LW", "LW-W", "LLL-" }
4)
{"-WL?WL??LL","L-???WWLW?","W?-??L?LL?","???-???LLL","L???-?LW?L","WLW??-?WWW","?L??W?-L?W","?WWWLLW-?W","WLWW?L??-?","W??WWLLL?-"}
54321
Returns: {"-WLLWLLLLL", "L-LLWWWLWW", "WW-LLLLLLL", "WWW-LWLLLL", "LLWW-LLWLL", "WLWLW-WWWW", "WLWWWL-LLW", "WWWWLLW-LW", "WLWWWLWW-W", "WLWWWLLLL-" }

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

Coding Area

Language: C++17 · define a public class UnfinishedTournament with a public method vector<string> construct(vector<string> G, int x) · 134 test cases · 2 s / 256 MB per case

Submitting as anonymous