
Match Editorial 
SRM 94June 3, 2002
The Problems
DIVI easy? (350 points, SquareFind.numSquares):
This problem had some people
puzzled. I know in my room, I, and at least one other person, spent almost the
whole challenge on this problem. However, if you recognized how to determine a
square quickly, you were all set, as no special algorithm was needed to loop
through the inputs.
Given a list of points, return the number of perfect squares you can find
between all the points. Oh, and squares need not be aligned to the axes.
There were two algorithms that I saw for this problem:
1) for all possible sets of 4 points, determine if they make a square.
2) search for square line possibilities, then return the count / 4.
for the first algorithm, there were two properties that you needed to look for:
1. two diagonals were equal nonzero length
2. all four lines were equal length
If these two properties were true, it must be a square. For a good solution of
this type, see bigg_nate's solution.
For the second algorithm, this was a clever way to determine squareness.
Consider a line between two points p_{1} = (x_{1},y_{1})
and p_{2} = (x_{2},y_{2}). This line is a part of a
square if and only if there exists two points p_{3} = (x_{3},y_{3}),
and p_{4} = (x_{4},y_{4}) in our list, such that p_{1},
p_{2}, p_{3}, and p_{4} make a square. If we say that
starting at p_{n}, traveling to p_{n+1}, we can get to p_{n+2}
by turning left 90 degrees. Using geometry, we can calculate x_{n+2} by
the formula x_{n+1}  (y_{n+1}  y_{n}), and calculate
y_{n+2} by the formula y_{n+1} + (x_{n+1}  x_{n}).
Using this relationship, we can find p3 and p4.
At the end, we have each side of a square being counted once for the square
that it can be in, so we must divide the number of matches by 4 to get the
number of squares.
For a good example of this, see venco's solution
DIVI medium (450 points, NumberFill.gradient):
This was a fill algorithm
problem with two stages. In the first stage, you searched each area for the
highest number, saving the position. In the second stage, you filled the area
from that number with the following rules when you fill in a given direction:
up, down: copy the number in the current location
right: add one to the number in the current location
left: subtract one to the number in the current location
standard recursive fill algorithms execute in plenty of time.
DIVI hard (1050 points, Counter.tallyer):
This problem was a combinatorical problem. The range of 1 to
99999999 made sure a brute force solution would time out. Of the myriad of ways
to solve this problem, I chose two that I thought were good representations of
the mentality necessary to solve it:
METHOD 1: break the range into two more manageable pieces of 1 to 9999.
(SnapDragon)
Assume we have two functions: sum(n) = the sum of the digits of n, and prod(n)
= the product of the digits of n.
1 to 9999 is a very manageable range, and can be easily counted. The way
SnapDragon did his algorithm is:
step 1: count the ways you can make your number from 1 to 9999 for both
products and sums by using the sum and prod functions.
step 2: if high >= 10000, count the ways you can make your number from high
 (high % 10000) to high. I will explain the reasoning for this below.
step 3: Here is the tricky part. He builds a map of all the possibilities for
0000 to 9999 (including leading 0s) for both sums and products. The key of the
map is the sum or product of all the digits, and the value is the number of
ways that sum or product is achieved in this range. For each number in the
range, he adds one to the map elements with keys sum(n) and prod(n).
Then, we assume that for the range:
n * 10000 + 0 to n * 10000 + 9999
The number of "valid" numbers whose digits add up to x are the number
of numbers in the range:
0000 to 9999
whose sum adds up to x  sum(n). You can see that we can use the key x  sum(n)
to look up the precomputed value in the map. Therefore, for each range of
numbers, there is only one call to sum(n) and one search in the map.
Products are computed the same way, except instead of using x  sum(n), he uses
x / prod(n) (being careful for divide by 0 errors).
Step 3 is done for all n such that 1 <= n < high / 10000.
Notice that we do not say n <= high / 10000. The reason for this is because
we already did the values where n == high / 10000 in step 2. We cannot do those
numbers in step 3 because step 3 goes up to n * 10000 + 9999, which may be
higher than the high number.
METHOD 2: For sums, break the ranges into smaller ranges. (dmwright)
First, for the products, it is pretty apparent that all the digits must be
factors of x, and none can be 0 (unless the product is 0). This eliminates most
of the numbers in the range, allowing a brute force solution to work for
products. dmwright's algorithm to find the products is to try all values for
digits. If a particular value is not a factor of the number, or the current
product is greater than the number, or the current number is greater than the
high value, try another value.
Now, for the sums, perform the recursive function below:
for a given range, if the high limit of the range is < 10, return 1 if the
target is in the range of numbers given, 0 otherwise.
if the high limit is > 10, he sets the lowest digit to 0  9, and then
recurses for the higher digits by calling the function again with the range low
/ 10 to high / 10 trying to match the value x  digit. The only issue is for
the first 10 numbers in the range, and the last 10 numbers in the range. For
example, in the range 25  143, he actually calculates the values for 20  149.
He must remove the values for 20  24, and the values for 144  149. He does
this by hand calculating the sums for those numbers, and if they equal the
target, subtracting one from the total.
The final touch is to use memorization to eliminate duplicate calculations.
Note that this technique could be used for products as well, by recursing with
x / digit instead of x  digit as the new target.
By
schveiguy
TopCoder Member