
Match Editorial 
SRM 135Tuesday, February 11, 2003
Match summary
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
VideoCrypto
Used as: DivisionII, Level 1:
Value 
300 
Submission Rate 
212 / 247 (85.83%) 
Success Rate 
190 / 212 (89.62%) 
High Score 
Jwizard for 282.60 points 
Reference Implementation: brett1479 in practice room
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.
Plates
Used as: DivisionII, Level 2 :
Value 
550 
Submission Rate 
111 / 247 (44.94%) 
Success Rate 
68 / 111 (61.26%) 
High Score 
jdandr2 for 509.98 points 
Used as: DivisionI Level 1 :
Value 
250 
Submission Rate 
157 / 172 (91.28%) 
Success Rate 
130 / 157 (82.80%) 
High Score 
radeye for 248.28 points 
Reference Implementation: brett1479 in practice room
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.
Marriage
Used as: DivisionII, Level 3:
Value 
1000 
Submission Rate 
22 / 247 (8.91%) 
Success Rate 
3 / 22 (13.64%) 
High Score 
mishagam for 601.63 points 
Reference Implementation: brett1479 in practice room
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.
Clusters
Used as: DivisionI, Level 2:
Value 
450 
Submission Rate 
128 / 172 (74.42%) 
Success Rate 
48 / 128 (37.50%) 
High Score 
Lunatic Fringe for 385.21 points 
Reference Implementation: brett1479 in practice room
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*(n1) (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.
CircleHighway
Used as: DivisionI, Level 3:
Value 
950 
Submission Rate 
27 / 172 (15.70%) 
Success Rate 
5 / 27 (18.52%) 
High Score 
Yarin for 701.43 points 
Reference Implementation: brett1479 in practice room
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.
By
brett1479
TopCoder Member