Friday, November 22, 2002

Implementation

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 two-dimensional character array given as input, and the commands are either no-ops (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 three-dimensional 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.

Implementation

It's clear from the examples that simply iterating paths is not the answer, as there can be up to 2⁶³ 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 three-dimensional 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 base-2 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 two-dimensional matrices (representing the number of paths between all pairs for two different lengths) and returns a two-dimensional 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 two-dimensional 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.

Implementation

This is just a suped up version of a typical breadth-first-search problem, something which should pose little challenge to competitors that have made it to the semi-finals. The most interesting aspect of this problem is the input, part of which specifies parameters to a pseudo-random 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⁵ = 3200000 locations in the graph. There's no problem with storing information for all of these in memory. The general process of a breadth-first search is then as follows.

The primary data structure for a breadth-first 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 four-dimensional). 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 n-element 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.