JOIN
 Match Editorial
SRM 279
Wednesday, December 21, 2005

Match summary

The competition gathered 851 participants stimulated with perspective not only to earn additional rating points, but also cash prizes. Division 1 200 was very easy giving a chance to warm up before two others, which were much more difficult. The medium problem was above the average by difficulty, but the idea was pretty standard. The correct solution for the hard in addition was hard to guess, which explains the low success rate with only 12 correct submissions.

The winner is Petr with 1620.59, which is almost 300 points more than ACRush who get the second place with 1322.83. The third and the fourth are bmerry and misof correspondingly.

Division 2 winner is King_Bette followed by two newcomers chenll and zwdant.

Unfortunately because of a small technical problem this SRM does not influence the participant rating, but the prize money will be delivered to the winners as promised.

# The Problems

DancingSentence
Used as: Division Two - Level One:
 Value 300 Submission Rate 361 / 418 (86.36%) Success Rate 309 / 361 (85.60%) High Score veskok for 298.03 points (2 mins 18 secs) Average Score 253.23 (for 309 correct submissions)
Used as: Division One - Level One:
 Value 200 Submission Rate 381 / 382 (99.74%) Success Rate 370 / 381 (97.11%) High Score krijgertje for 199.59 points (1 mins 17 secs) Average Score 191.74 (for 370 correct submissions)

The solution to this problem is pretty straightforward. You just need to remember the case of the previous letter while iterating through the string. The spaces should be preserved as is. If the previous letter was lowercase, you need to uppercase the current one if necessary. And vice versa, if the previous letter was uppercase, you need to lowercase current one. Here is the top Java solution written by Googly:

``` public String makeDancing(String sentence) {
String ret = "";
boolean upper = true;
for (int i=0; i<sentence.length(); i++) {
char c = sentence.charAt(i);
if (c == ' ') {
ret += " ";
} else {
if (upper) {
ret += Character.toUpperCase(c);
} else {
ret += Character.toLowerCase(c);
}
upper = !upper;
}
}
return ret;
}
```

TheTournament
Used as: Division Two - Level Two:
 Value 500 Submission Rate 296 / 418 (70.81%) Success Rate 189 / 296 (63.85%) High Score chenll for 486.22 points (4 mins 48 secs) Average Score 309.49 (for 189 correct submissions)

The solution for this task is also straightforward. You need to calculate the total number of matches for each player and the number of matches each player won. The map container can be rather helpful for those calculations, though low constraint allow brute force solution run in time.

Here is a quite short solution written by Olexiy:

``` public String findLeader(String[] data) {
int bestPlayed = 1; // Games played by the best team found so far
int bestWon = -1; // Games won by the best team so far
String bestTeam = "";
for (int game = 0; game < data.length; game++) {
String team = data[game].split(" +")[0]; // Check the team which won the game-th game
int won = 0;
int played = 0;
for (int i = 0; i < data.length; i++) {
String[] s = data[i].split(" +");
if (s[0].equals(team)) {
played++;
won++;
}
if (s[2].equals(team)) played++;
}
if (won * bestPlayed > bestWon * played ||
(won * bestPlayed == bestWon * played && team.compareTo(bestTeam) < 0)) {
bestTeam = team;
bestPlayed = played;
bestWon = won;
}
}
return bestTeam;
}

```

CoinPiles
Used as: Division Two - Level Three:
 Value 1100 Submission Rate 70 / 418 (16.75%) Success Rate 31 / 70 (44.29%) High Score King_Bette for 905.81 points (13 mins 46 secs) Average Score 610.48 (for 31 correct submissions)

It is clear that the answer will be much less then 50. So we can look through all possible answers and for each candidate check if it is possible to arrange coins in that number of piles. Now we need to check the case with N piles. To check this case we do the following: sort the coin sizes, choose the N largest unique sizes and make them the top coins in each pile. Now we are going to place all remaining coins. We will do it in the following way: we will take the coins in the non-decreasing order and put 0 coins to the first pile (which already has the smallest top coin), 1 coin to the second pile, 2 to the third, etc. All remaining coins to the last pile. While putting the coins all the rules should be checked, and if at least one is violated, the number of piles being checked should be considered invalid. On the other hand, if we can put all coins into piles, we continue with the next value of N.

DivisiblePermutations
Used as: Division One - Level Two:
 Value 575 Submission Rate 144 / 382 (37.70%) Success Rate 105 / 144 (72.92%) High Score kalinov for 551.03 points (5 mins 58 secs) Average Score 385.83 (for 105 correct submissions)

This task can be solved using the dynamic programming. At first let's introduce the term "mask". Under mask we understand any subset of digits from the original number (the order of digits in subset is not particular). It can be presented as the number of times each digit occurs in the subset. So for number "122132" the mask can be presented as {2, 3, 1, 0, ..., 0}. It's easy to show that the total number of different masks for the specified number N is not more than 5832.

Let's define A[t, m] as the number of permutations of mask t which are equal to the m modulo M. The answer is A[T, 0], where T is the mask for the given N. This value can be calculated lazily as it is shown in the flowing pseudo-code:

``` A[t, m] = 0;
for (i = 1..9)
for (m2 = 0..M-1)
if (m2 * 10 + i = m (mod M))
A[t, m] += A[t - i (mask t without one of the i digits), m2];
```

SwapSorter
Used as: Division One - Level Three:
 Value 1000 Submission Rate 98 / 382 (25.65%) Success Rate 12 / 98 (12.24%) High Score ACRush for 649.74 points (23 mins 44 secs) Average Score 472.07 (for 12 correct submissions)

Let's build the oriented multi-graph where vertices are all unique numbers from the given array. For each element of the original A[i] which is not equal to the corresponding element of the sorted array B[i] let's add the edge (A[i], B[i]) to the graph. Obviously, each connected component of the resulting graph is Eulerian.

Allowed swap of two elements in terms of graph is the replacement of two consequent edges (v1, v2) and (v2, v3) with one edge (v1, v3) and selfloop (v2, v2). All selfloops do not have any interest for us and should be removed. For example, for A = {3, 1, 2} graph will have following edges: (3, 1), (1,2), (2, 3). Swapping of 3 and 1 will lead to replacement of edges (3, 1) and (1, 2) with the edge (3, 2).

Let's consider connected components with two vertices. Each swap in such component removes two edges (two selfloops appears instead and should be immediately removed). If the total number of edges in the component was E, we will make E/2 swaps.

Let's consider connected components with more than two vertices. As we already discussed it is possible to build Eulerian Circuit inside each component. If component contains 3 vertices and 3 edges, it is clear that 2 replacements can be done. Otherwise, in this Eulerian circuit is possible to find at least one triple of consequent distinct vertices v1, v2, v3 so, that after replacing of edges (v1, v2) and (v2, v3) with the edge (v1, v2) the component will still has at least three vertices and will remain to be Eulerian. Therefore, if such component has E edges, the maximum number of swaps can be done is E-1.

By Andrew_Lazarev
TopCoder Member