Just a few quick notes about problems (not the full-sized editorial as usual).

A — Buildind a Bookshelf

Iterate over all possible lengths of top/floor l_t and walls l_w (note that they can be equal); reserve two planks of chosen lengths for each. If there are a_i planks of length l_i left, there should at least (be careful not to divide by zero of l_w = 1!) departments of width l_i. The number of inner walls is equal to the number of departments, except for the case when the total width of departments is equal to the width of the bookshelf (we don't need the last inner wall). Check if there are sufficient planks for inner walls, and also if the departments fit into the bookshelf; also, excessive inner walls should placed in the free space. That's an O(n³) solution; finally, notice that the floor should be longer than all the shelves, thus it makes sense to try only the two largest types of planks for the floor. Finally, O(n²).

B — Flatland Division

The most failed problem of the contest. Most accepted solutions are for this problem, I guess, due to a) it was in the beginning of the problemset, and b) this type of problem occurs frequently on many contests. I apologize for the low quality of the problem.

The idea is as follows: the dividing line can be moved so that is nearly passes throw some two cities. Iterate over the pair of these 'border' cities, and find the total population on both sides of the line; choose the best option. To speed up, fix one border city and rotate the line around it. there are O(n) events when a changes side respective to the line; sort them by angle and process iteratively. That makes up for an solution. I tried to make sure no O(n³) solutions pass, but it seems I failed even at that. =(

C — Solitaire Simplified

There is a straightforward O(n⁴) DP solution which basically stores all the interesting info about the state of the game; it can be probably optimized to O(n³). I will describe another, more thought-requiring solution.

Consider an inverse permutation of the deck; that is, if the i-th number of the deck is p_i, numbers q_i are determined by q_pi = i. The number 1 will be surely thrown out on the first discarded through the cards; the number will be discarded on the first pass if q₂ > q₁ or q₂ > q₃ > ... > q_n; and so on.

We see that on each pass through the cards maximal increasing prefix and maximal decreasing suffix of q will be discarded; on the next pass the new maximal monotonous prefix and suffix will be discarded and so on. Suppose there will be m passes through the deck, and the final number is k; this means that there are exactly m - 1 increases in q to the right of k, and exactly m - 1 drops (or, in other words, k - (m - 1) increases) to the left of k; thus the total number of increases will be k - 1 regardless of m. The problem reduced to a classic one: count the number of permutations of n number with exactly k - 1 increases. It can be done straightforwardly in O(n³), or even faster using some ingenious formulas.

D — Xor

Coming up.

E — Tree Growing

The information about the tree can be stored simply as a sequence of operations. The sizes of the tree after each operation will also be useful. The "+ k" is thus trivial.

Now to find the distance between two vertices. This can be divided into two tasks: finding depth (distance from the root) d(v) of the vertex v given its number, and determining depth of the LCA of two vertices; the distance is given by d(x) + d(y) - 2d(lca(x, y)).

If v = 1, the depth is clearly 0. Otherwise, the number of the subtree of the root which contains v is ⌊ (v - 1) / s, where s is the size of a single subtree. Similarly, the number of vertex v in the subtree in its original numeration is . We have reduced the problem to the similar one concerning the subtree; treat it recursively. The sequence of sizes provides all the necessary information; thus, the depth can be found in O(h), where h is the height of the tree.

To find LCA of x and y, proceed similarly; the root of the current tree if the LCA if one of x or y is the root, or they are contained in different subtrees. Thus, the depth of LCA can also be found in O(h).

Unfortunately, h can be rather large. However, there can be very few operations (less than 60) with k ≥ 2 as the total number of vertices is at most 10¹⁸. We can store the operations with k = 1 in compressed form, as they just attach one edge to the root of tree. Finally, all the operations with little enhancement can be done in O(h'), where h' is the number of operations with k > 1.

F — To Saw Or Not To Saw

If a = c, the answer is simply min(b, d) (the shortest sawtooth length).

Otherwise, suppose a > c. Consider the space between two sawtooths of (c, d)-saws; we may as well consider the (a, b)-saw wrapped up around the space. The ends of the sawtooths of (a, b)-saw form a modular sequence , which is the same set of ends as the periodical sequence with diffence ; thus the (a, b)-saw can be changed to the saw with difference but the same angle of sawtooths. Finally, we arrive at the previous situation with the common difference of ; the saw with the least steep angle of sawtooth will determine the maximal length. Thus, the answer is . Do not forget to use 64-bit integers for multiplication.