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 ProblemsDancingSentenceUsed as: Division Two  Level One: Used as: Division One  Level One:
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:
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 gameth 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:
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 nondecreasing 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. DivisiblePermutationsUsed as: Division One  Level Two:
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 pseudocode: A[t, m] = 0; for (i = 1..9) if (i in mask t) for (m2 = 0..M1) 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:
Let's build the oriented multigraph 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 E1. 
