Thursday, May 11, 2006 Match summary 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 ProblemsNounReformUsed as: Division Two  Level One:
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"; }XBallGame Used as: Division Two  Level Two:
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]); }DivisorInc Used as: Division Two  Level Three: Used as: Division One  Level One:
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)). IntegerPalindromeUsed as: Division One  Level Two:
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^{(N1)/2}, because the leftmost digit cannot be equal to zero. Therefore the number of the palindromes of the length N is also 9*10^{(N1)/2}. So we can easily find the length of the Kth 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^{(N1)/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+add1; i++) res *= 10; return res; } private long generatePalindrome(int len, int add, int k) { StringBuffer buffer = new StringBuffer(); for(int i=0; i < len+add1; 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); } }JoinedString Used as: Division One  Level Three:
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. 
