Happy Lantern Festival!

Problem A: A Very Simple Compiler

The 16-bit width of half precision implies that the total number of possible values of x is strictly less than 65,536 when not taking special values into account. Taking advantage of this condition, a simple solution is to evaluate the expression for every value of x and hard-code the results into a table for the generated code to look up. Half-precision arithmetic can be done through single-precision arithmetic, making use of the conversion routines provided.

Problem B: Incremental Python Parsing

A segment tree is used to store the program, each node of the tree representing a consecutive code fragment. For each node, the following information about the corresponding code fragment is maintained in each modify operation in O(log n) time:

• qn: parity of the number of quotes
• bn: number of left brackets minus that of right brackets
• bm: minimum of differences as defined for bn of all prefixes of the code fragment
• ln: count of new-lines up to the position where bm takes its value

Notice that it is unnecessary to distinguish the three kinds of brackets because they are always matched when queries occur. For a query operation, consider all characters up to the position specified in the query. They divided into code fragments F₁, F₂, …, F_k in order, each represented by a node of the segment tree x_i (1 ≤ i ≤ k), where k = O(log n). Starting with q₀ = b₀ = s₀ = 0, for each i (1 ≤ i ≤ k), define:

• q_i = q_{i − 1} ⊕ qn_i
• b_i = b_{i − 1} + bn_i
• s_i = s_{i − 1} + ln_i when b_{i − 1} + bm_i = 0, s_{i − 1} otherwise

s_k will be the answer to the query.

Problem C: Ikki’s Story I – Road Reconstruction

It is easy to see that all the edges that Ikki needed to find must be saturated in some maximum flow. But not all saturated edges will satisfy his need. The point is that we have to decide whether a saturated edge is the only saturated one in a s-t path. If there is only one saturated edge in the path, increasing the capacity of this edge will surely lead to a larger maximum flow value.

So we run some graph search algorithm on the residual network to see which vertices are reachable from source, then collect them in a set S; and which vertices the sink is reachable from, then collect them in a set T. If a saturated edge reaches from some vertex in S to another in T, it surely is one we need.

Problem D: Ikki’s Story II – War with TN

An O(N(N+ M)) algorithm will run too long. The author’s approach is based on two runs of breadth first search. The first run grows a breadth first search tree rooted at s and finds a shortest path from s to t p in terms of number of edges. Only vertices that appear in p are considered candidates. The second run determines for each vertex the shallowest vertex in p from which it can be reached without passing any edges in p. Then some vertex in p, if any of its tree descendants in p is connected to any of its ancestors by a path that is edge-disjoint from p, can be eliminated.

Problem E: Ikki’s Story III – Rescue frkstyc!

Consider adding the vertices one by one to the tree in increasing order of their designated numbers. It’s not difficult to draw a recurrence relation from the process. In fact you can prove a one-to-one correspondence between the answers and the Eulerian numbers.

Problem F: Ikki’s Story IV – Panda’s Trick

Observe that two links cross when both connected inside the circle iff they cross when both connected outside the circle. Use an undirected graph to represent the relations between links. If two links cross, their corresponding vertices are connected by an edge. Then a cross-free connection is possible iff the graph is bipartite.

Problem G: Apocalypse Someday

All numbers containing 666 can be considered as strings of the language defined by the regular expression [1-9][0-9]*666[0-9]*. An equivalent deterministic finite automaton (DFA) can be constructed to recognize the strings. Counting of the strings can also be done with the DFA by the technique of dynamic programming. Inversing the count gives the corresponding number.

Problem H: From Pythagoras to …

A positive integer n is a sum of two squares iff all prime factors of n congruent to 3 modulo 4 have even exponents in the prime factorization of n. A proof requires knowledge of the Legendre symbol and Fermat’s two-square theorem.