
Match Editorial 
SRM 108Thursday, August 12, 2002
Match summary
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 DivisionII 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 DivisionI): bstanescu, with a final score of
1421.7; Yarin with 1347.74; ZorbaTHut with 1302.99; and
ShakeSpace with 1077.79. In DivisionII the competition was much more
intense, with most room leaders scoring in the 600s.
The Problems
Lars (value 300)
Used as: DivisionII, Level 2 :
Submission Rate  145/167 (86.83%)
Success Rate  90/145 (62.07%)
High Score  RajAjmani for 297.03 points
Reference implementation:
RajAjmani
Implementation
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).
StemChange
Used as: DivisionII, Level 2 (Value 500):
Submission Rate  118 / 167 (70.66%)
Success Rate  87 / 118 (73.73%)
High Score UFP2161 for 400.96 points
Used as: DivisionI, Level 1 (Value 250):
Submission Rate  91 / 96 (94.79%)
Success Rate  77 / 91 (84.62%)
High Score  radeye for 241.83 points
Reference implementation:
radeye
Implementation
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 thirdperson, 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.
Packyman
Used as: DivisionII, Level 3
Reference implementation:
fiddlybit
Implementation
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.
WordSearch (Value 450)
Used as: DivisionI, Level 2 :
Submission Rate  73 / 96 (76.04%)
Success Rate  19 / 73 (26.03%)
High Score  ZorbaTHut for 369.81 points
Reference implementation:
ZorbaTHut
Implementation
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.
LeftMoves (Value 900)
Used as: DivisionI, Level 3 :
Submission Rate  32 / 96 (33.33%)
Success Rate  18 / 32 (56.25%)
High Score  bstanescu for 687.40 points
Reference implementation:
bstanescu
Implementation
Despite its added complexity, this problem is still nothing more than a
simple optimalpaththroughamaze finding problem. This can be easily tackled
with a breadthfirst 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).