A. Martian Volleyball

First note that in order to end the game as soon as possible only the currently leading team must get points.

Consider the condition that one of the teams wins. It must score at least k points and have at least 2 points advantage.

So the answer is max(k, min(x, y) + 2) - max(x, y).

B. Painting the Wall

First note that if the maximal length of the continuous segment is L, at least L colors are needed to paint the wall. On the other side L colors is always enough.

Consider a square L × L, fill the first line with integers from 1 to L, fill the following lines with all its possible circular shifts. Use these squares to cover the given wall rectangle like this (L = 4):

Now each vertical and horizontal segment of length L or less has all tiles of different colors. All that is left is to bring back the lamps.

C. Magic Artifact

Let us denote advantage that Maxim gets if he finds artifact as c_i, so c_i = a_i - b_i.

Let Maxim first complete levels in order 1, 2, ..., n. If he finds the artifact at the i-th level, the time he needs to complete the game is equal to b_j plus c₁ + ... + c_i. So the expected time of completing the game is:

b₁ + ... + b_n + p₁·c₁ + p₂·(c₁ + c₂) + ... + p_n·(c₁ + ... + c_n).

b₁ + ... + b_n doesn't depend on level order, so let us try to make the rest as small as possible. Expanding the sums, we get sum of all c_i·p_k for such i, k that i ≤ k.

Let us now swap levels i and i + 1 in our order. For the given i among c_i·p_k terms only the one equal to c_i·p_i + 1 changes — it is replaced with c_i + 1·p_i. If the order was optimal, it must be c_i·p_i + 1 ≤ c_i + 1·p_i, in the other case it was optimal to swap them and get a better answer. Transform this to:

c_i / p_i ≤ c_i + 1 / p_i + 1.

In the optimal answer for all i from 1 to n - 1 this inequality must be satisfied. Therefore it is optimal to sort levels according to the key c_i / p_i. Note that if p_i = 0, you may consider c_i / p_i = ∞.

Sorting according to the key c_i / p_i should be done carefully. If the fractions are compared using floating-point division, the case c_i = p_i = 0 will lead to error because 0 / 0 = NaN. If the fractions are compared using the comparator c_i·p_k < c_k·p_i, the case c_i = p_i = 0 will also lead to error because the result of that comparison will always be false. That means that levels with c_i = p_i = 0 should be handled separately. Such levels can be completed at any time because they do not affect the result besides fixed terms b_i. For example, they can be placed at the end.

After sorting the desired expected value can be found using the formula above, use prefix sums for c_i to get it fast.

D. Memory Manager

First for each query q_i let us find go_i — the minimal j, such that among q_j, q_j + 1, ..., q_i there are at most k different blocks — that would mean that it is possible to place pointers before the j-th query in such way that queries j, j + 1, ..., i are performed immediately. This can be made in O(sum(|q_i|)), using, for example, two pointers.

Now let us use dynamic programming, denote as dp_i the minimal time needed to perform the first i queries. If go_i = 0 then dp_i = 0. If the equation is not satisfied, dp_i = min_{j = goi..i}(dp_j - 1 + s_j) — we choose the query j to perform the pointer movement before. Since values go_i do not descend, this value can be maintained using either std::set of dp_j - 1 + s_j, or queue with minimum query support.

E. LISA

First let us consider the problem for given two strings: to solve it calculate the number of occurrences of each letter in the first string, the number of occurrences of each letter in the second string, not including the first letter of the first string and the last letter of the second string, that must be used any way. Now the answer is the product of string lengths, decreased by the sum of values cnt1[letter] * cnt2[letter] for each letter. Let us leave proof as an exercise, such problem was at Northern Subregional Contest of NEERC 2015 http://neerc.ifmo.ru/archive/2015/northern/north-2015-statements.pdf, Problem C. Unlimited participants could solve this problem at Three Quaterfinals Cup.

For n strings similar ideas can be used. Put all strings to a prefix trie, all strings to a suffix trie, the total number of ways to get a string is the product of the number of vertices in these tries. What we need to subtract is similar product of number of occurrences of letters in tries, first/last letters of each word must not be considered.

Now we need to answer segment queries. Let us make sqrt-decomposition, divide all strings to groups based on sum of their lengths. Let us greedily add strings to a group until their sum of lengths is more than sqrt(total sum of lengths). Note that the last string can have a big length.

Now use Mo's algorithm, sort queries using the block of the left end as a key, move right end only forward between left end block changes. To add/remove a string to a trie one must maintain the number of active vertices in a trie subtree for each vertex, and the number of entries of letters to a trie.