Any suggestions, remarks and information about mistakes are welcomed. If you can improve the quality of this tutorial, please write me a private message :)

332A - Down the Hatch!

Since n ≥ 4, one Vasya’s turn does not affect his other turns. Consequently, you should find just the number of positions (0-indexed) in the given string, which indexes are multiples of n and before which there are at least three same symbols.

Asymptotics of the solution — O(|s|)

Code

332B - Maximum Absurdity

Let’s build the array of partial sums, which will permit to find the sum in any segment of the array in O(1). Let's iterate through the number a (the left edge of the leftmost segment) in descending order. Now we need to find among segments of length k, starting from position which index is greater than or equal to a + k, a segment with the maximum sum. Since we search a in descending order, we can maintain this segment during the transition from a to a - 1.

Asymptotics of the solution — O(n).

Code

332C - Students' Revenge

Let’s sort orders ascending b_i, and by equality of b_i — descending a_i. One can assume that in an optimal solution all the orders obeyed by the chairperson go in the sorted list after orders that she hasn’t obeyed (it may be wrong if there are several same orders, but it doesn’t affect parameters of an answer). Let’s iterate through i — the position of the first order in the sorted list, which the chairperson will obey. To the left of this order we should choose p - k orders which the chairperson won’t obey. As we should choose orders with the maximum sum of b_i, we can just choose p - k orders that immediately precede the i-th order. To the right of the i-th order we should choose k - 1 orders which the chairperson will obey. These orders should have the maximum sum of a_i. If we iterate i by descending, we can keep these k - 1 orders in some data structure that can perform basic operations with sets in logarithmic time (for example, multiset in C++).

Asymptotics of the solution — O(nlogn)

Code

332D - Theft of Blueprints

In the problem is given the weighted undirected graph without loops and multiple edges satisfying the following property: for every set S containing k vertices there is exactly one vertex adjacent to all vertices from this set (*) (this vertex is called “adjacent with S”). For any k-element set of vertices we can calculate the special characteristic: the sum of the weights of edges that connect vertices from S with vertex, adjacent with S. It is required to find the mathematical average of the characteristics of all k-element sets of vertices.

One can solve this problem using the following fact (the proof is now available only in the Russian version of this post): if k ≥ 3, only complete graph containing k + 1 vertices satisfies the problem statement. For complete graphs answer is equal to doubled sum of weights of all edges, divided by n. The same way one can calculate answer if k = 1. Now let’s consider the case k = 2. Let’s iterate through the vertex i which is adjacent with our two-element set. Let’s write in ascending order all such numbers j that c_i, j ≠  - 1. Any two different vertices of this list form the set for which vertex i is adjacent, and there are no other such sets of vertices. Looking over all pairs of vertices in this list, we can add characteristics of all these sets to the answer. Since it’s guaranteed that the graph satisfies the property (*), each pair of vertices will be analyzed only once. A similar approach is used in the validator for this problem.

Asymptotics of the solution — O(n²).

Code

332E - Binary Key

Let’s iterate through the number of ones in the key (cnt). One can note that cnt can’t be large than min(|s|, k), as the keys containing more than |s| ones can’t be lexicographically minimal.

Let’s consider the solution of this problem with the fixed cnt. Any complete pass on the key corresponds to the extracting cnt of k scanned symbols of the container, i. e. container is divided into blocks of length k, and the message is divided into blocks of length cnt (last blocks may be shorter). We’ll number the characters in each block of the message from 0 to cnt - 1. We’ll call (q, j)-suffix suffix of q-th block of the message that starts from a position j in this block. Let’s solve the problem with dynamic programming: d_i, j is true if there exists a key, the first i characters of which are zeros and which corresponds to the extracting from container the string that is the result of concatenation of all (q, j)-suffixes of the message. The transitions are based on the filling of i-th position of the key with zero or one (we need to choose the minimum acceptable character). To restore the key you can keep chosen characters for each subtask.

Asymptotics of the solution — O(k·|s|² + |p|).

Code