Problem A: Common Substrings

The basic idea is to evaluate the longest common prefix for each pair of suffixes, one from A and the other from B, and add its contribution to the answer. To avoid the force enumeration, you may sort all the suffixes in a list and  scan it, evaluating the contributes of a section of consecutive A's suffixes when we encounter a suffix of B. (Do the similar when encounter B's suffix.)

Problem B: Crossing

Sort the queries in non-descending order of x. For each query, evaluate the amounts of  points in area III, under the horizontal  line and to the left of the vertical line. You may use Segment-Tree to implement it. The answer to the query can be computed by the previous three results.

Problem C: Network

For each edge in the original tree, evaluate how many new channels contributes to creating a new route connecting the ends. If it is 0, the edge together with each new channel may destroy the network. If it is 1, the edge together with the only contributing channel can destroy the network. You may use LCA-RMQ to meet the time limit.

Problem D: Quadratic Functions

All quadratic functions have the form a_ix² + 2a_ix + c_i. Suppose a_i ≤ a_j .We call i is smaller than j if and only if

 a_ix² + 2a_ix + c_i ≤ a_jx² + 2a_jx + c_j   =>  (c_i - c_j) ⁄ (a_j - a_i) ≤ x² + 2x

Denote g(i, j) = (c_i - c_j) ⁄ (a_j - a_i)

Thus, we can maintain an index sequence p₁,  p₂, ...,  p_k such that a_p1 < a_p2 < ... < a_pk and g(p₁, p₂) > g(p₂, p₃) > ... > g(p_k-1,  p_k) by using a balanced tree.

Problem E: Difference is Beautiful

First evaluate the longest perfect sequences staring at every positions. For each [L, R], find a pivot that every longest perfect sequence starting within [L, pivot-1] fits in [L, R] and the ones starting within [pivot, R] exceeds the interval. You may use RMQ to evaluate the answer for the first part.

Problem F: Quad Tiling

Noticing the transfer matrix using in the O(2⁴ × n) Dynamic Algorithm is constant, you can get the answer by evaluating the nth power of the matrix, which can be done in O(logn).

Problem G: X-factor chains

Suppose X = p₁^a₁ + p₂^a₂ + ... + p_m^a_m where p₁ .. p_m are distinct primes. The maximum length is the sum of all a_i. The number is the amount of repeatable permutations of {p₁×a₁, p₂×a_2, ... p_m×a_m}.

Problem H: Kaka's Matrix Travels

Network Flow model is supposed to be used in this problem. Create two nodes u and v for each grid, add an arc from u to v with capability 1 and cost according to the number in that grid. Adding arcs with infinite capability and 0 cost to the neighboring grids. You may use any MinCost-MaxFlow algorithm to get the answer.