EllysTournament
TCO19 SRM 759 · 2019-05-28 · by espr1t
Problem Statement
Elly signed up for a table tennis tournament. There are N participants in the tournament, including her. Each participant has an ELO rating (i.e., a number approximating how good he or she is). For the purpose of this task we will assume that if two players with ELO ratings X and Y play against each other, the first player will win with probability X / (X + Y) and the second player will win with probability Y / (X + Y).
The tournament is played in rounds. In the beginning all participants sit in a single row. In each round two players sitting next to each other are chosen uniformly at random. The chosen players play a game. The loser of the game is eliminated from the tournament. (The players who were the loser's neighbors in the old row are now each other's neighbors in the new row.) After playing N-1 rounds (each consisting of a single game) a single person will remain. This person is the winner of the tournament.
It is the beginning of the tournament.
The
Notes
- Your return value must have an absolute or a relative error at most 1e-9.
- All random events in the tournament are mutually independent.
Constraints
- N will be between 1 and 500, inclusive.
- K will be between 1 and N, inclusive.
- ratings will contain exactly N elements.
- Each element of ratings will be between 1 and 3000, inclusive.
4
2
{2103, 2019, 1911, 2331}
Returns: 0.17753927527829697
There are four people enlisted for the tournament. Ellys is the second from the left. In order to win, she has to beat the opponent standing to the left of her (because there is nobody else to the left that can beat him), which happens with chance 2019 / (2019 + 2103) = 0.489810771470. There are three possible options for the remaining two opponents: Elly beats both. This happens with chance 2019/(2019 + 1911) = 0.513740458015 for the first one and then 2019/(2019+2331) = 0.464137931034 for the second, for a total of 0.513740458015 * 0.464137931034 = 0.238446433272. The lower rated opponent can beat the higher rated one, and then Elly can beat him. This happens with chance 1911/(1911+2331) = 0.450495049505 for the lower rated to beat the higher rated and then 2019/(2019+1911) = 0.513740458015 for Elly to beat him for a total of 0.450495049505 * 0.513740458015 = 0.231437533066. The higher rated opponent can beat the lower rated one, and then Elly can beat him. This happens with chance 2331/(1911+2331) = 0.549504950495 for the higher rated to beat the lower rated and then 2019/(2019+2331) = 0.464137931034 for Elly to beat him for a total of 0.549504950495 * 0.464137931034 = 0.255046090816. Please note that (ignoring the match against the player to the left), either the first match is between the two opponents to the right (covering cases 2 and 3) or the first match is with Elly and the one with rating 1911. Thus, the total chance for Elly to win the tournament is: 0.489810771470 (to beat the player to the left) * ( 1/2 * 0.238446433272 (to beat both players to the right) + 1/2 * (0.231437533066 + 0.255046090816) (to beat only one of the players to the right) ) The result here is 0.489810771470 * (0.5 * 0.238446433272 + 0.5 * (0.231437533066 + 0.255046090816)) = 0.177539275278.
12
6
{42, 88, 13, 11, 71, 55, 32, 13, 72, 53, 37, 50}
Returns: 0.06697114679670368
20
13
{1543, 1230, 421, 1415, 1271, 1962, 2677, 2373, 2951, 114, 1379, 2015, 2211, 955, 2066, 2573, 2982, 296, 1730, 1591}
Returns: 0.05017297846158086
100
42
{2750, 2877, 2224, 186, 1398, 1084, 1542, 2770, 2288, 1078, 373, 2417, 476, 2968, 564, 1565, 1740, 1377, 2633, 287,
111, 823, 578, 520, 1708, 174, 144, 1295, 694, 678, 227, 2588, 371, 2740, 211, 1798, 82, 2385, 2979, 389,
2031, 1667, 2541, 2561, 1471, 2562, 974, 577, 286, 2836, 120, 2290, 185, 554, 2549, 1410, 1814, 1508, 2559, 1806,
2215, 1606, 2637, 1394, 1583, 1491, 2908, 529, 2556, 1034, 2770, 750, 2866, 2590, 1156, 2646, 2536, 958, 2862, 2565,
1027, 2744, 1160, 276, 2080, 322, 92, 790, 2452, 1859, 602, 2935, 2392, 1076, 2991, 1158, 2721, 868, 112, 29}
Returns: 0.003026484586204139
5
1
{42, 13, 17, 19, 23}
Returns: 0.4998653043354169
Submissions are judged against all 52 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EllysTournament with a public method double getChance(int N, int K, vector<int> ratings) · 52 test cases · 2 s / 256 MB per case