Qualification Round 2 Saturday, March 31, 2007 Match summaryThis Saturday's qualification round attracted most of the highrated 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 sportsoriented, 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 ProblemsBuildATeamUsed as: Division One  Level One: This problem checks your ability to quickly implement the algorithm given in the statement. First you need to create an array, with the ith element of the array corresponding to the ith 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: 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: vectorBuildTheBestTeam Used as: Division One  Level Three: 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 bth 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; } 
