Match summary

This Saturday's qualification round attracted most of the high-rated coders who needed to compete for a spot in Round 1, and most of them easily advanced. Since most of the sports champions will be crowned during the next couple of months (NBA, NHL, TCO), the problems today were sports-oriented, with igorsk, DmitryKorolev and lNVISIBLE finishing in the top three. Congratulations to them, and to the other 547 coders who were able to move on to Round 1, and good luck to everybody who is going to participate in the last Qualification Round!

The Problems

BuildATeam

Used as: Division One - Level One:

Value 250

Submission Rate 1163 / 1250 (93.04%)

Success Rate 1104 / 1163 (94.93%)

High Score sason for 249.36 points (1 mins 26 secs)

Average Score 203.77 (for 1104 correct submissions)

This problem checks your ability to quickly implement the algorithm given in the statement. First you need to create an array, with the i-th element of the array corresponding to the i-th team. Then, add the strengths of all the players to the teams corresponding to those players (read "to the corresponding elements of the array"). The maximal element of the array will be the strength of the strongest team.

C++ code follows:

int maximalStrength(vector <int> skills, int teams) {
    vector<int> v(teams, 0);
    sort(skills.begin(), skills.end());
    for (int i = 0; i < skills.size(); i++) {
        int a = i % (2 * teams);
        v[a < teams ? a : 2* teams - a - 1] += skills[i];
    }
    return *max_element(v.begin(), v.end());
}

BasketballStandings

Used as: Division One - Level Two:

Value 450

Submission Rate 804 / 1250 (64.32%)

Success Rate 729 / 804 (90.67%)

High Score radeye for 425.11 points (6 mins 57 secs)

Average Score 276.99 (for 729 correct submissions)

The solution to this problem consists of 3 parts - parsing the input, sorting the teams and constructing the output.

The parsing is quite easy since the team name, its numbers of wins and its number of losses are all separated by a single space. Sorting teams can be more difficult, since we need to compare each team separately. We can use a standard routine to do the sorting for us, though, if we use a small trick. As you can see from the statement (and easily prove), adding k to the team's number of wins and 2*k to team's numbers doesn't change the gap between this team and any other team, nor does it affect the team's position in the standings. Therefore, we can calculate the number of wins each team would have won if it would play, say, 1000 games, and sort the results according to this number.

For example, if a team has W wins and L losses, it needs to play (1000 - W - L) games more. We think it will win (1000 - W - L)/2 of them, making its total wins count equal to (W + (1000 - W - L)/2). To make sure we won't have any bugs with floating point precision, we multiply this number by 2 for all teams:

vector  constructTable(vector  teams) {
    vector > data;
    for (int i = 0; i < teams.size(); i++) {
        int n1 = teams[i].find(' ');
        int n2 = teams[i].find(' ', n1 + 1);
        int wins = atoi(teams[i].substr(n1 + 1, n2 - n1 - 1).c_str());
        int losses = atoi(teams[i].substr(n2 + 1).c_str());
        data.push_back(make_pair(-(2 * wins + 1000 - (wins + losses)), teams[i].substr(0, n1)));
    }
    sort(data.begin(), data.end());
    for (int i = 0; i < data.size(); i++)
        data[i].first *= -1;
    vector res;
    for (int i = 0; i < data.size(); i++) {
        char buf[50];
        int gap = data[0].first - data[i].first; // The gap between the best and the i-th teams
        sprintf(buf, "%s %i.%i", data[i].second.c_str(), gap/2, (gap % 2) * 5);
        res.push_back(string(buf));
    }
    return res;
}

BuildTheBestTeam

Used as: Division One - Level Three:

Value 1000

Submission Rate 174 / 1250 (13.92%)

Success Rate 59 / 174 (33.91%)

High Score simonenko for 790.87 points (15 mins 29 secs)

Average Score 556.64 (for 59 correct submissions)

During this overview, "captain" will mean "a captain which is not a captain of the powerplay team", "captains" will mean "all captains except the powerplay captain", and I will refer to the captain of the powerplay team explicitly.

To be able to solve this problem we need to predict the behavior of the captains. To make this easier, we will sort all players in the order preferred by these captains (players with higher usual skills first, with powerplay skills as a tiebreaker). After sorting the players in this order, a captain will always pick the first player among those who were not yet picked. As a consequence, if at some moment player i was not yet picked, then any player j (j > i) was either picked by the powerplay captain or was not picked at all (Statement 1).

Statement 2. The players of the optimal powerplay team can be picked in the order they would be picked by captains.
Proof. Let players P1 and P2 be chosen to the powerplay team and P2 be more preferred by captains. Let the powerplay captain choose those players in rounds R1 and R2 respectively, and R1 < R2. We will prove the powerplay captain can swap his picks and pick P2 in round R1 and P1 in round R2. The fact that player P2 was picked in round R2 means player P1 also wasn't picked until that round (see Statement 1), so the powerplay captain can pick him in round R2. Player P2 was not picked until round R2, therefore he obviously was not picked in any of the previous rounds, including round R1. Therefore, the powerplay captain would be able to pick him in round R1.

After the boring theoretical part we move to the implementation part. We suppose the powerplay captain will pick players in the order they are preferred by other captains. Therefore, if he picks player i in round j, then he can pick only players with indices less than i in all the following rounds. If f(a, b) is equal to the total powerplay strength of all players chosen to the powerplay team starting from round b, if player a was the last powerplay captain's pick. Then f(a, b) = Maximum of (powerplaySkills[i] + f(i, b + 1)) for all i > a. Also, we need to make sure that player i wasn't picked by the captains earlier. To do this we need to calculate the number K of picks made by all captains before the b-th pick of the powerplay captain, and make sure i is bigger than or equal to K. The java implementation of this approach follows:

(we suppose the players are already sorted)
    int f(int pos, int round) {
        if (round >= T) return 0;
        if (pos >= N) return -100000;
        int res = memo[pos][round];
        if (res != -1)
            return res;
        int q = minPicks(round);
        if (q > pos)
            return memo[pos][round] = f(q, round);
        res = 0;
        for (int i = pos; i < N; i++)
            res = Math.max(res, powerplaySkills[i] + f(i + 1, round + 1));
        return memo[pos][round] = res;
    }
    int minPicks(int round) {
        int res = 2 * teams * (round / 2);
        if (round % 2 == 1)
            res += (2 * teams - ind - 1);
        else
            res += ind;
        return res;
    }

By Olexiy
TopCoder Member