Get Time
statistics_w  Match Editorial
SRM 135
Tuesday, 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  discuss it
Used as: Division-II, 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


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  discuss it
Used as: Division-II, 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: Division-I 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


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  discuss it
Used as: Division-II, 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


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  discuss it
Used as: Division-I, 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


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.

CircleHighway  discuss it
Used as: Division-I, 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


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