Match Editorial

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

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)

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;
 }

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;
 }

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.

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)
   if (i in mask t)
     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];

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.