Match Editorial

With the Collegiate Championship only a few weeks down the road, competition attendance is growing steadily. Over 400 coders registered for SRM 131 including top ranked competitors Yarin, John Dethridge, SnapDragon, and ZorbaTHut. Competition was fierce, with the top scoring spot changing hands multiple times in the coding, challenge, and system test phases. In the end, Yarin prevailed with SnapDragon and John Dethridge close behind.

As a departure from the standard types of problems used, this competition featured an assorted set of algorithmic solutions unlike those seen in previous competitions. It is very exciting to see competitors struggle with problems that challenge their minds, forcing them to develop innovative techniques with little time to think. For example, the division 1 hard problem required the efficient generation of minimum weight Steiner trees, a topic none of the top ranked coders seemed to have experience with. It was this problem that ended up deciding who won SRM 131.

The Problems

Value	250
Submission Rate	252 / 264 (95.45%)
Success Rate	138 / 252 (54.76%)
High Score	stingant for 245.21 points

Reference Solution: brett1479 in the practice room

Implementation

In this problem, coders were asked to determine the final letter grade a student should receive given their exam scores, and the number of TopCoder competitions they competed in. The intelligent Professor M. forces his students to compete in at least 3 competitions per semester. Their final grade will fall a single letter if they compete in less than 3 competitions. To solve this problem one must add up the given scores and then account for the number of competitions.

Value	500
Submission Rate	196 / 264 (74.24%)
Success Rate	96 / 196 (48.98%)
High Score	Karshikinpa for 474.04 points

Reference Solution: brett1479 in the practice room

Implementation

Here coders needed to implement the spelling rule: I before E except after C. To make things slightly more complicated, the I's, E's, and C's can be either capital or lowercase. In addition, the rule must be continually applied until every place where E comes before I is removed unless after C. For example, after a single application of this rule to the string "eeei" we end up with "eeie". There is still an I before an E so we must apply the rule again producing "eiee". Applying the rule a final time produces the string "ieee" and we are done. Code to solve this problem basically consisted of swapping i's and e's until no more swaps could be made, is in the practice room under brett1479.

Value	1000
Submission Rate	119 / 264 (45.08%)
Success Rate	103 / 119 (86.58%)
High Score	vipernky for 996.22 points

Value	300
Submission Rate	126 / 136 (92.65%)
Success Rate	109 / 126 (86.51%)
High Score	Yi Zhang for 298.28 points

Reference Solution: brett1479 in the practice room

Implementation

Given a 2^k by 2^k square floor, you have been asked to lay down tiling covering the entire area incurring the smallest cost. The two types of tiles at your disposal are: a 1 by 1 square tile, and a 2 by 2 tile with a 1 by 1 square removed from one of its corners (an L-shaped tile). The L-shaped tile may be flipped or rotated in any fashion. In addition, both the small square shaped tiles, and the L-shaped tiles cost $1 to lay down. To solve this problem, one could theoretically try to brute-force every possible arrangement of tiles, but a simpler method is possible. Consider the solution to the 2 by 2 square floor below. Using a single L-shaped piece with a square piece costs a total of $2. The key insight here is to realize that the 4x4 case can be produced by placing four of the 2x2 cases next to each other. We can align the single squares in each of the four 2x2 components so that they lie in the middle of the resulting 4x4 block thus giving us the opportunity to use another L-shaped block. In other words, when four of the 2x2 diagrams are used to produce the 4x4 diagram 1, we aligned the B's to all occur in the middle. In 4x4 diagram 2, three of these B's are replaced by the L-shaped E block. Different letters have been used to illustrate the different blocks. Furthermore, we can align four 4x4 blocks to produce a 16x16 block. 4x4 diagram 3 shows how I have slightly changed the organization of diagram 2 to place the single leftover square 'F' in the lower righthand corner allowing four diagram 3 blocks to be connected to form a 16x16 block analogously to how we generated the 4x4 block.

2x2      4x4 (diagram 1)   4x4 (diagram 2)     4x4 (diagram 3)
 --        ----               ----                ----
|AB|      |AAAA|             |AABB|              |AABB|
|AA|      |ABBA|             |AEEB|              |AEEB|
 --       |ABBA|             |DEFC|              |DECC|
          |AAAA|             |DDCC|              |DDCF|
           ----               ----                ----
                                        

The moral of this story is, you never need to use more than a single square in any of the problem sizes. Thus the answer can be calculated by finding the total area, dividing by 3, and then adding 1 for the remaining square block.

Value	500
Submission Rate	121 / 136 (88.97%)
Success Rate	73 / 121 (60.33%)
High Score	SnapDragon for 480.25 points

Reference Solution: brett1479 in the practice room

Implementation

In this problem, coders were asked to find the minimum size chart containing rating information for a bunch of "red" ranked TopCoder competitors. If a coder is red for a period of time, the chart must contain a contiguous bar from the column designating the start of this period, to the column designating the end. Since no overlap may occur, if multiple competitors are red simultaneously, multiple rows must be used. Arranging these bars such that the fewest number of rows is used solves the problem. To accomplish this, we sort the ranges by starting competition numbers and loop through them in ascending order. When processing each item, if one of the rows we have already used is free we can place the bar in that row. Otherwise we must allocate a new row.

Value	1000
Submission Rate	24 / 136 (17.65%)
Success Rate	8 / 24 (33.33%)
High Score	Yarin for 777.13 points

Reference Solution: brett1479 in the practice room

Implementation

In computer chips, wires usually must travel only horizontally and vertically between two points. When trying to build a chip such that all parts on it are connected, many wires must often be used. These parts and wires are often modeled by vertices and edges in a graph. In order to produce a more efficient wiring scheme extra vertices, called Steiner points, may be added allowing for cheaper solutions. To solve this problem, we realize that the only points that need be considered share x and y coordinates with the given points. For example, if the points given are (5,5), (0,0) and (10,0) the x-coordinate of added points must be 0, 5, or 10, where as the y-coordinate must be 0 or 5. Since the maximum number of input points is 5, the largest number of added points we have to consider is 25. In addition, we will never need more than 5 added points to solve this problem, so we can check all subsets of these 25 elements up to 5 elements determining which set of added points produces the best answer. Each time we want to check, we can run a minimum spanning tree algorithm such as Prim's algorithm.