Friday, November 22, 2002
RoadTrip
Used as: Level 1Implementation
This problem is strongly reminiscent of the programming language BeFunge.
In a sense, this problem calls for the implementation of an evaluator for a very simplified version
of the language. The program is the twodimensional character array given as input, and the commands
are either noops (the dots) or turns (left, right, or 180 degrees). Input to the program would be
a starting location and a direction, and the output would be the number of locations visited at least once.
The problem then just calls for evaluating the input program for all possible
inputs, and returning the maximal output. You must also detect infinite loops, and terminate any program
that enters one.
The easiest method for handling motion and turns is by specifying an array of position offsets to
represent movement in each direction. For example:
int[][] dxy = {
{ 0, 1 }, // east
{ 1, 0 }, // north
{ 0, 1 }, // west
{ 1, 0 }, // south
}
Each row in this array represents movement in a particular direction, and the rows are ordered
such that the row following represents a left turn and the row preceding represents a right turn.
The first column is the row offset, and the second column is the column offset. Thus {0, 1}
represents no change in row and a positive change in column, which corresponds to eastward movement.
To turn left, then, one just adds 1 to the current direction and then takes that value
mod 4 (so, a left turn when the direction is 3 yields 0). A right turn
consists of subtracting 1, but the modulus operator doesn't work the same way for negative
numbers. It is easier to add 3 instead (since 3 and 1 are congruent modulo 4).
This method is useful for many, many grid traversal problems.
Now all that is left is detection of infinite loops. An infinite loop will only occur if you
revisit a previously visited location and leave it in the same direction that you have left it before.
Thus, maintain a threedimensional boolean array, where the indices represent row, column, and direction.
When you leave a location, check the appropriate element in the array. If it is true, you have entered
an infinite loop, and might as well terminate the program, as no new locations will ever be visited.
Otherwise, set the appropriate element in the array to true and continue evaluation.
Simply evaluate the program for all possible locations and directions, and count how many locations are
visited. Then just return the maximum.
GraphPaths
Used as: Level 2Implementation
It's clear from the examples that simply iterating paths is not the answer, as there
can be up to 2^{63} paths that one must count. Instead we must count the paths
without iterating them. In fact, a dynamic programming solution is called for.
Suppose that we know the number of paths of length a between all pairs of vertices,
as well as the number of paths of length b.
Can we use this information to compute the number of paths of length a + b for all pairs?
We can, and it's actually quite easy. If there exist m paths of length a from
vertex i to vertex j, and there exist n paths of length b
from vertex j to vertex k, then there must be m * n paths of length
a + b from vertex i to vertex k. Thus with three nested for
loops, one can easily generate a matrix giving number of paths of a particular length from similar
matrices for smaller lengths.
Now we can see how to solve this problem in time that is proportional to the logarithm of
the given length. Simply look at the binary representation of the length. The binary representation
is a way of decomposing a value into a sum of powers of 2. So, all we have to do is
compute the number of paths between all pairs of vertices for all lengths that are powers of 2
(up to a certain point).
For this, we again use the method described above. If we know the number of paths of length a,
we can compute the number of paths of length a + a. So, we build a threedimensional array,
paths, where paths[x][i][j] gives the number of paths of length 2^{x} from vertex
i to vertex j. The range of the first index needs to be 0..30 (since
the base2 logarithm of the maximum length we will be given is less than 31). We initialize paths[0]
to be all zeros, except where an edge exists from i to j. If there is an edge from
i to j, then paths[0][i][j] = 1.
We then successively build paths[1] through paths[30]. Since we're going to have
to repeat this process later on to obtain the answer for our given length, it is a good idea to
develop this process as a function, which takes two twodimensional matrices (representing the number of
paths between all pairs for two different lengths) and returns a twodimensional matrix (representing
the number of paths between all pairs for the sum of the two input lengths). Then, to build
paths[n], we simply pass two references to paths[n  1] to this function.
The function also has to handle overflow detection. Basically, before increasing any value, verify that
the amount it is going to be increased by is less than the difference between the maximum value and its
current value. If so, replace it with 1.
Once we build paths, we are ready to compute the answer. We initialize a twodimensional
sum to all zeros, and then set sum[i][i] = 1 for all vertices i. This
represents the number of paths of length 0. We then iterate through the bits of length.
If bit i is 1, then we pass sum and paths[i] to the function
we implemented above and replace sum with its return value. After we've done this for all
the bits of length, we have our answer for all pairs of vertices. We simply look up the
value at the location specified by the input parameters and return it.
HigherMaze
Used as: Level 3Implementation
This is just a suped up version of a typical breadthfirstsearch problem, something which should pose
little challenge to competitors that have made it to the semifinals. The most interesting aspect of
this problem is the input, part of which specifies parameters to a pseudorandom number generator which
is used to populate the graph before the search is performed. This might make testing and challenging
more difficult, but the problem statement explicitly specifies how to code the generator, so it should
not pose much difficulty as far as coding goes.
There are at most 20^{5} = 3200000 locations in the graph. There's no problem with storing
information for all of these in memory. The general process of a breadthfirst search is then as follows.
The primary data structure for a breadthfirst search is a priority queue. The values that are stored in
the priority queue are tuples. Each such tuple represents a location and a cost for reaching that location.
Thus the priority queue is initially populated with the starting location with a cost of zero.
Each value that we pull from the queue represents a location we can reach (and the minimal cost of reaching
that location). For each location we reach, we generate the locations of all its neighbors (which may include
neighbors reached directly through wormholes) and compute the costs
for reaching each of these locations by passing through the current location. That is, we compute the cost
of travelling from the current location to a neighbor, and add that cost to the cost of reaching the current
location. We then construct a tuple for associating each of the neighboring locations with the computed cost
for each, and add them to the priority queue.
Usually, for efficiency, we would not not add a tuple to the
queue if there has already been added to the queue a tuple for the same location with a lower cost.
However, we are dealing with a graph where edges may have negative weights, so this practice would be
erroneous.
This is all standard fare, and all of the contestants have probably solved this problem for two, three, or even
four dimensions (I recall an ACM ICPC problem a few years ago that was fourdimensional). This is just
a generalization of the same problem. Generalizing the solution is trivial, except for the matter of iterating
neighbors. Writing code to generate neighbors of an arbitrary location in n dimensions is trivial if
n is constant for your program, but it's slightly harder to generalize for any n. This consists
of generating all nelement arrays where the values of each element can be either 1, 0,
or 1, and this could easily be done in a simple recursive function. Generating locations of asteroids
in the manner prescribed should probably be done in the same manner.
By Logan
TopCoder MemberAuthor Profile
