Contents

1. Holey Square Tiling
2. Stochastic Finite State Automaton
3. Ellipsoid
4. Paper-, er, Transcript-Folding Game
5. A Game with Colored Balls
6. System of Linear Equations
7. Undergraduate Instruction Evaluation
8. RoBa Has a Second Art Gallery!

• References

Problem A: Holey Square Tiling

Assuming that a horizontal domino covers the lower left corner halves the number of possible tilings. Based on this assumption, we continue to complete the tiling. First notice the case shown in Figure 1, which can be completed in only one way.

Figure 1

The remaining cases fall into two categories depending on the placement of the domino covering the upper right corner, each dividing the holey square into two isolated L-shapes (see Figure 2).

Figure 2

Apply similarly the argument of assuming a direction for the domino covering the corner to these L-shapes will further divide them into rectangles of width 2 (see Figure 3), the number of whose tilings are Fibonacci numbers.

Figure 3

Detailed discussions on counting holey square tilings can be found in [Tau04].

Problem B: Stochastic Finite State Automaton

Let f_ik denote the probability that the automaton is in state i after k transitions, define and f(x) = (f₁(x), f₂(x), …, f_n(x))^T. Apparently, f(x) is the probability-generating function associated with the random vector X = (X₁, X₂, …, X_n) where X_i is the number of transitions that have been made when the automaton is in state i. With f(x) we can conveniently describe the behavior of the automaton with the equation

f(x) = xAf(x) + b

or

(I − xA)f(x) = b.

Observe that the probability that the automaton halts in each state i is given by p_i · f_i(1) with . Substituting 1 into all occurrences of x in the equation above we can solve for f(1) and subsequently all desired probabilities.

Calculating expected values and standard deviations from probability-generating functions involves the derivatives of probability-generating functions. Assuming second-order differentiability of the probability generating function g(x) associated with some random variable Y, we have

• E(Y) = g'(1),
• Var(Y) = g''(1) + g'(1) − (g'(1))².

(Refer to [GKP94] for further details.) It is noteworthy that for each state i, p_i · f_i(x) is not immediately the probability-generating function in which we are interested. The vector f(x) describes the automaton as a whole, thus each of its components reflects information about the corresponding state from the perspective of the whole automaton. For each state i, we want to find the conditional expected value and standard deviation of X_i provided that the automaton halts in state i. Consequently, the probability-generating function of interest is

.

This requires us to find, in addition to f(1), f'(1) and f''(1). Taking the first- and second-order derivatives on both sides of the the equation concerning f(x), we have

(I − xA)f'(x) − Af(x) = 0,
(I − xA)f''(x) − 2Af'(x) = 0.

Again substituting 1 into all occurrences of x in the equations above we can solve for f'(1) and f''(1). Then we can easily determine the desired expected values and standard deviations.

As an additional remark, the solvability of the aforementioned equations relies on the invertibility of I − A, which is ensured since I − A is diagonally dominant.

Problem C: Ellipsoid

The reference solution implements the principal component analysis (PCA) technique, which the author solely intends to have the problem theoretically grounded. Given a relatively loose error margin the author instead suggests that a better contest-time strategy be to figure out some subtle methods. In particular, the author finds that the following one works very well, producing results comparable to those given by PCA.

1. Translate the points so that the averages of the x-, y- and z-coordinates are zero. Then every point can be considered a vector whose head is at the origin and whose tail coincides with that point.
2. Repeat the following procedure three times.
   1. Generate a random vector n.
   2. Calculate .
   3. If n and n' is is close enough, report n' and proceed to step iv; otherwise assign n' to n and go back to step ii.
   4. Project orthogonally the points onto the plane through the origin with n' as its normal.

To whom may be interested, here are a brief description of how the PCA solution proceeds.

1. Translate the points so that the averages of the x-, y- and z-coordinates are zero.
2. Construct a 3-by-N matrix B each of whose column are the coordinates of a point.
3. Compute C = ¹⁄_{(N − 1)}BB^T. (C is called the the empirical covariance matrix.)
4. Eigendecompose C and report its eigenvectors in decreasing order of the their corresponding eigenvalues. The reference solution uses the QR algorithm for this step.

[Shl05] is a good introduction to PCA.

Problem D: Paper-, er, Transcript-Folding Game

This problem is undoubtedly the easiest one of the contest. In a word, the answer is the smaller between

and

.

Problem E: A Game with Colored Balls

The only complication of the game occurs when, after a segment is dislodged, the two segments immediately before and after the removed one share the same color and thus have to be joined into a longer one. Using a union-find algorithm we can efficiently handle the complication. All candidate segments can be maintained in a priority queue. The priority queue must support efficient modifications to its elements, since when two segments are joined, being replaced by a new, longer one and these changes have to be reflected accordingly in the priority queue. Common data structures for priority queues such as heaps and binary trees all meet this requirement.

Problem F: System of Linear Equations

For unconstrained linear system Ax = b, Gaussian elimination is an effective method. However, in the presence of nonnegativeness constraints, Gaussian elimination does not work since it has no control on the unknowns’ signs.

Without loss of generality, we assume that b ≥ 0. Instead of directly seeking for a solution to the equation Ax = b subject to x ≥ 0, we alternatively starts with a solution x to the inequality Ax ≤ b subject to x ≥ 0, and strive to minimize the violation |b − Ax|₁ (|·|₁ means the sum of components, 1-norm, of a vector) by moving from one solution to another. Each step we try to identify an unknown x_i and change its value, as well as the value of another unknown x_j if necessary, abiding by the nonnegativeness constraints, so that the violation decreases. This step is repeated until the violation becomes zero or can no longer be decreased. Then we can decide whether we have discovered a solution to Ax = b subject to x ≥ 0 or the linear system has no nonnegative solution.

The process above implicitly states the simplex method for linear programming applied to the problem below:

minimize y₁ + y₂ + … + y_m

subject to

,
x_i ≥ 0, ∀i = 1, 2, …, n,
y_i ≥ 0, ∀i = 1, 2, …, m.

Problem G: Undergraduate Instruction Evaluation

The solution to this problem can be illustrated by the sample test case, which is taken from [AMO93]. The sample test case can be described as the following linear program:

maximize 5y₁ + 12y₂ + 10y₃ + 6y₄

subject to

,
y₁, y₂, y₃, y₄ ≥ 0.

The dual of this linear program is

minimize x₁ + x₂ + x₃ + x₄ + x₅

subject to

,
x₁, x₂, x₃, x₄, x₅ ≥ 0,

which, by adding in slack variables and performing some row operations, can be rewritten as

minimize x₁ + x₂ + x₃ + x₄ + x₅

subject to

,
x₁, x₂, x₃, x₄, x₅, z₁, z₂, z₃, z₄ ≥ 0.

In this latter form, the coefficient matrix has exactly a pair of 1 and −1 in each column, coinciding with the incidence matrix of some directed network. Since the constants on the right-hand side sum to zero, the constraints can be understood as the mass balance constraints of flows. Finishing the construction, the function that is to be minimized can be considered as the flow cost. In sum, the linear program above describes an uncapacitated minimum cost flow problem.

Solving the minimum cost flow problem gives a solution to the dual program. In order to find a solution to the primal program, one can establish nonnegative distance labels for the vertices with respect to the residual network. These distance labels solve the primal program and subsequently the original one.

Problem H: RoBa has a Second Art Gallery!

[EU95] discusses this problem, the analysis in which is paraphrased as follows.

It is not difficult to prove that the an optimal pair of cameras must always be installed on two vertices of the polygon. There are two different ways that two cameras can cover the whole gallery, as shown in Figure 4.

Figure 4

The case in the left is easy. However, the case in the right seems quite complicated. It is not immediately clear what choices of points C and D will minimize α + β for moving any of C and D changes α and β simultaneously. Observe that, as shown in Figure 5, taking advantage of the fact that α + β + γ + δ = 2π, we can maximize γ + δ instead. Furthermore, moving C will only change γ, and moving D will only change δ. Thus, we can maximize γ and δ independently. This last step can be done either numerically or analytically.

Figure 5

[EU95] proposed a quadratic time algorithm and a linear-time variant for the case where the vertices of the polygon are cocircular.

References