Table of Contents

1. Generalized Connect Four
2. Ultimate Weapon
3. Matrix Analysis
4. A Modular Arithmetic Challenge
5. Alternating Sum of Digits
6. Resistance
7. Light Switching Game
8. Escape of Life and Death
9. References

Problem A: Generalized Connect Four

A naïve implementation of the negamax search is unlikely to pass all test cases within the time limit. A common and simple improvement to the negamax search is a technique called alpha-beta pruning. The alpha-beta search maintains two values, α and β, which represent the minimum score that the maximizing (next) player has been assured of so far and the maximum score that the minimizing (previous) player has been assured of at the same moment respectively. The initial values of α and β are the minimum and maximum possible scores respectively. Out of the nature of zero-sum games, α′ = −β and β′ = −α are passed as arguments in each recursive call to the search procedure, and the return value is negated as ρ to update α with the greater one of the two (thus making the alpha-beta window smaller). When α becomes greater than β during the search, the current position cannot be the result of the best play by both players because the minimizing player will not allow the maximizing player to achieve a higher score than β. At this point, pruning occurs as the current position is not further explored. In the optimal case, alpha-beta pruning can reduce the effective branching factor to its square root and thus allows the algorithm to search twice as deep with the same of amount of computation.

Problem B: Ultimate Weapon

The continuous, closed and convex surface that encloses a set of points and has the smallest surface area is the convex hull of the points. There are many algorithms to construct three-dimensional convex hulls. Here only the incremental algorithm is described.

Assuming the absence of degeneracy, the incremental algorithm works as follows.

1. Connect the first four points to form a tetrahedron, the initial convex hull.
2. For each remaining point p which lies outside the current convex hull, add it to the convex hull as follows.
   1. Assuming that the convex hull is an opaque body, determine the facets that are visible from p.
   2. Connect p to endpoints of the horizon edges, the edges lying between visible facets and invisible ones, to form new facets of the convex hull.
   3. Remove the facets that were visible from p and are now inside the convex hull.

Problem C: Matrix Analysis

Denote by β^k the vector formed by concatenating the columns of B^k in order for each k ≥ 1. It is clear that there exists a mn × mn matrix A such that β^k = Aβ^k−1 for each k > 1. This results in an O((mn)³log k)-time algorithm to compute any B^k.

An alternative approach derives from the observation that for each given pair (i, j), the value of b_ij^k is a polynomial function in k, i.e.

,

where δ_ij is the order of the polynomial and c_ij^t is the coefficient of k^t. To compute the coefficients, we can first rewrite the given recurrence relation defining b_ij^k as

,

then sum both sides over 2, 3, …, k, which gives

.

The two summations in parentheses above are in general of the form

,

where f(t) is a polynomial in t. Breaking f(t) into separate terms reduces the summation to the well-known problem of computing sum of powers, whose solution involves Bernoulli numbers.

Problem D: A Modular Arithmetic Challenge

For the sake of convenience, we shall first address those cases where there is no solution. Such cases are characterized by either trivially L > min{R, M − 1} or no multiple of gcd(M, D) falls between L and R (inclusive).

For the rest of our discussion, we assume that the solution x exists and, without loss of generality, 0 ≤ L ≤ R < M. Instead of finding x directly, we first determine the value of Dx mod M, with which we can compute x later. If some multiple of D falls between L and R (inclusive), i.e.

,

it is evident that in this case. Otherwise, it must hold that

Dk < L ≤ R < D(k + 1)

where . In addition, under the assumption of existence of x, it must also hold that M mod D ≠ 0. Denote by x′ the solution to the instance of the problem with M′ = D, D′ = D − M mod D, L′= L mod D, R′ = R mod D. We then have Dx = Dk + D′x′ mod D. The value of D′x′ mod D can be found recursively. Once we have found the value of Dx mod M, we can use the extended Euclidean algorithm to compute x.

Problem E: Alternating Sum of Digits

We explain the solution using an example where K = 3 and N = 1011. First of all, we group all numbers from 1 to 1011 by their radix lengths into maximal groups whose sizes are powers of 3 except for the last group, as listed below.

In the list above, underlined digits are preceded by plus signs in the summation while the others are preceded by minus signs; digits in red are the common prefixes shared by numbers in the same group. Next, we will focus on summation within a single group.

Summation within one group can be found by computing the sum over the common prefixes and that over the suffixes separately. Computing the former is intuitively easier since it has a regular pattern. To facilitate the computation of the latter, we break the suffixes of the numbers into individual digits and handle the digits by radix place. When listed in order, digits in each radix place of the suffixes of the numbers make up a sequence of the form (0^x1^x2^x)^y where x and y are powers of 3 (a^k represents k consecutive occurrences of a; the parentheses indicate grouping). The pattern may be incomplete in the last group, but that should not be too difficult to address. Whether the digits in the sequence are preceded by alternating signs is decided by the radix length of the numbers. The sign before the leading 0 is decided by the total count of digits in previous groups and the radix place.

Problem F: Resistance

To compute the equivalent resistance measured between two designated junctions in a circuit of resistors, we can either connect the two junctions to the ends of a constant voltage source and compute the current across the circuit, or connect them to the ends of a constant current source and compute the potential difference between them. In either way, we establish a system of linear equations in voltages at the junctions and currents over the resistors according to Kirchhoff’s current law and Ohm’s law, which are quoted as follows.

Kirchhoff’s current law. At any point in a circuit where charge density is not changing in time, the sum of currents flowing towards that point is equal to the sum of currents flowing away from that point.

Ohm’s law. The current passing through a conductor between two points is directly proportional to the potential difference across the two points, and inversely proportional to the resistance between them.

Then we can use Gaussian elimination to solve the linear system.

In the case of using a constant current source, the problem can be alternatively formulated as a convex cost flow problem. The circuit is regarded as an undirected flow network where the cost of an arc is defined as the heat generated by the current flowing through the corresponding resistor. We establish a flow of current on this network that generates the least heat and compute the equivalent resistance using the generated heat according to Joule’s first law. The successive shortest path algorithm for minimum (linear) cost flow still works, but special care has to be taken when computing the costs of augmenting paths since the cost of any arc is a quadratic function in the flow over it.

Problem G: Light Switching Game

Before examining the game in a cube of arbitrary dimensions, we shall first analyze a simplified version where the cube is restricted to be of dimensions n × 1 × 1. We claim that a game with lights on in cells (x₁, 1, 1), (x₂, 1, 1), …, (x_k, 1, 1) is equivalent to a game of Nim with k piles of chips containing x₁, x₂, …, x_k chips respectively. This is because

1. Turning off the light at (x_i, 1, 1) alone is equivalent to removing the whole pile of x_i chips;
2. Turning off the light at (x_i, 1, 1) and toggling the light at (x_j, 1, 1) is equivalent to removing x_i − x_j chips from a pile containing x_i chips.

Consequently, the nimber of the aforementioned game is x₁ ⊕ x₂ ⊕ ⋯ ⊕ x_k, where ⊕ denotes nimber addition, which is effectively bitwise exclusive-or.

Now we are ready to scrutinize the original game. Assume that the game has lights on in cells (x₁, y₁, z₁), (x₂, y₂, z₂), …, (x_k, y_k, z_k). It remains valid to decompose the game into the sum of k sub-games each having a distinct light on. Less well-known, the nimber of any sub-game (x, y, z) can be written as x ⊗ y ⊗ z, where ⊗ denotes nimber multiplication. The set of nimbers, , in conjunction with nimber addition and multiplication, constitutes a field , with 0 and 1 as the additive and multiplicative identities respectively.

To evaluate x ⊗ y, we can take advantage of the following two lemmas concerning Fermat 2-powers (numbers of the form 2²ⁿ) in addition to the properties of the field :

1. The nimber product of a Fermat 2-powers and any smaller number is their product in the sense of ordinary natural number arithmetic.
2. The nimber square of a Fermat 2-power x is 3x⁄2 in the sense of ordinary natural number arithmetic.

The following example demonstrates how techniques are combined to evaluate 32 ⊗ 16:

Problem H: Escape of Life and Death

The underlying model of this problem is the shortest path problem on direct acyclic graphs. After topologically sorting the vertices, one can compute the shortest path in linear time.

References