Friday, November 22, 2002
Used as: Level 1
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
c2 = a2 + b2 + 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( (c2 - a2 - b2) / (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.
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.
Used as: Level 2
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.
Used as: Level 3
There exists an O(n log2 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 204 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 i2 for 1 <= i <= 10).
Next we must remove all rectangles that are completely enclosed by another rectangle. This is a simple
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 (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.
TopCoder MemberAuthor Profile