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 ProblemsComboLengthUsed as: Division Two  Level One:
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(i1) ? c+1 : 1); return ret; }FractionSplit Used as: Division Two  Level Two: Used as: Division One  Level One:
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+n1)/n; al.add("1/"+x); n = n*x  d; d *= x; } return (String[])al.toArray(new String[0]); }DerivationDisplay Used as: Division Two  Level Three:
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 { a^{n}b^{m}  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:
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 memoizationstyle optimizations, the algorithm described here passes all systests. On the largest case, it required 16 million recursive calls, and ran in under 2 seconds. HowUnsortedUsed as: Division One  Level Three:
This classic problem can be solved in numerous ways, but the standard method is Merge sort. The simple O(n^{2}) 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. 
