Match Editorial

This set of problems was unusually easy, and correct solutions mostly came about from an ability to follow directions. Surprisingly, considering the low level of difficulty of the problems, only one person (out of 167) successfully solved the Division-II Level 3 problem. The remaining problems generally showed high success rates.

Despite the easiness of the problems, only four coders solved all three of their problems (all in Division-I): bstanescu, with a final score of 1421.7; Yarin with 1347.74; ZorbaTHut with 1302.99; and ShakeSpace with 1077.79. In Division-II the competition was much more intense, with most room leaders scoring in the 600s.

The Problems

Submission Rate - 145/167 (86.83%)
Success Rate - 90/145 (62.07%)
High Score - RajAjmani for 297.03 points

This problem is a simple matter of dealing with ASCII values of letters and following directions. The easiest mistakes to make were probably to use inclusive comparison operations rather than exclusive operations (e.g., length >= 20 as opposed to length > 20).

Submission Rate - 118 / 167 (70.66%)
Success Rate - 87 / 118 (73.73%)
High Score UFP2161 for 400.96 points

Submission Rate - 91 / 96 (94.79%)
Success Rate - 77 / 91 (84.62%)
High Score - radeye for 241.83 points

This problem was a good demonstration of how crazy natural languages tend to be. Like the previous problem, solving this problem was primarily a matter of carefully following directions. The problem provided the necessary data structure.

If the conjugation is singular and not third-person, the stem change needs to be performed. This consists of locating the next to last vowel in the word (a simple linear search from the end of the word) and replacing it with the given replacement. It is then a simple matter of dropping the last two characters and appending the proper ending obtained from one of the given tables.

Only once before have I noticed an event where only one coder successfully solved a particular problem. It's rather surprising that this was the case with this particular problem. The logic of the solution is reasonably simple. One has to be able to compute the result of pitting one Packyman against another, and then return the Packyman with the three highest scores.

The former task consists of accumulating a bonus percentage by iterating through the four type combinations (primary and secondary types between two opponents). This could be simple cut and paste coding, as in fiddlybit's solution.

The latter task consists if imposing the prescribed ordering on the Packymen, once you've computed how they would fare against their opponents. Once the best three have been selected, sort them by name and return them.

Submission Rate - 73 / 96 (76.04%)
Success Rate - 19 / 73 (26.03%)
High Score - ZorbaTHut for 369.81 points

This problem poses an interesting slant (if you will pardon the pun) on word searches. The problem is to locate an occurance of a word where each successive letter of that word occurs in a fixed distance in a particular direction from the preceding letter. Furthermore, there is a restriction on what this distance can be: it must be the minimum distance between lattice points intersected by the line formed by the letters.

In other words, one needs to iterate through all the reasonable slopes that can be constructed from two relatively prime values. That is, each slope is constructed from two values, dx and dy, representing offset in columns and rows respectively between each letter. These two values then describe how a successive letter in the word will be reached. The reason that these values must be relatively prime is that, if they are not, then the line segment described will intersect at least one lattice point before the successive letter is reached.

As the search area is of finite size, there are a finite number of reasonable relatively prime pairs that we can form. Our values for dx and dy each must be between 1 and 20 inclusive, and there can only be far fewer than 400 possible directions.

For each combination of direction (+/-dx, +/-dy) and location (x, y) in the puzzle, we check to see if the word exists there. The direction tells us how to increment/decrement x and y between each successive letter in the word. As long as we are careful about not going out of bounds, it is easy to determine if the word exists at a particular location in a particular orientation. We must also not forget to deal with the horizontal and vertical directions, represented by (+/-1, 0) and (0, +/-1) respectively.

Submission Rate - 32 / 96 (33.33%)
Success Rate - 18 / 32 (56.25%)
High Score - bstanescu for 687.40 points

Despite its added complexity, this problem is still nothing more than a simple optimal-path-through-a-maze finding problem. This can be easily tackled with a breadth-first search. In this case, distance becomes a tuple (keys, leftMoves), giving simultaneously minimum number of keys required and the minimum number of left moves for that number of keys. Initially we know the distance to any 'V' location is (0, 0), and it is easy update the minimum distance to each of its neighbors. We then repeat the process for each updated neighbor in the next step. We continue this until no more updates occur. At this point we will know the minimum distance from some 'V' location to the 'W' location (or, if this distance was never updated, it will be some preset value representing infinity).