POJ Monthly on April Fool’s Day!

Problem A: Coins

For an even number of coins, there is no solution. The number of flippings and that of coins that have heads facing up are always of the same parity. And no number can be both even and odd. Thus the conclusion follows.

For an odd number of coins, denoting the number by n, the answer is n − 1. Let m be the number of coins that have heads facing up, all possible numbers of flippings are given by the set S_m = {m + 2k | k ∈ N} ∪ {n − m + 2k | k ∈ N}. The minimum element that all S_m’s share is n − 1.

Problem B: Washing Clothes

Clothes of each color are washed independent of those of other colors. When washing clothes of one color, Dearboy should divide them into two best balanced parts, in the sense that the difference of time required for washing the parts is as small as possible. Finding such a dividing is in fact an instance of a 0/1 knapsack problem where the method of dynamic programming applies.

Problem C: Rescue Alice

The problem can be interpreted as to find a point in a set of points in the Cartesian plane which minimizes the sum of distances to other points in the set, where distance is defined in the L_∞-metric. By applying the transformation (x, y) → (^{(x − y)} ⁄ ₂, ^{(x + y)} ⁄ ₂) = (x′, y′), the L_∞-metric will be replaced by the L₁-metric. Using the transformed coordinates, the sum of distances with respect to point i can be rewritten as ∑_{j ≠ i} |x_i′ − x_j′| + ∑_{j ≠ i} |y_i′ − y_j′|. The two summations can be computed separately.

Problem D: PM³

Let E = {1}_{1 × N}, F = {1}_{M × 1}. C = AB implies EC = E(AB) and CF = (AB)F. If C and AB differ at the element in row r and column c, then EC and E(AB) will differ at the element in column c, and CF and (AB)F will differ at the element in row r. Thus the incorrect element of C can be located by evaluating and comparing EC, E(AB), CF and (AB)F. Exploiting the associativity of matrix multiplication, E(AB) and (AB)F can be first changed into (EA)B and A(BF) before evaluation, which can lead to a great speed-up.

Problem E: Heap

The postorder traversal sequence of keys of a heap described in the text must be an increasing sequence where some pairs of consecutive elements are required to be strictly increasing. Hence, the problem can be reduced to determine the minimum number of elements of an array that have to be modified so that the array satisfy the constraints on increasingness. This latter problem is closely related to the longest increasing subsequence problem, though reduction is not straightforward.

Problem F: Median of Lines

Notice that all f_i(x)’s are increasing functions, so is their median F(x). Therefore the equation F(x) = 0 can be solved by performing bisection on x.

Problem G: Repairing Company

This problem is basically a minimum path cover problem. Use a direct graph to represent the relations between tasks. If it is possible for a repairman to show up in time for task j after finishing task i, insert an edge emanating from vertex i to vertex j into the graph. Then the minimum number of repairman needed is equal to the path cover number of the graph.

Problem H: Eugenics

The ideas in the problem can be directly implemented with any graph search algorithm.