
Match Editorial 
SRM 112Monday, September 9, 2002
The Problems
GardenHose
Used as: DivisionII, Level 1:
Value

250 
Submission Rate

145
/
227
(63.88%)

Success Rate

140
/
145
(96.55%)

High Score

gruban for
233.94 points

Reference implementation:
madking
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.
Top5
Used as: DivisionII, Level 2:
Value

450 
Submission Rate

135
/
227
(59.47%)

Success Rate

114
/
135
(84.44%)

High Score

Frostburn for
418.33 points

Reference implementation:
androm
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.
SumK
Used as: DivisionII, Level 3:
Value

850 
Submission Rate

71
/
227
(31.28%)

Success Rate

57
/
71
(80.28%)

High Score

FunOrPain for
759.70 points

Used as: DivisionI, Level 1:
Value

250 
Submission Rate

92
/
98
(93.88%)

Success Rate

76
/
92
(82.61%)

High Score

PurpleBob for
242.49 points

Reference implementation:
ZorbaTHut
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+k1) = 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(k1)*k/2
(which we can do using the modulus operator). The only problem is that we're dealing with quantities of approximately
k^{2}
, and k is permitted to be as large as 1,000,000. Therefore the computations should
be done using 64bit arithmetic to avoid overflow.
Wildebeest
Used as: DivisionI, Level 2:
Value

650 
Submission Rate

33
/
98
(33.67%)

Success Rate

27
/
33
(81.82%)

High Score

radeye for
542.00 points

Reference implementation:
ZorbaTHut
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
bottommost point (i.e., the point with maximum y value). Any beast with ycoordinate greater than or
equal to that of the bottommost point is not enclosed. Furthermore any beast with ycoordinate less than or
equal to that of the bottommost 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 xcoordinate and that of the bottommost point of the
fence (call this dx) and do the same for the ycoordinate (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.
Ranker
Used as: DivisionI, Level 3:
Value

1050 
Submission Rate

15
/
98
(15.31%)

Success Rate

15
/
15
(100%)

High Score

ZorbaTHut for
691.22 points

Reference implementation:
bigg_nate
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.