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

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*|)

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*).

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*)

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*^{2}).

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*|^{2} + |*p*|).

Really fast editorial, thank you. C problem is much harder than usual, I spent more than one hour on it. :(

" Since we search a in descending order, we can maintain this segment during the transition from a to a - 1."

Can you please explain this sentence a bit better?

Here is an example:

We start from a = 5. There is only one another segment (i.e. {5, 6} with indices [7, 8]). We remember it for another steps.

Now we move a to 4. There are one new another segment {5, 5}. We compare it with previous maximum value. In this example {5, 6} is better than {5, 5}, that's why we do nothing.

Then we move a to 3. This time new possible segment {9, 5} (indices [5, 6]) is better than our maximum and we remember it.

What is a?

I followed a approach somewhat like it but getting WA on a test that was not expected though.

Do you see any fault in my approach? 52082864

Delete Code

Problem B I don't know why it's wrong???????

Any solutions for problem D?

take too much time on understanding the meaning of Problem C.

The problems are translated well , but all problems are too long ! Shortering some problems will be better .

Problem C is a good problem .

I couldn't understand Problem A's statement. Can someone simply told me about this problem with sample input analyse?

Can someone please explain problem C's statement again? ... I tried but couldn't get it.

Thank you!

Can anyone tell me how to prove `` if k ≥ 3, only complete graph containing k + 1 vertices satisfies the problem statement''?

332B - Maximum Absurdity

TestCase

4 1

1 2 2 2

I am not able to understand why2 4is wrong answer for above test case. My submission: 12785367"If there are multiple solutions, print the one with the minimum number a. If there still are multiple solutions, print the one with the minimum b."

Feeling foolish did not read problem statement properly.

What's wrong with this?CODE