JOIN
 Match Editorial
SRM 234
Wednesday, March 16, 2005

Match summary

During this fast paced SRM, many coders were able to finish the entire set well before the coding phase ended. The Div 1 Hard, scored at 850, proved easier than the medium for most high ranked competitors. With a blazing medium submission, and a respectable challenge phase performance, SnapDragon was able to claim the Div 1 title. This victory was particularly special, since it allowed Snap to reclaim his throne at the top of Division 1. Remaining on top will be the biggest challenge, with Tomek less than 40 points behind. In Division 2, the newcomer Weixing Li won by a comfortable margin. Honorable mention goes to Savior and logged for taking second place in their respective divisions.

# The Problems

ComboLength
Used as: Division Two - Level One:
 Value 250 Submission Rate 270 / 283 (95.41%) Success Rate 226 / 270 (83.70%) High Score gdiitk for 248.31 points (2 mins 20 secs) Average Score 219.35 (for 226 correct submissions)

This problem asks for the longest substring entirely composed of one letter. To compute this, loop over the input string, and count the length of each potential substring. Java code follows:

public int howLong(String moves) {
int ret = 1;
for (int i = 1, c = 1; i < moves.length(); i++)
ret = Math.max(ret, c = moves.charAt(i) == moves.charAt(i-1) ? c+1 : 1);
return ret;
}

FractionSplit
Used as: Division Two - Level Two:
 Value 500 Submission Rate 212 / 283 (74.91%) Success Rate 133 / 212 (62.74%) High Score gdiitk for 492.58 points (3 mins 29 secs) Average Score 331.79 (for 133 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 171 / 172 (99.42%) Success Rate 150 / 171 (87.72%) High Score krijgertje for 246.53 points (3 mins 22 secs) Average Score 211.27 (for 150 correct submissions)

This premise of this problem is a nice exercise for a Discrete Mathematics course. One must prove that all positive fractions of the form n/d can be written as a sum of distinct unit fractions. Typically induction is used on the case where n<d. This result is then extended to the case where n>=d. Luckily, the problem statement revealed the key to the exercise. Repeatedly try to remove the largest possible unit fraction. Thankfully, the inputs are low enough that overflow is not an issue. Java code follows:

public String[] getSum(int nn, int dd) {
long n = nn, d = dd;
ArrayList al = new ArrayList();
while (n > 0) {
long x = (d+n-1)/n;
n = n*x - d;
d *= x;
}
return (String[])al.toArray(new String[0]);
}

DerivationDisplay
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 49 / 283 (17.31%) Success Rate 19 / 49 (38.78%) High Score WeixingLi for 765.17 points (16 mins 51 secs) Average Score 506.23 (for 19 correct submissions)

This problem can be paraphrased as follows: Write a parser. Since the grammar in question is fixed, the CFG rules can be hardcoded into the solution. The structure of the CFG, combined with the constraints, insure that there will always be a unique solution. Essentially, this means that the input string would belong to the set

{ anbm | n != m }
or the set
{ bxa | x is a positive length string }.
The early replacement steps entirely depend on which of the above sets contains the input string. The later steps are determined by m and n, or the contents of x.

WeirdRooks
Used as: Division One - Level Two:
 Value 650 Submission Rate 55 / 172 (31.98%) Success Rate 32 / 55 (58.18%) High Score SnapDragon for 528.26 points (14 mins 20 secs) Average Score 336.17 (for 32 correct submissions)

This problem has a structure that lends itself to a recursive solution. Processing the board from bottom to top, we eliminate one row at a time, and recursively solve a smaller instance. If no rook is placed on the bottom row, then all of the squares in the row can be marked special. Storing the number of these special squares, we then sever the bottom row from the board, and recurse on the remaining upper rows. If we place a rook in the bottom row, then only the squares to its right can be marked as special. In addition, when recursing on the upper rows, the column the rook resides in must be deleted from the board. Without any memoization-style optimizations, the algorithm described here passes all systests. On the largest case, it required 16 million recursive calls, and ran in under 2 seconds.

HowUnsorted
Used as: Division One - Level Three:
 Value 850 Submission Rate 64 / 172 (37.21%) Success Rate 26 / 64 (40.62%) High Score AdrianKuegel for 828.24 points (4 mins 37 secs) Average Score 603.02 (for 26 correct submissions)

This classic problem can be solved in numerous ways, but the standard method is Merge sort. The simple O(n2) inversion (unsortedness point) counting algorithm will timeout due to the input size. The Merge sort technique works as follows. To count the number of inversions in an array of size m, we first divide the array in half, and count the number of inversions in each half. Clearly the inversions in each half will contribute to the total number of inversions in the array. Next we sort each half. Finally, as done in Merge sort, we fill an array in sorted order, using the two halves as input. When we use a value x from the right half, we know that a certain number of inversions occurred in the original array. This is because x is the lowest remaining value, but it sat to the right of all elements in the left half, so the number of remaining left half elements must be added to the inversion total. One added benefit of this process, is that we can skip the "sort each half" step, since we are sorting during the process anyways.

By brett1479
TopCoder Member