Match Editorial

This challenge was held just one and a half day after the previous SRM — nevertheless the number of the participants was pretty high. Russian coders put on an excellent performance, getting five of the top 10 places, including first and second. andrewzta proved his right to wear the new target sign he got after the last SRM and won the Division 1. Second place went to Petr, who scored most in the first and third problems. Third was Ying from China.

In Division 2 many participants successfully solved the first and second problems. The third also had a fairly high success rate. The division leaders are thecompknight, Vadimmer, and atlas_ding.

The Problems

Value	250
Submission Rate	322 / 354 (90.96%)
Success Rate	258 / 322 (80.12%)
High Score	andres14bc for 244.71 points (4 mins 11 secs)
Average Score	192.16 (for 258 correct submissions)

In this problem you just need to do what is written in the problem statement. Here is the sample solution:

public class NounReform {
    static final String[] rule1 = new String[]{"s", "z", "x", "ch", "sh"};
    static final String[] rule2 = new String[]{"ay", "ey", "iy", "oy", "uy"};

    public String[] makePlural(String[] nouns) {
        List<String> result = new ArrayList<String>();
        for (String s : nouns) {
            result.add(reform(s));
        }
        return result.toArray(new String[0]);
    }

    private String reform(String noun) {
        for (String s : rule1) {
            if (noun.endsWith(s)) return noun + "es";
        }
        for (String s : rule2) {
            if (noun.endsWith(s)) return noun + "s";
        }
        if (noun.endsWith("y")) return noun.substring(0, noun.length() - 1) + "ies";
        return noun + "s";
    }

Value	500
Submission Rate	244 / 354 (68.93%)
Success Rate	205 / 244 (84.02%)
High Score	zein for 472.26 points (6 mins 57 secs)
Average Score	324.75 (for 205 correct submissions)

This problem as well is pretty straightforward. You just need to rebuild the statistics thoroughly following rules from the problem statement. Here is the sample solution:

    public String[] newStatistics(String[] placeboard) {
        List<String> result = new ArrayList<String>();
        for (String s : placeboard) {
            String player = s.substring(0, s.length() - 2);
            String position = s.substring(s.length() - 2);
            List<String> tail = new ArrayList<String>();
            for (String s1 : placeboard) {
                if (s1.startsWith(player)) {
                    tail.add(s1.substring(s1.length() - 2));
                }
            }
            tail.remove(position);
            Collections.sort(tail);
            for (String s1 : tail) {
                position += "," + s1;
            }
            result.add(player + position);
        }
        return result.toArray(new String[0]);
    }

Value	900
Submission Rate	46 / 354 (12.99%)
Success Rate	18 / 46 (39.13%)
High Score	tsjoker for 841.08 points (7 mins 37 secs)
Average Score	568.23 (for 18 correct submissions)

Value	250
Submission Rate	196 / 300 (65.33%)
Success Rate	178 / 196 (90.82%)
High Score	Petr for 246.90 points (3 mins 11 secs)
Average Score	194.07 (for 178 correct submissions)

Let's build a graph where vertices are numbers from N to M and there is an edge from vertex v1 to vertex v2 if v2 can be obtained from v1 using exactly one operation from the problem statement. To solve the problem you just need find the shortest path from the vertex N to the vertex M in this graph. This can be done using breadth first search algorithm.

The subtask of the finding of all natural divisors of a number K can be solved using O(sqrt(K)) operations (each divisor p greater than sqrt(K) has one correpsonding divisor K/p less than sqrt(K)).

Value	500
Submission Rate	176 / 300 (58.67%)
Success Rate	140 / 176 (79.55%)
High Score	Revenger for 488.22 points (4 mins 26 secs)
Average Score	330.22 (for 140 correct submissions)

Let's call left part of a number (L + 1) / 2 leftmost digits of the number, where L is the length of this number. The left part of the palindrome unambiguously defines the whole palindrome and vice versa.

Let's note that for a given length N the number of the left parts for the numbers of this length is 9*10^(N-1)/2, because the leftmost digit cannot be equal to zero. Therefore the number of the palindromes of the length N is also 9*10^(N-1)/2.

So we can easily find the length of the K-th palindrome and its position P among the palindromes of this length. Note, that if two palindromes have a same length and the left part of one palindrome is less than the left part of another palindrome, the same is true and for the palindromes themself. Thus the left part of the desired palindrome will be 10^(N-1)/2 + P. And the hole palindrome can be reconstructed by its left part.

Here is the sample solution:

public class IntegerPalindrome {
     public long findByIndex(int K) {
        int k = K;
        for(int len = 0; len <=10; len++) {
            for(int add=0; add<=1; add++) {
                long total = getTotal(len, add);
                if (k >= total) {
                    k -= total;
                } else {
                    return generatePalindrome(len, add, k);
                }
            }
        }
        return 0;
    }

    private long getTotal(int len, int add) {
        if (len+add == 0 ) return 0;
        long res = 9;
        for(int i=0; i<len+add-1; i++)
            res *= 10;
        return res;
    }

    private long generatePalindrome(int len, int add, int k) {
        StringBuffer buffer = new StringBuffer();
        for(int i=0; i < len+add-1; i++) {
            buffer.append(k % 10);
            k /= 10;
        }
        buffer.append(k+1);
        String s = buffer.reverse().toString();
        s = s + new StringBuffer(s.substring(0, s.length() - add)).reverse().toString();
        return Long.parseLong(s);
    }
}

Value	900
Submission Rate	45 / 300 (15.00%)
Success Rate	12 / 45 (26.67%)
High Score	Petr for 690.02 points (16 mins 46 secs)
Average Score	525.92 (for 12 correct submissions)

This task can be solved using the dynamic programming technique. First let's remove all the words which are the part of some other word from the given array. Clearly, if we have a part of the string written, and we want to add some word to the end of this string, we should use as many characters from the end of the string as the prefix of the word as possible.

Let A(subset of words S, last used word W) be the shortest string containing all words from S and tailing with the word W. A(S, W) can be calculated by iterating through all the words T_i from S and adding the necessary number of characters to A(S - W, T_i). Holding only the last word is sufficient, because no word is a substring of another word after the first step of the solution.

You can look at the Petr's solution as reference.