Match Editorial

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

The Problems

The solution to this problem consists of converting the input number and its square to strings and returning the length of the longest common suffix (or, instead of converting to strings, one can simply obtain the digits from the right using division and modulo by 10). Simply increment a counter i (starting from 0) until either the counter is equal to the length of the shorter string or the ith characters from the end of each string do not match, then return the length of the shorter string minus i. To get the ith character from the end of a string, get the character at the index that is the length of the string minus i minus 1 (so that i = 0 corresponds to the last character of the string). Alternatively (and this is probably easier), one could simply reverse the two strings, so that counting is done instead from the beginning of the strings.

This problem consists of finding the optimum subset of problems. For a set of n elements, there are 2ⁿ possible subsets, including the empty set. This set of subsets is known as the power set.

Since one can construct a subset by either choosing to include or exclude each element from a set of n elements, it follows that there are 2ⁿ subsets, and that we can simply iterate a counter from 0 to 2ⁿ-1, using the binary representation of the counter to determine whether or not each element of the set is a member of the subset represented by the counter. A true bit corresponds to membership, while a false bit corresponds to exclusion. Thus for this problem we iterate from 0 to 7 inclusive. We assign the 0th bit to the 0th problem, the 1st bit to the 1st problem, and the 2nd bit to the 2nd problem. If a problem's corresponding bit is true, it is selected. If the sum of times of all selected problems is less than or equal to 75 and the sum of scores of all selected problems is greater than the best sum seen so far, we store its sum as the new best sum.

Note that the first argument to the method was completely unnecessary. Perhaps it was there to throw people off, or to make challenges more difficult (due to the need to satisfy an arbitrary set of constraints). I'm sure this caused at least a few coders to take a few seconds to scratch their heads and wonder if there was some trick hidden somewhere.

The solution to this problem is basically a simulation under the given rules. One just had to avoid a couple of tricks that were fairly obvious in the problem.

Since the dates are given in chronological order, a lot of the work is done for you. Though it is tempting to convert each date to a single number (e.g. days since January 1, 1974), this is not necessary, as the only comparison we need to make is to see if two adjacent dates are within a year of each other.

We iterate through each element of the input array, basically applying the points system as we go along and terminating if we ever go beyond the current date. For each element, we see how many years passed between that element and the preceding element (if any). This is determined by taking the difference between the year values (avoiding the Y2K bug, of course). If the month of the current date is less than the month of the preceding date, subtract one year. If the month of the current date is the same as that of the preceding date, but the day is less than or equal to that of the preceding date, also subtract one year. Then subtract three times the resulting number of years from the point counter, bringing it back up to 0 if it is negative. Then we add the points corresponding to the date. At the end we perform the same difference with the current date and the final element of the input array (except we do not add points to the point counter).

This problem could have easily qualified for a Level 1 problem. Obviously one needs a reasonably efficient implementation for computing s(n), or factorizing n. Simply iterating from 2 to floor(sqrt(n)) inclusive and checking each value to see if it divides into n is sufficient. Care needs to be taken not to add any factor twice (which will happen if the factor is the square root of n), and one must handle the cases of 0 and 1 specially (s(0) = s(1) = 0). Many alternate ways of factorizing n exist, most of which are faster, but this simple method is sufficient for this problem. See some of the reference implementations for variations.

The rest consists of computing up to 35 successive values of the aliquot series, with an input value as the initial value. For each new value computed, do a linear search of the preceding values of the series to see if any match. If so, return the index of the first occurrence and its value. Alternatively, one could store each found value with its index in a hash map. If 35 numbers are generated without any repeats, {-1, -1} should be returned.

Technically this handles the special case of 0 terminating the series, but there was ambiguity regarding what should be returned if the 36th number in the series is 0. It is obvious that the 37th number will also be 0, so implementations that handled occurrences of 0 specially would return {35, 0}, while submissions that simply checked for duplicates would return {-1, -1}. The only input value where this occurred was 318, and, due to the lack of consensus regarding which approach was correct, all challenges and test cases with this value were discarded.

Note that all intermediate values needed to be 64 bits in width to avoid overflow. The hint for C++ users informing them of long long essentially gave this away. The case that had the longest runtime by far was 840, which was a sample case. Thus anyone that tested with all the sample cases was pretty much guaranteed to get the problem correct.

The most common mistake was probably not storing all intermediate results, including each value of the aliquot series, as 64-bit integers.

The first task is to run a convex hull algorithm on the four points. If the resulting hull only has three vertices, then the result is a triangle. Otherwise additional processing has to be done to determine what sort of quadrilateral the points constitute. Various algorithms for computing the convex hull of a set of points exist. However, since we're dealing with a constant four points, brute force would be easy enough to implement.

After we compute the convex hull, we obtain the vertices in counter-clockwise order (this is the result of some algorithms anyway). We can then reason about the four points using some basic geometry. First, we obtain vectors that represent each side of the quadrilateral. Each point is basically a vector from the origin; the difference of these vectors describes the orientation and length of the line between them. Thus we obtain vectors representing the four sides of the quadrilateral by taking the differences between successive points.

To check for a rectangle or square, we determine if all four internal angles are perpendicular. This consists of taking each adjacent pair of lines and determining if their dot product is zero. If so, then the two lines describe an internal right angle. If all four angles are right angles, then the result is either a square or a rectangle. Comparing the lengths of two adjacent sides will decide whether it is a square or a rectangle.

Next on the list is checking if it is a parallelogram. We check this directly by determining if the first and third lines are parallel and the second and fourth lines are parallel. We can determine if two lines are parallel by taking their cross product, which for two vectors of non-zero length is only zero if they are parallel. In two dimensional space, the cross product is the product of the first vector's x-component and the second vector's y-component minus the product of the first vector's y-component and the second vector's x-component. If both pairs of lines are parallel, then the quadrilateral is a parallelogram and possibly a rhombus. Again we check side lengths to determine which is the case.

Finally we check to see if the quadrilateral is a trapezoid, which is true if either of the two pairs of lines are parallel. If not, then the quadrilateral is simply a quadrilateral.