Match Editorial

The Problems

Value	250
Submission Rate	180 / 219 (82.19%)
Success Rate	132 / 180 (73.33%)
High Score	konsept for 245.66 points

Reference implementation: brett1479 (practice room)

Implementation

As the statistics show, most people found this problem pretty doable. Coders were asked to return the digit value that occurred most frequently, breaking ties by favoring higher order digits. Java users could use code like this:

   String temp = ""+inputInt;    
immediately gaining access to the digits of the input integer.  
C++ users could use sprintf:
   char temp[20];
   sprintf(temp,"%d",inputInt);
or stringstreams:
   stringstream ss;
   ss<<inputInt;
   string temp = ss.str();

Value	550
Submission Rate	107 / 219 (48.86%)
Success Rate	86 / 107 (80.37%)
High Score	gali for 529.64 points

Reference implementation: brett1479 (practice room)

Implementation

Although slightly harder than the Easy problem, many quickly figured out what was necessary to solve the Medium. Coders were given n distinct integers between 1 and n inclusive, jumbled up in an arbitrary order. This ordering represented a permutation of the given integers. For example:

int inputArray[] = {3,5,4,1,2}; ,
means if you had the integers {1,2,3,4,5} after applying the 
given permutation you would have the 
integers {3,5,4,1,2}.  In other words, 1 maps to 3, 2 maps to 5, 3 maps to 4, 
4 maps to 1, and 5 maps to 2.

The problem asked for how many disjoint cycles were required to represent the given permutation. The definition of a disjoint cycle comes out of Abstract Algebra, specifically from the theory of Permutation Groups. Basically, start with a number between 1 and n. Then figure out what it maps to. Then figure out what that number maps to. Continue this process until you reach the number you began with. For example, say we start with 1 in the example above. Then 1 maps to 3, 3 maps to 4, and 4 maps to 1. This means there is a cycle denoted by (1, 3, 4). Another disjoint cycle (disjoint meaning, it doesn't share any numbers with the previous cycle) is (2, 5). Since we have accounted for all of the 5 numbers there is a total of 2 disjoint cycles. Java code to implement this reasoning works as follows:

int count = 0;
boolean[] marked = new boolean[inputArray.length]; //for marking used numbers
for (int i = 0; i < marked.length; i++) {   //make sure to account for all numbers
   if (marked[i]) continue;      //we already accounted for this number
   int j = i;    //temp used to store the value we are starting at
   count++;
   while (mark[j]) {
      mark[j] = true;
      j = inputArray[i] -1;    //  '-1' needed since array values are 1-based
            //  and we need 0-based indexing
} 
}
return count;

In my opinion Abstract Algebra is one of the most entertaining fields in math. If you want to take an interesting course in a university setting, or acquire a challenging hobby Algebra may be just what you are looking for (unless you cringe at the sight of anything math related).

Value	1100
Submission Rate	31 / 219 (14.16%)
Success Rate	5 / 31 (16.13%)
High Score	coshx for 571.10 points

Value	550
Submission Rate	93 / 119 (78.15%)
Success Rate	35 / 93 (37.63%)
High Score	venco for 448.47 points

Reference implementation: brett1479 (practice room)

Implementation

This problem, purely in terms of coding time, was arguably the hardest problem of the round. Coders were asked to determine how many blocks were present in a given piece of code. To make things harder comments denoted by '#' symbols, and line-joining operations denoted by '##' symbols could appear just about anywhere in the input. The basic plan is to first rid the code of the annoying comments and line-joins, and then worry about the block structuring. The former is performed by condensing the input into one huge string (lines delimited by some unused character) and looping through it, or looping through the characters each element of the input one at a time.

With the input void of comments and line-joins you can now check the block structure. The important facts to realize are: 1) Blank lines should be ignored, 2) The only thing that matters on each line is where the first significant character is located, 3) Further indented lines start new blocks, and 4) Less indented lines close all open further indented blocks and must match the indentation of a previously open block. A simple way to implement this "block-counter" is to use a stack that holds the indentations of each line, and a counter to hold the number of blocks encountered. Process each line as follows: If the indentation value of the current line is greater than the top of the stack, push its value on the stack and increment your totalNumBlock counter. If it is less than the top of the stack, keep popping values off the stack until you find a value equal to the current indentation. If you never find such a value return -1. When you are done processing all of the lines return the value of totalNumBlock

Value	250
Submission Rate	117 / 119 (98.32%)
Success Rate	114 / 117 (97.44%)
High Score	antimatter for 248.92 points

Reference implementation: brett1479 (practice room)

Implementation

Most division 1 coders raced through this problem, a number of whom submitted solutions before 3 minutes had elapsed. The gist of the problem is, n strings have been concatenated together one character at a time. To get the ith string out of the scrambled mess you simply extract all characters whose position mod n is 0. The problem gave you the scrambled string and the number of original strings (circumference in the problem) and asked for all the original strings. Java code that implements this logic is:

String[] ret = new String[n];  //Decoded strings to be returned
   java.util.Arrays.fill(ret,"");   //Initialize array to contain empty strings
for (int i = 0; i < codedMessage.length(); i++)  //Loop over encoded string
ret[i%n]+=codedMessage.charAt(i); //Place char on the appropriate string
   return ret;  //Return the decoded strings

Value	950
Submission Rate	27 / 119 (22.69%)
Success Rate	17 / 27 (62.96%)
High Score	WishingBone for 694.52 points

Reference implementation: brett1479 (practice room)

Implementation

This problem didn't require a lot of code, but its underlying concept was less than obvious. Participants were asked to implement skew-decimal multiplication. A positive number written in skew-decimal format is composed of the digits '0'-'9' and 'X' such that: 1) There are no leading zeros, and 2) Once an 'X' occurs in the number all following digits (if any) must be zeros. The problem also stated the recurrence relation that correlates the positive integers with the skew-decimal numbers:

Integer 1 corresponds to Skew 1
Integer N corresponds to (Skew N-1) + 1

Incrementing a skew-decimal number is slightly weird. If the number contains an 'X', incrementing the number means changing the 'X' to a '0' and incrementing the number to its left (noting the special case that '9'+1 = 'X'). If the number doesn't contain an 'X' increment its rightmost digit. For example, (Skew 1X0)+1=Skew 200 and (Skew 99)+1=9X . The trick to this problem is realizing how much each digit in the skew-decimal number is worth. Notice that you must increment a particular digit 10 times to get it to change from 0 to 'X'. Then you must increment the entire number once to change the newly created 'X' to '0' thus incrementing the next higher digit. Consider the following examples:

Skew Number	Integer Value
X	10
10	11
1X	21
20	22
X0	110
100	111
200	222
X00	1110
1000	1111

Noticing a pattern in the above table we can see that the digit values from right to left (least order to highest order) are thus: 1,11,111,1111,11111,... Using this fact it is then easy to convert each skew-decimal number to a long, multiply the longs together, and convert the long back to a skew-decimal value.