Serega's blog

By Serega, 6 years ago, translation, In English,

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

 
 
 
 
  • Vote: I like it
  • +40
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like 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?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is a?

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it -19 Vote: I do not like it

Delete Code

  • »
    »
    6 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any solutions for problem D?

»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Problem C is a good problem .

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Thank you!

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "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, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with this?CODE