Friday, November 22, 2002

Implementation

This problem is the well-known traveling salesman problem. More formally, the problem is to find the Hamiltonian cycle of least weight. This problem is NP-complete, but that's no big deal, since there are only up to 9 cities. Thus we simply iterate through all orderings of the non-starting cities (there may be up to 8 of these), and evaluate the cost of the Hamiltonian cycle described by each ordering. Generating these orderings is easy, using C++'s next_permutation function from <algorithm>.

The rest of the problem consists of calculating weights for each edge. This is useful code to have sitting around for reuse, as I have seen a number of ACM problems that deal with computing distances between latitude and longitude coordinates on a sphere. The problem statement gives the formulas for transforming latitude and longitude into Cartesian coordinates. However, some more geometry is necessary to determine the distance on the sphere between the two points.

Imagine a triangle formed by drawing two lines from the center of the sphere to two cities, and a third line directly between the two cities (cutting through the sphere). Each of the lines from the center of the sphere has a known length (the radius of the sphere). We can determine the length of the third line easily enough by computing Euclidean distance between the Cartesian coordinates of the two cities (the square root of the squares of the differences between the values for each coordinate). Since we know the lengths of all three sides of this isosceles triangle, we can easily determine the angles of all three corners. If we know the angle of the corner located at the center of the sphere, we can determine the length of the arc defined by this angle. The length of this arc will give us the shortest distance on the sphere between the two cities.

To find this angle, we will use the law of cosines. This is a formula that pops up in many, many geometry problems:

c² = a² + b² + 2ab cos C

In the above, lowercase variables refer to side lengths, while uppercase variables refer to angles opposite a particular side (e.g., C is the angle of the corner opposite the side with length c). We know a, b, and c (c is the Euclidean distance between the two cities), and need to know C. So a little rearranging gives us:

C = cos^-1( (c² - a² - b²) / (2ab) )

Or, in C:

C = acos((c * c - a * a - b * b) / (2 * a * b));
            

Now, once we know C, we can determine the length of the arc defined by C. The ratio of the arc length to the circumference of the sphere is equal to the ratio of the arc angle to 2pi. That is:

d / (2pir) = C / (2pi)

In the above, d is the length of the arch. The 2pi cancels out on both sides, so we get d = Cr.

Implementation

This problem has a very straight-forward solution. First, we iterate through each possible orientation of each possible choice for the center piece. On each iteration, we iterate through all orderings of the remaining six pieces. Each ordering will specify how the pieces will be laid out around the center piece. Choose an arbitrary starting point and direction (e.g., start at the top and proceed clockwise). As with Travel, C++'s next_permutation would be very useful here.

Each ordering will dictate the orientation of the pieces surrounding the center piece. So all we do for each ordering is determine if it represents a placement that can be made without violating the rules. So, we find the position of the value in the top piece that matches the top value in the center piece. The value next to it (proceeding counter-clockwise about the piece) will be the value that must be adjacent to the next piece. So, we find the position of the the value in the next piece that matches the top-right value in the center piece. The value that follows it in a clockwise manner in the second piece must match the value we found in the first piece. If not, this ordering cannot be a valid placement. Otherwise, we proceed in the same fashion for all the pieces, remembering to check the final piece against the first piece as well.

Implementation

There exists an O(n log² n) algorithm for solving this problem, but the bounds are so low that it makes no sense to deal with the mess of such an algorithm. Instead, I will describe a simpler but more expensive solution.

First, we generate a lot of rectangles by iterating over all choices of 4 1-units (with duplicates allowed), and use the locations of these units to form bounds for a rectangle. We can do this with four nested for loops, a simple process that generates up to 20⁴ rectangles. We immediately discard any rectangle that contains a 2-unit, and any duplicate rectangles. This leaves us with at most 385 rectangles (summation of i² for 1 <= i <= 10). Next we must remove all rectangles that are completely enclosed by another rectangle. This is a simple O(n²) process.

Now we must examine the remaining rectangles to determine the subset of minimum size that selects all the 1-units. At this point we must do a little dynamic programming. For each rectangle, determine the set of 1-units it encloses. This set can be represented by an integer: if the rectangle encloses the ith 1-unit, then the ith bit of the integer's binary representation is 1. We then create an array mins, where mins[x] is the minimum number of rectangles required to enclose all the points in the set represented by x. Initialize each element of mins to be a number greater than the number of rectangles (so we can recognize sets we haven't generated yet), and initialize mins[0] = 0 (because it takes zero rectangles to enclose zero points).

Now, for each rectangle, we iterate through each set with a generated value in mins and determine if the set obtained by adding the current rectangle has fewer rectangles. That is, for each x in mins where mins[x] is not greater than the number of rectangles, we perform the logical or operation with the representation of the set of units enclosed by the current rectangle to get a new set, y. If mins[x] + 1 < mins[y], we replace mins[y] with mins[x] + 1. After we do this for all rectangles, the value of mins[(1 << n) - 1] (where n is the number of 1-units) will contain the answer.