Match Editorial

The Problems

Value	250
Submission Rate	145 / 227 (63.88%)
Success Rate	140 / 145 (96.55%)
High Score	gruban for 233.94 points

Implementation

If the hose length is at least as long as the length of either dimension, then all plants can be watered. Otherwise, we get the number of rows and columns the hose can cover, by dividing the row and column distances respectively by the hose distance. If the hose can travel x rows and y columns, then there will be a rectangle of plants in the middle that cannot be reached consisting of n - 2x rows and n - 2y columns.

Value	450
Submission Rate	135 / 227 (59.47%)
Success Rate	114 / 135 (84.44%)
High Score	Frostburn for 418.33 points

Implementation

The easiest way to solve this problem is to repeatedly pull the applicants from the list that have the maximum score. That is, determine the maximum value in the scores array, then add all those applicants whose scores are this maximum value to the return array and remove them from the scores and names arrays. Removal can consist of simply overwriting their score with a negative value. We continue this process of finding the maximum score and removing applicants with that score until we have at least five applicants in the return array.

Value	850
Submission Rate	71 / 227 (31.28%)
Success Rate	57 / 71 (80.28%)
High Score	FunOrPain for 759.70 points

Value	250
Submission Rate	92 / 98 (93.88%)
Success Rate	76 / 92 (82.61%)
High Score	PurpleBob for 242.49 points

Implementation

Every programmer should know that the sum of the integers from 1 to k inclusive is k*(k+1)/2. It then follows that the sum of the integers from n to n+k is (n+1)*k*(k+1)/2 (because n + (n+1) + ... + (n+k) = (n+1)(1 + 2 + ... + k)).

For integers x and k, we want to determine if there exists an integer y such that y + (y+1) + ... + (y+k-1) = x. All we have to do is solve for y. We have

y * k + (k - 1) * k / 2	=	x
y * k	=	x - (k - 1) * k / 2
y	=	(x - ((k - 1) * k) / 2) / k

So to determine if y is integral, we only need to see if k divides into x-(k-1)*k/2 (which we can do using the modulus operator). The only problem is that we're dealing with quantities of approximately k² , and k is permitted to be as large as 1,000,000. Therefore the computations should be done using 64-bit arithmetic to avoid overflow.

Value	650
Submission Rate	33 / 98 (33.67%)
Success Rate	27 / 33 (81.82%)
High Score	radeye for 542.00 points

Implementation

The solution is to iterate through all the possible placements of the fence that would contain at least one wildebeest. In this manner the number of iterations is reduced to a manageable level. We choose an arbitrary corner of the fence and place it at all the lattice points such that the fence will contain at least one beast. Since the beasts are really points of no size, we need to also place the corner at offsets of half a unit vertically or horizontally from any lattice point.

Relative to a particular beast location, there is a finite number of offsets where we can place a corner of the fence and contain that particular beast (using the lattice points and midpoints as described above). In fact, these offsets are always the same, and can be precomputed. We then iterate through each beast. For each beast we iterate through all fence placements containing that beast. For each fence placement we then count the beasts it contains, and save the maximum.

To count the number of beasts enclosed by the fence at a particular location, we need a method for determining whether or not a given beast is enclosed by the fence. Let's suppose we specify the location of the fence as the coordinate of its bottom-most point (i.e., the point with maximum y value). Any beast with y-coordinate greater than or equal to that of the bottom-most point is not enclosed. Furthermore any beast with y-coordinate less than or equal to that of the bottom-most point minus the length of the diagonal is excluded. If a location passes these two tests, we then take the absolute value of the difference between its x-coordinate and that of the bottom-most point of the fence (call this dx) and do the same for the y-coordinate (call this dy). If dy is greater than the diagonal, then assign to dy the difference between the diagonal length and the former value of dy. If dx < dy, then the beast is enclosed by the fence.

Value	1050
Submission Rate	15 / 98 (15.31%)
Success Rate	15 / 15 (100%)
High Score	ZorbaTHut for 691.22 points

Implementation

The key to the solution of this problem was to develop an efficient data structure for holding previous scores and computing ranks of new scores on the fly. When inserting a value into this data structure, it must be possible to compute the number of values greater than the value being inserted that have already been inserted into the structure.

One approach is to use a binary tree. Each node in the tree is associated with a score value. Each node's left child and all its descendants represent values less than that node's score value, while the right descendants represent values greater than that node's score value. With each node is also maintained a count of values that have been inserted to the right of that node in the tree, as well as a count of the number of times the node's value has been inserted.

When a score is generated, it is inserted into the tree. Insertion consists of walking the tree until a node representing that score is encountered or the traversal has no place to go. Traversal consists of moving to the left child of a node if its score value is greater than the score we're inserting, or the right child if its score value is less. If there is no such child, we must insert a new node at this location representing the score to be inserted. Whenever we traverse to the right child, we increment the parent node's count of values greater than it.

As we insert we also maintain a running total representing the rank of the score we're inserting, to be returned once the value is inserted. If we traverse to a left child, we increment the rank counter by the parent node's number of instances and by the number of values that have been inserted to the right of the parent. If we traverse to a right child, we do not increment the rank counter.