JOIN
 Match Editorial
SRM 137
Thursday, March 6, 2003

# The Problems

The phrase "March Madness" best describes the last SRM. Over 15% of the division 1 competitors submitted the hard problem, but only 2 passed systests. SnapDragon, who won the competition, resubmitted the hard problem twice, and eventually won by successfully challenging 5 of the coders in his room. "I didn't even check the last [challenge], I just went for the sweep" said SnapDragon, after sucessfully challenging all of the div 1 hards in his room. schveiguy, the second place finisher, had the highest problem score but could not top SnapDragon's challenge round performance. Division 2 coders faced similar difficulties, with only 10 coders passing systests on the hard problem.

MedianOfMedians
Used as: Division 2 - Level 1:
 Value 250 Submission Rate 204 / 227 (89.87%) Success Rate 175 / 204 (85.78%) High Score koder for 247.71 points

The most straightforward way to solve this problem involved sorting each of the rows given. Extracting the second element from each of these sorted rows will produce a new list of 3 elements. Sorting this list, and taking the second elment will produce the result. Coders need not convert the given input to integer values until the very end, since sorting the characters will produce the same results.

PQNumbers
Used as: Division 2 - Level 2:
 Value 500 Submission Rate 115 / 227 (50.66%) Success Rate 52 / 115 (45.22%) High Score sh_maestro for 444.07 points

Given 2 numbers we are going to consider the possible values generated by multiplying powers of them together. In other words, given numbers p and q we are going to consider values of the form p^k * q^j. Since we are guaranteed that all necessary values will be no greater than 1 million, we can loop through all possible exponents of p and q, and store all of the products, ignoring any values that are greater than 1 million. All of the generated values can be thrown into a sorted set structure whereby, the nth largest value is easily extracted.

ViscoverExpress
Used as: Division 2 - Level 3:
 Value 1000 Submission Rate 26 / 227 (11.45%) Success Rate 10 / 26 (38.46%) High Score omasoud for 543.91 points

Used as: Division 1 - Level 2:
 Value 450 Submission Rate 114 / 132 (86.36%) Success Rate 76 / 114 (66.67%) High Score Yarin for 424.08 points

An intuitive way to solve this problem is to first write a "numberCheck" method. This function takes a string of 16 digits and return true or false depending on whether the value checked out. Such a method loops through the string, summing up the digits (multiplying by 2 where necessary). If the resulting sum is 0 mod 10 return true. Once this helper method is written, the main function can try to generate all possible errors, detecting which ones produce valid numbers. The "at most 1 incorrect digit" error can be produced by replacing each number with any possible digit. The transposition errors can be produced by trying every swap.

Rendezvous
Used as: Division 1 - Level 1:
 Value 300 Submission Rate 120 / 132 (90.91%) Success Rate 81 / 120 (67.50%) High Score antimatter for 295.07 points

Solving this problem basically comes down to solving a system of equations. The two pieces start at (0,0) and (x,y). They change position by <DX,DY> and <dx,dy> respectively each turn. To find the first place they could meet we must solve the equations: t*DX = x+t*dx and t*DY = y+t*dy where t is the turn number. Solving for DX and DY in these equations we get: DX = x/t + dx and DY = y/t + dy where t!=0. A hint was given that we only need check a finite range of positions to rule out all possibilities. Looping through all t values will quickly find the result. Alternate methods which loop over DX and DY values can work as well.

TextileDetective
Used as: Division 1 - Level 3:
 Value 1000 Submission Rate 21 / 132 (15.91%) Success Rate 2 / 21 (9.52%) High Score schveiguy for 629.15 points

This problem, although relatively easy in nature, had many tricks and cases increasing its difficulty tremendously. When a problem breaks into numerous cases, it no longer becomes easy to envision an entire solution. Handling each case in seclusion simplifies matters, but how does one define these cases, and are they separable? Both are questions not so easily answered.

The first issue to be dealt with in this problem is the color of the weft thread. Once chosen, other pieces fall into place. Many methods exist, but the simplest is probably looping through all possible colors. If one turns out infeasible, just continue, and try the next. Given the color of the weft thread, we can determine the color of each warp thread. One square at a time, we loop through the fabric determining which columns should be raised, and which lowered in each row. During this process, we verify that each row and column has at least one raised and one lowered color as the problem states. If everything checks out we are nearly done. One case remains: warp threads that share the same color as the weft thread. We will call columns with this condition weft columns. If all columns are weft columns (a fabric of a single color) we will still need 2 harnesses to drive the machine. If only some are weft columns but every row has been accounted for (every row contains at least 1 raised or lowered harness at some point) all of these weft columns can be attached to preexistant harnesses. Finally, if there are rows that still require a raised or lowered harness at some point, the extra weft columns can fill this gap adding 1 to the total number of required harnesses. Having considered all cases (there are alot) the result produced is the correct number of harnesses.

In summary, we first choose a weft thread color, then we determined the weft and non-weft columns. Using this information we can determined the lowered and raised status of each square in the weft columns. If certain rows still do not meet the 1 lowered 1 raised criteria, the weft columns can fill that gap, otherwise we are done. The only other hitch, is that certain invalid setups must be checked. For example, a column with 3 different colors must produce a return value of -1.

By brett1479
TopCoder Member