Connection Status:
Competition Arena > RegularSeason

RegularSeason

SRM 207 · 2004-08-10 · by Olexiy

SRM 207 · 2004-08-10 · by Olexiy · Brute Force, Simple Math, Sorting
Class Name: RegularSeason
Return Type: String[]
Method Name: finalStandings
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

A new basketball season will start this autumn, and you want to predict its results. You have been watching the tournaments for ages and following the teams closely, so you can exactly determine the probability that a particular team will win a match vs some other team. Now you want to know, given these probabilities, how many games each of the teams is expected to win in the upcoming tournament.

You will be given a String[], teams. Each element of teams will be formatted as "NAME P1 P2 ... PN", where NAME is the name of the team, and P1, P2, ..., PN are the probabilities that this team will win home games against the 1st, 2nd, ..., Nth teams, respectively (the ith probability for the ith team will always be equal to 0). Ties are not possible due to the rules, so if the ith team has a probability p of beating the jth team in a home game, then the jth team has a probability of (100-p) of beating the ith team when the ith team is at home. Finally, you will be given an int rounds, which gives you the number of rounds in the championship. This means that team A will play 2*rounds games against each other team B (rounds as the visitors and rounds as the home team). You should predict the expected number of games each team will win in the tournament. You should round your prediction to the nearest integer (.5 rounds up).

The return value should be a String[], with each element formatted as "NAME NUMBER", where NAME is the name of the team, and NUMBER is the predicted number of wins. NUMBER should have no extra leading zeroes. The return value should be sorted by NUMBER in decreasing order (so the first element of the result will represent the most probable champion). If several teams have the same rounded number of wins, sort them using predicted number of wins before rounding (again in decreasing order); if a tie still remains, sort the tied teams by NAME in ascending alphabetical order.

Notes

  • If a team has a probability of p that it will win a particular game, then that game contributes p/100 to the expected number of games the team will win. However, it is advisable that you wait to divide by 100 until you have completed the summation of the expected number of wins (in order to avoid problems with floating point precision).

Constraints

  • teams will contain between 2 and 20 elements, inclusive.
  • No element of teams will contain more than 50 characters.
  • Each element of teams will be formatted as "NAME P1 P2 ... Pn".
  • Each NAME will contain only uppercase letters ('A'-'Z').
  • P1, P2, ..., Pn will each be an integer between 0 and 100, inclusive, with no extra leading zeros.
  • The ith probability of the ith element of teams will be 0.
  • rounds will be between 1 and 10, inclusive.
  • No two elements of teams will have the same NAME.
Examples
0)
{"A 0 10 50",
"B 100 0 100",
"C 50 10 0"}
5
Returns: { "B 19",  "A 6",  "C 6" }

Teams A and C are each expected to win half of their games against the other. A and C will both lose all their road games against team B. They are both expected to win 0.5 home games against B (0.1 * 5). Summarizing and rounding 0.5 up will give us the result: B - 19 wins. A - 6 wins. C - 6 wins. Be aware of rounding AFTER calculating the summary for each team. Also, the sum of predictions for all teams may be NOT equal to the sum of games played (there were 30 games played, but teams are predicted to have 31 wins after the rounding).

1)
{"SPURS 0 33 67 100",
"LAKERS 67 0 33 100",
"WOLVES 33 67 0 100",
"KINGS 0 75 75 0"}
2
Returns: { "SPURS 8",  "LAKERS 7",  "WOLVES 7",  "KINGS 3" }
2)
{"A 0 10 20 30 40 50 60 70 80 90",
"AA 90 0 10 20 30 40 50 60 70 80",
"AAA 80 90 0 10 20 30 40 50 60 70",
"AAAA 70 80 90 0 10 20 30 40 50 60",
"AAAAA 60 70 80 90 0 10 20 30 40 50",
"AAAAAA 50 60 70 80 90 0 10 20 30 40",
"AAAAAAA 40 50 60 70 80 90 0 10 20 30",
"AAAAAAAA 30 40 50 60 70 80 90 0 10 20",
"AAAAAAAAA 20 30 40 50 60 70 80 90 0 10",
"AAAAAAAAAA 10 20 30 40 50 60 70 80 90 0"}
10
Returns: { "A 90",  "AA 90",  "AAA 90",  "AAAA 90",  "AAAAA 90",  "AAAAAA 90",  "AAAAAAA 90",  "AAAAAAAA 90",  "AAAAAAAAA 90",  "AAAAAAAAAA 90" }

Don't forget about alphabetical order.

3)
{"DAAJN 0 56 19 81 59","PPERLJ 48 0 35 90 83","P 75 17 0 86 71","UNHWSYYO 51 30 1 0 9","MG 36 14 16 99 0"}
9
Returns: { "P 52",  "PPERLJ 49",  "DAAJN 36",  "MG 31",  "UNHWSYYO 12" }
4)
{"BZRDW 0 78 85 100 100 61 39 26","PEEVMENTK 30 0 84 2 37 9 68 5","ORT 0 92 0 27 27 59 69 84","MDJVANRL 73 48 20 0 75 47 46 95","YX 75 10 60 38 0 74 61 57","IMJWIL 36 15 22 42 81 0 52 99","ZHT 75 34 17 66 49 6 0 70","FTVKNX 50 14 95 14 91 69 30 0"}
1
Returns: { "BZRDW 9",  "MDJVANRL 8",  "IMJWIL 7",  "ORT 7",  "ZHT 7",  "PEEVMENTK 6",  "FTVKNX 6",  "YX 6" }

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

Coding Area

Language: C++17 · define a public class RegularSeason with a public method vector<string> finalStandings(vector<string> teams, int rounds) · 44 test cases · 2 s / 256 MB per case

Submitting as anonymous