To get the maximal possible result you have just to sort summands in non-decreasing order by coefficients (counting coefficients with preceeding signs + and -). You should not pay attention to 'a++' or '++a'! The question is: why is it true? 

First, consider an expression with only 'a++'. Then our assertion is obvious: it is better to multiply 'a' by small coefficients when it has small value, and by large coefficients, when it becomes larger. The same also takes place in case of negative coefficients or a-value. Of course, it is not a rigorous proof. I hope you will think on it if you haven't get it yet.

Second, consider the expression k * a +  +  + k *  +  + a, where k is some coefficient equal for both summands. Let initial value of 'a' equals to a₀. Calculating the value of the expression both ways, we obtain: k * a₀ + k * (a₀ + 2) = k * (a₀ + 1) + k * (a₀ + 1). So in this case the order is immaterial.

Third, let us have the expression k * a +  +  + l *  +  + a, where k and l are two distinct coefficients. This expression can have two different values: k * a₀ + l * (a₀ + 2) and k * (a₀ + 1) + l * (a₀ + 1). The first value is greater than the second one if and only if k < l. We can deal with the expression k*++a+l*a++ analogously.

Thus if we have two succesive summands with the same coefficient, we may swap or not to swap them. If we have two succesive summands with distinct coefficients, we must put the summand with a smaller coeficient first. Applying these considerations while it is necessary, we get a sequence of summands sorted by coefficients. 

For this problem, the greedy solution is acceptable. Process given numbers consequently until 1 is found. Then continue to process searching for 2, then for 3, etc.

The authors solution takes O(n²) time and O(n²) memory. Solutions with time and O(n) memory are also acceptable.

Let us reformulate the problem. Given a set of segments on a line, and the task is to find the largest subset such that segments in it don't intersect ``partially''. Two segments [a, b] and [c, d] intersect partially, if, for instance, a < c < b < d.

Take all the ends of the given segments, sort them, and compute the dynamics: d_l, r is the largest possible size of such subset that segments in don't intersect partially and located between the l-th end and the r end (in sorted order), inclusively. We want to compute d_l, r having already computed d_i, j for all l ≤ i ≤ j ≤ r, but [i, j] ≠ [l, r]. First put d_l, r = d_{l + 1, r} if we don't take segments with the left end in l. Now process the segments with the left end in l. If the segment [l, r] exists, we undoubtedly take it to our set. If we take another segment, say, [l, i], where i < r, look at segments [l, i] and [i, r] (we have  answers for them already computed) and try to update d_l, r. The asymptotics is O(n²), because  the total number of left ends is O(n). Then you have to output the certificate, i.e. the optimal set itself. It can be done in the standard way.

The flies can NOT see each other iff they are in opposite vertices. You may use multiple ways to check this. For instance, you can check the Manhattan distance |x₁ - x₂| + |y₁ - y₂| + |z₁ - z₂| = 3 or the Euclidian distance . You can check if all three coorditanes are distinct (x1 != x2) && (y1 != y2) && (z1 != z2), or just (x1^x2)+(y1^y2)+(z1^z2) == 3!

The number of ways to put b items into a boxes is, of course, a^b. So we have an acyclic game for two players with positions (a, b) for which a^b < n. Unfortunatly, there exists an infinite number of such positions: a = 1, b is any. But in this case, if 2^b ≥ n, it is a draw position, because the only way for both players (not leading to lose) is to increase b infinitely. 

Another special case is a position with b = 1 and rather large a. Namely, if , there is also only one move from this position - to increase a. If a = n - 1 the position is losing, if a = n - 2 it is winning, for a = n - 3 it is losing again and so on.

Thus we have two kinds of positions to deal with them specially. The number of other positions is not very large, and you can compute the standard dynamics for acyclic games for them.

The simple modelling of frog's jumps works too long, because n can be 10⁹. The right solution is to count for each frog a number of smashed mosquitoes by checking divisibility of numbers of hills with mosquitoes by d_i.

What can I say about problem G? You should parse a given function and calculate its value for all values of n. Of course, it is impossible to do it just implementing the recursion, because this can work too long (see example with Fibonacci sequence). So you should use dynamic programming.

You have to calculate all products i * j, and output them in the system of notations with radix k.

Consider only the part of the graph reachable from 1. The task is to find the largest number t, such that a chosen set of vertices is reachable only at moments divisible by t. Suppose we have built  such a set S₀. Look at sets S₁, S₂, ..., S_t - 1 of all vertices reachable at  moments having remainders 1, 2, ..., t - 1 modulo t, respectively. One can easily check that these sets are disjoint, and their union coinside with the set of all reacheble vertices. Clearly, that the edge from u to v can exist only when u and v belong to consequetive sets, i.e. , , k + 1 is taken modulo t.

For each vertex v, find a distance d_v from 1 to v (if there is multiple paths, choose any, for example, by dfs). If the edge exists from u to v, it must be . By analyzing all the edges, we come to the conclusion that the optimal value of t equals to the greatest common divisor of the numbers |d_u + 1 - d_v|. To find the set S₀ is not very difficult now.

The simplest solution is to find two numbers l and r - the length of the longest common prefix and the length of the longest common suffix of two strings, respectively. If l + 1 < n - r then there is no solution. Here n is the length of the first string. Otherwise we should output positions from max(n - r, 1) to min(l + 1, n).

Problem K

Problem K has a great number of different solutions, so I'm surprised that there was a lack of them during the contest. Solutions with time O(k⁴) and even some O(k⁵) solutions with optimization were acceptable, but KADR describes even better solution in O(k³) (http://mirror.codeforces.com/blog/entry/793).