Match Editorial

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.

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.

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.

Value	1000
Submission Rate	26 / 227 (11.45%)
Success Rate	10 / 26 (38.46%)
High Score	omasoud for 543.91 points

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.

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.

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.