Tuesday, February 8, 2005 Match summary Last night's SRM was one of the most exciting in recent history. SnapDragon, tomek, John Dethridge, and radeye were neck and neck till the very end. The top ranked competitors submitted their solutions in rapid succession, each vying for the top position. After an unusually active and tumultuous challenge phase many things were uncertain, except who would win. Assuming his solutions passed, radeye was assured the first place prize. Once the systests finished, radeye's position as winner was confirmed. In Division 2, an Indonesian coder with the handle titid_gede won first place by a considerable margin. The newcomer jkburt took home a respectable second place finish. The ProblemsInequalityCheckerUsed as: Division Two  Level One:
The most popular solution computed each sum separately using a for loop. Since the only possible denominators are 1, 2, and 4, the final calculation can be done pretty easily. An alternate solution uses the fact that 1^{3} + ... + n^{3} = n^{2}(1 + n)^{2}/4Using this formula, we find that the final result is always n^{2}/4. This shows that in actuality, the final denominator can only be 1 or 4. A solution written in Java follows: int[] getDifferences(int n) { return n%2==0 ? new int[]{n*n/4,1} : new int[]{n*n,4}; }SortEstimate Used as: Division Two  Level Two: Used as: Division One  Level One:
The two major obstacles in this problem are the runtime, and the corner cases. Seeing as there is no straightforward method to directly solve the inequality, we need to search for the correct value. In order to write a solution that runs quickly enough, a binary search should be used. When deciding the initial upper bound for your binary search, make sure to use a value greater than time. The solutions that did not take this precaution failed on inputs where time was low. DeserializeSequenceUsed as: Division Two  Level Three:
This problem is a typical Div 2 Hard. Recursively check all possible situations, and count how many work. To solve the problem, we write a recursive function that takes 2 parameters: the string to work on, and the previous sequence element. In the body of the function, we try all possible prefixes that represent valid integers. To be valid, the integer cannot be less than the preceding sequence element, and must be between 1 and 100000 inclusive. The function can then be called recursively with the remaining suffix, and the newly obtained value as arguments. Memoization can be used to speed up this process, but it was not required given the constraints. Java code follows: int rec(String str, int prev) { if (0 == str.length()) return 1; int ret = 0, curr = 0; for (int end = 0; end < str.length(); end++) { curr = (curr * 10) + str.charAt(end)'0'; if (curr < prev) continue; if (curr > 1000000) break; ret += rec(str.substring(end+1),curr); } return ret; } public int howMany(String str) { return rec(str,1); }PascalCount Used as: Division One  Level Two:
The input constraints made computing each binomial coefficient impossible. The values become unwieldly on the longer rows. Luckily, we can get away with knowing how many times 2, 3, and 5 divide each term. An entire row can be processed lefttoright in an efficient manner using the following identity: i! ij i!  *  =  j! * (ij)! j+1 (j+1)! * (ij1)!Thus, we can quickly compute how many times 2, 3, and 5 divide the current term using the previous term and (ij)/(j+1). To illustrate how these divisibility counts are used, we look at the case of determining how many terms are divisible by 6. Since checking divisibility by 6 is equivalent to checking divisibility by 2 and 3, we determine how many terms in a row have positive counts for both 2 and 3. MultiReplacer Used as: Division One  Level Three:
Let #a(x) denote the number of a's occuring in the string x. This problem boils down to computing #a(f(x)), #b(f(x)), and #c(f(x)) given that you know #a(x), #b(x), and #c(x). First, let's look at explicit formulas for these terms: #a(f(x)) = #a(arep)*#a(x) + #a(brep)*#b(x) + #a(crep)*#c(x) #b(f(x)) = #b(arep)*#a(x) + #b(brep)*#b(x) + #b(crep)*#c(x) #c(f(x)) = #c(arep)*#a(x) + #c(brep)*#b(x) + #c(crep)*#c(x)Rewriting this in terms of matrices we get: ( #a(arep) #a(brep) #a(crep) ) ( #a(x) ) ( #a(f(x)) ) ( #b(arep) #b(brep) #b(crep) ) * ( #b(x) ) = ( #b(f(x)) ) ( #c(arep) #c(brep) #c(crep) ) ( #c(x) ) ( #c(f(x)) )Using matrices we have reduced the problem of applying f many times to exponentiating a matrix many times. Since we can exponentiate a matrix to the kth power in time logarithmic in k, we are able to compute the result quite quickly. Care should be taken to apply the modulus after each arithmetic operation in order to avoid overflowing. 
