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

InequalityChecker
Used as: Division Two - Level One:
 Value 250 Submission Rate 190 / 225 (84.44%) Success Rate 183 / 190 (96.32%) High Score ctynan for 245.03 points (4 mins 3 secs) Average Score 186.45 (for 183 correct submissions)

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

13 + ... + n3 = n2(1 + n)2/4
Using this formula, we find that the final result is always n2/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:
 Value 600 Submission Rate 67 / 225 (29.78%) Success Rate 21 / 67 (31.34%) High Score ronit_dragon for 489.45 points (14 mins 11 secs) Average Score 339.65 (for 21 correct submissions)
Used as: Division One - Level One:
 Value 300 Submission Rate 148 / 182 (81.32%) Success Rate 102 / 148 (68.92%) High Score radeye for 298.28 points (2 mins 9 secs) Average Score 234.10 (for 102 correct submissions)

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.

DeserializeSequence
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 28 / 225 (12.44%) Success Rate 13 / 28 (46.43%) High Score titid_gede for 890.46 points (10 mins 13 secs) Average Score 595.93 (for 13 correct submissions)

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:
 Value 500 Submission Rate 112 / 182 (61.54%) Success Rate 50 / 112 (44.64%) High Score SnapDragon for 463.33 points (8 mins 7 secs) Average Score 325.69 (for 50 correct submissions)

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 left-to-right in an efficient manner using the following identity:

i!             i-j                 i!
---------------- * ---------  =  -------------------
j! * (i-j)!       j+1          (j+1)! * (i-j-1)!
Thus, we can quickly compute how many times 2, 3, and 5 divide the current term using the previous term and (i-j)/(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:
 Value 900 Submission Rate 57 / 182 (31.32%) Success Rate 47 / 57 (82.46%) High Score m00tz for 838.39 points (7 mins 48 secs) Average Score 600.87 (for 47 correct submissions)

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.

By brett1479
TopCoder Member