Match Editorial

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

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;
}

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)

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;
   al.add("1/"+x);
   n = n*x - d;
   d *= x;
    } 
    return (String[])al.toArray(new String[0]);
}

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 } 

        { bxa | x is a positive length string }. 

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.

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(n²) 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.