Problem A: A Number from Yanghui Triangle

p is virtually (10^k + 1)ⁿ following the Binomial Theorem. Hence the common technique of binary exponentiation will present an algorithm running in O(log k + log n) time.

Problem B: Big Christmas Tree

It is not difficult to observe that the total cost is the sum of the weights of the nodes times the unit costs of the paths from them to the root. Based on this observation, it can be deduced that the “Christmas tree” is actually a shortest path tree. Now that the costs are non-negative, Dijkstra’s algorithm implemented with some efficient priority queue can be used.

Problem C: Cake Pieces and Plates

A dynamic-programming-based algorithm running in O(nm) time will solve the problem. The one described below requires O(m) space.

Denote the number of different placing of i cake pieces onto j plates by opt_{i, j}. Consider all such placings. If at least one plate is empty, then the placing is also a placing of i cake pieces onto j − 1 plates. If none of the plates is empty, by taking away one piece from each plate, the placing is turned into a placing of i − j cake pieces onto j plates. The preceding deduction gives the recurrence relation opt_{i, j} = opt_{i, j − 1} + opt_{i − j, j}. Using this relation the dynamic programming process can be implemented to require O(m) space.

Problem D: Expected Difference

E(B_m − B₁) = E(B_m) − E(B₁) = ∑ⁿ_{k = m} (^{k − 1}_{m − 1}) (a_k − a_{n − k + 1}) ⁄ (ⁿ_m). Arithmetic error in calculating the weights of elements is a potential source of errors. Some iterative method can be used to tackle the problem.

Problem E: K-Monotonic

The basic idea is dynamic programming. Denote by opt_{i, j} the cost for converting the the subsequence consisting of the first i elements into j monotonic subsequences, and by cost_{i, j} the cost for converting the subsequence consisting of the elements between the i-th and the j-th ones (inclusive) into a single monotonic sequence. Then opt_{i, j} = max _{all possible k’s} { opt_{k, j − 1} + cost_{k, i} } for all possible combinations of i and j with j > 1, and opt_{i, 1} = cost_{1, i} for all possible i’s.

Computation of cost_{i, j} can be divided into two parts by assuming the related subsequence is converted into either a strictly increasing sequence or a strictly decreasing sequence. Assume the sequence is to be converted into an strictly increasing sequence. By taking the transformation A′_i = A_i − i for all i, the restriction of strict monotone can be relaxed to be monotone. At this point, the conversion can be viewed as dividing the subsequence into even shorter subsequences, elements in each one of which are changed to the same value. This view incurs no loss of generality as long as subsequences of length one are allowed. Now focus on a single short subsequence whose elements are to changed to the same value. It can be shown that the best value to which the elements are to be changed is the median of the elements. By carefully extending this thought while keeping the monotonic condition satisfied the minimum cost for converting the whole subsequence into a strictly increasing sequence can be found. The case of conversion into a strictly decreasing sequence can be handled in a similar manner.

Problem F: Cut the Sequence

The solution to this problem is also based on dynamic programming. Call the desired sum of some cutting the value of the cutting. Denote the value of some optimal cutting of the subsequence consisting of the first k elements of the original sequence by opt_k. Then opt_k = min _{l < i < k} { opt_i + max _{i < j ≤ k} { a_j } } where l is the smallest possible index such that ∑^k_{j = l} a_j ≤ M for all k > 0, and opt₀ = 0. If the index i minimizing opt_k is found by enumerating all possible values, the resulting algorithm will run in O(N²) time in the worst case. But further observation reveals that only those indices in the set I = { l, k } ∪ { i : l < i < k ∧ a_i > max _{i < j ≤ k} { a_j } } are worth considering. With a double-ended queue and a priority queue, the set I and the terms corresponding to the indices in it contributing to the formula of opt_k can be maintained in O(log N) time for each k, which will provide an algorithm running in O(N log N) time.

Problem G: Giftbox

It can be shown that a box or the gift can be placed into another box if and only if the less-than relation holds componentwise when the dimensions of each object are sorted in non-decreasing order. Regarding the boxes and the gift as nodes and the containability relation among them as directed arcs, the problem is transformed into finding the longest path in an acyclic directed graph.

Problem H: Image Rotation

Describe the transformations from the original image to the new image with matrices. The compound of the transformations is described by the product of the matrices. And the inverse of the compound is described by the inverse of the product. From the matrices the formulae of transformation can be determined in closed form.