Match Editorial

		MATCH EDITORIAL LINKS:
	Room 1 Review Archive   Rookie Review Discuss this match   Problem Set Want to write a feature?

The Problems

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 non-zero 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₁ = (x₁,y₁) and p₂ = (x₂,y₂). This line is a part of a square if and only if there exists two points p₃ = (x₃,y₃), and p₄ = (x₄,y₄) in our list, such that p₁, p₂, p₃, and p₄ 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

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.

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.