Problem A: Candies

Let x_· denote the number of candies. The problem describes a number of constraints of the form x_B − x_A ≤ c and asks for max x_flymouse − x_snoopy. This is a model of the shortest path problem. The description also implies that c is non-negative in all constraints. Dijkstra's algorithm is a common choice to handle shortest path problem with non-negative weights.

Problem B: Father Christmas flymouse

The first observation is that flymouse would never enter a room to receive words with negative comfort index, therefore it is safe to turn every negative number in the input into zero. The next thing to see is that rooms reachable from one another can be combined into a single room, i.e., in terms in graph theory, strongly connected components in the reachability graph of rooms can be contracted. Contraction results in a directed acylic graph, which is very much suitable for a dynamic programming procedure to perform on.

Problem C: Numerical Integration

Solution to this problem is divided into two principal modules: an expression evaluator and an integrator.

There are many methods to implement a parser for expressions, among which the most preferable one is to implicitly rewrite the grammar as an operator grammar and parse it using stacks. It is recommendable that the parser changes the expression into a form that facilitates evaluation. Two such forms are postfix representation and tree representation of expressions.

An good integrator is crucial to the solution. The description mentions Newton-Cotes formulas. Common instances of Newton-Cotes formulas include the midpoint rule, the trapezoidal rule and Simpson’s rule. These rules themselves are too simple. But it does not require complex ideas to make them robust. The key is using an adaptive approach based on recursive subdivision. While evaluating the quadrature over some interval for the approximation, an error bound is also estimated. If the bound does not exceed a certain threshold, the approximation is accepted; otherwise the interval is divided into two subintervals for refinement.

Problem D: Walking Race

Solving this problem requires two steps – find out the distances wc walks each day and determine the longest series of days. The first step is accomplished by doing a depth-first search in the tree-like structure of check-points and paths. And the second step is done by using two double-ended queues to maintain an increasing sequence and a decreasing one of distances. Both steps require linear time.

Problem E: King of Fighters

This problem consists of a model of weighted bipartite matching. The model is very special in that nodes in its underlying bipartite graph are unevenly divided, which implies its requires very few augmentations to reach a optimal matching. Efficient implementation of the Hungarian method will achieve a respectable running time.

Problem F: Command Network

The problem asks for the minimum spanning arborescence rooted at a fixed node of a directed network. Chu-Liu-Edmonds algorithm applies. The algorithm proceeds as follows. For each node in the network except the root node, pick the arc into it with the smallest weight. The picked arcs form a spanning arborescence, the algorithm terminates. Otherwise, some arcs must form some cycles. Weights of picked arcs into nodes in cycles are subtracted from weights of the other arcs into these nodes. And the cycles are contracted. Repeat the same process on the resulted graph to find its minimum spanning arborescence. Then cycles are expanded. Deleting suitable arcs on the cycles gives the desired arborescence.

Problem G: Traveling Trio

There exists a path from the first city to the last such that all shared routes appear on it. A dynamic programming procedure is crafted upon such a path to solve the problem.

Problem H: Jumping Frog

If the little frog can jump from one leaf to another, we call the two leaves are visible from each other. Based on the visibility between pairs of leaves a weighted graph is constructed. Then the problem is transformed into determining a shortest path on the graph.