JOIN
 Match Editorial
SRM 302
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 Problems

NounReform
Used as: Division Two - Level One:
 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) {
}
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:
 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.remove(position);
Collections.sort(tail);
for (String s1 : tail) {
position += "," + s1;
}
}
return result.toArray(new String[0]);
}

DivisorInc
Used as: Division Two - Level Three:
 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)
Used as: Division One - Level One:
 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)).

IntegerPalindrome
Used as: Division One - Level Two:
 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++) {
if (k >= total) {
k -= total;
} else {
}
}
}
return 0;
}

private long getTotal(int len, int add) {
if (len+add == 0 ) return 0;
long res = 9;
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);
}
}

JoinedString
Used as: Division One - Level Three:
 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 Ti from S and adding the necessary number of characters to A(S - W, Ti). 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.

By Andrew_Lazarev
TopCoder Member