Match Editorial

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

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

  int[] getDifferences(int n) { 
    return n%2==0 ? new int[]{n*n/4,1} : new int[]{n*n,4}; 
  }

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)

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.

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

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)!

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)

 ( #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)) )