### Serega's blog

By Serega, 6 years ago, translation, ,

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 bi, and by equality of bi — descending ai. 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 bi, 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 ai. 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 ci, 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(n2).

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: di, 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|).

Code

• +40

 » 6 years ago, # |   +12 Really fast editorial, thank you. C problem is much harder than usual, I spent more than one hour on it. :(
 » 6 years ago, # |   +6 " 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?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +7 Here is an example: k = 2, n = 8 Indices: 1 2 3 4 5 6 7 8 Elements: 1 2 3 4 9 5 5 6 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.
•  » » » 23 months ago, # ^ |   0 What is a?
•  » » » 8 months ago, # ^ |   0 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
 » 6 years ago, # | ← Rev. 3 →   -19 Delete Code
•  » » 6 years ago, # ^ |   -9 Problem B I don't know why it's wrong???????
 » 6 years ago, # |   0 Any solutions for problem D?
 » 6 years ago, # |   +19 take too much time on understanding the meaning of Problem C.
 » 6 years ago, # |   +9 The problems are translated well , but all problems are too long ! Shortering some problems will be better .
 » 6 years ago, # |   +4 Problem C is a good problem .
 » 6 years ago, # |   0 I couldn't understand Problem A's statement. Can someone simply told me about this problem with sample input analyse?
 » 6 years ago, # |   0 Can someone please explain problem C's statement again? ... I tried but couldn't get it.Thank you!
 » 6 years ago, # |   +3 Can anyone tell me how to prove  if k ≥ 3, only complete graph containing k + 1 vertices satisfies the problem statement''?
 » 4 years ago, # |   0 332B - Maximum Absurdity TestCase 4 1 1 2 2 2 I am not able to understand why 2 4 is wrong answer for above test case. My submission: 12785367
•  » » 4 years ago, # ^ |   0 "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."
•  » » » 4 years ago, # ^ |   0 Feeling foolish did not read problem statement properly.
 » 4 years ago, # |   0 What's wrong with this?CODE