Match Editorial

The last competition before the Collegiate Championship went off without a hitch. Well over 400 competed in what turned out to be a very exciting match. In Division 1 it was a close race between all of the top rated competitors. Lunatic Fringe came out early finishing the easy and medium problems before anyone. At one point yellow rated coders led all of the rooms. This slowly changed as Yarin, John Dethridge, and Ambrose came through - submitting their solutions to the hard problem. Despite their efforts, Modulator, a yellow rated competitor, emerged from the coding phase with the highest score. In the challenge phase, the top position exchanged numerous times between Yarin and Modulator. Once the system testing had completed, Yarin prevailed with one of the few correct solutions to the hard problem.

Division 2 had similar intensity. Many of the higher rated coders raced through the easy and medium problems to be faced with a difficult hard - a permutation problem where timing out was a factor. A number of submissions were made, but in the end only two Division 2 coders successfully completed it. Mishagam came out on top with 1353 points and is now competing as a Division 1 coder.

The Problems

Value	300
Submission Rate	212 / 247 (85.83%)
Success Rate	190 / 212 (89.62%)
High Score	Jwizard for 282.60 points

Implementation

In this problem coders were presented with a unique encryption/decryption scheme for black and white pictures. Given the secret key and cyphertext(both pictures), competitors were required to juxtapose the two images and determine which spots would be colored in decrypted image. As explained in the problem, this required a scan through the joint image only retaining the color where both a even and immediately following odd numbered column were both colored. This directly translated into 2 for loops: the outer for the rows of the image, and the inner for the columns. The inner was incremented 2 each time to check a group of even and odd blocks per iteration.

Value	550
Submission Rate	111 / 247 (44.94%)
Success Rate	68 / 111 (61.26%)
High Score	jdandr2 for 509.98 points

Value	250
Submission Rate	157 / 172 (91.28%)
Success Rate	130 / 157 (82.80%)
High Score	radeye for 248.28 points

Implementation

As described in the problem, license plates have a distinct format composed of letters and digits. Supposing that license plates were assigned lexicographically (dictionary ordering) coders were asked to calculate how many license plates could still be generated given the format and the last assigned plate. To quickly calculate the remaining values one could transform the given plate number into a numeric value. This is done by realizing the letter digits of the plate are base 26 values whereas the digits are base 10. A string of multiplications quickly determines the necessary number. For example, lets say you had the license plate "9448". Since all are digits, all represent base 10 values. The calculation goes as follows: ((9*10+4)*10+4)*10+8) = 9448. The multiplications have been written out explicitly so the loop structure of the resulting code could be inferred. Another example may be "AB98A" whose calculation would be: (((0*26+1)*10+9)*10+8)*26+0 where 'A' and 'B' are treated as 0 and 1 respectively. As illustrated here, a loop that tests whether each character is a digit and multiplies by 10 or 26 accordingly produces the correct result.

Value	1000
Submission Rate	22 / 247 (8.91%)
Success Rate	3 / 22 (13.64%)
High Score	mishagam for 601.63 points

Implementation

This problem asked coders to arrange marriages between a group of men and women given how they felt about each other. The input contained the satisfaction values each person would receive for marrying a particular mate. By computing every permutation of mates and selecting the highest sum we arrive at our answer. The only catch is, avoid marriages that produce negative satisfaction values. This is done via a check in the recursion as seen in the reference implementation. To avoid timing out, make sure you eliminate the people you have married together from future recursive steps. This can be done via a boolean array that marks who has already been married.

Value	450
Submission Rate	128 / 172 (74.42%)
Success Rate	48 / 128 (37.50%)
High Score	Lunatic Fringe for 385.21 points

Implementation

The clustering coefficient of a particular vertex in a graph is the ratio between how many of its neighbors are connected and how many of its neighbors could be connected. This type of analysis is typically used in acquaintance graphs that study social patterns and thus the "friendship" analogy may be helpful here. If someone has a high clustering coefficient it means, in general, that many of his/her friends are friends with each other. In this example, the "linkage" analogy was used as is sometimes done in search engines. A web page would receive a high clustering score if the pages it links to were highly interlinked. To solve this problem you dump all of the input into a large adjacency matrix and iterate through it. For each vertex determine all of its neighbors, and count how many edges they had between them. Dividing this value by n*(n-1) (number of total possible directed edges between n vertices) will produce the clustering coefficient. To avoid rounding issues it can be easier to leave the values in numerator/denominator format and compare accordingly.

Value	950
Submission Rate	27 / 172 (15.70%)
Success Rate	5 / 27 (18.52%)
High Score	Yarin for 701.43 points

Implementation

The last thing you want to do in Siberia is push your car. To minimize the agony of such an experience this problem asked for the minimum amount of initial pushing that would be required to allow your vehicle to make one complete 1000km pushless trip around the track. Gas stations along the way were low on gas and could not always be counted on for help. In addition, the car's tank can only holds enough gas to travel 500km so poorly placed gas stations could ruin any chances of success. One of the easier solutions was to assume your were in the correct starting position and simulate a test run. If you failed, record how much you failed by, push the car that distance, and repeat the process. After iterating this process 10 or so times, if you still haven't found a solution, place your car at the next gas station and try again. This strategy was used in the reference implementation.