Hello everyone!

November 14, 19:30 MSK will take place Codeforces Round #212 (Div. 2), which was prepared by group of authors from Saratov State University: Artem Sedanov (FunkyCat), Sergey Sukhov (Serega), Olga Chikatueva (Helga), Dmitriy Zaycev (My-my).

We thank coordinator of Codeforces rounds Gerald Agapov (Gerald) for useful hints and Maria Belova (Delinur) for translation of problem's statements into English.

Good luck and high rating to all!

UPD1. In this round will be used dynamic scoring system (see here).

UPD2. Tutorial is published here.

UPD3. Rating is updated. We congratulate the winners who solved four problems:

1. CleRIC

2. i_must_learn_matan

3. Dshavn

4. gzh1998n

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

Hello everyone!

In several days (July 24, 19:30 MSK) will take place Codeforces Round #193 (Div. 2), which I have prepared. Those who has already reached the first division traditionally can participate in the round out of the competition.

I would like to thank Vitaliy Gridnev (gridnevvvit), Pavel Kunyavskiy (PavelKunyavskiy) and Dmitriy Ivanov (DmitriyIvanov) for testing of problemset, coordinator of Codeforces rounds Gerald Agapov (Gerald) for useful hints and Maria Belova (Delinur) for translation of statements into English.

Good luck and high rating to all!

UPD1. The score distribution in this round will be dynamic (see here). In our opinion problems are sorted according to their difficulty.

UPD2. Analysis of problems is publisched.

UPD3. Rating is updated. Congrutalations to the winners who solved 4 problems:

Williamacm

Windseeker

Tifuera

seen

Problem A. Epic Game.

Author's solution: http://pastebin.com/zRiQwy6u

It's enough just to model the described game to solve this problem. You can search a greatest common divisor in any reasonable way.

Problem B. Before Exam.

Author's solution: http://pastebin.com/kBjCwiiD

Let's consider solution of the task for maximum level of profience (for minimum level solution is similar). It's clear that maximum level can be reached either in a card that has fallen one somebody's lot already or in a card about that we know nothing. In the first case we can just calculate levels of profiency for all cards from input and choose maximal level. The second case is more tricky. Let's sort all the theorems that weren't mentioned in cards from input in order of non-increasing of profiency's level. It's obvious that sought-for card consists of first theorems in sorted list. This case is possible if the number of different cards mentioned in input is stictly less than k. For example, in the test

3 2
1 2 3
2
1
2

we can't consider a card containing third theorem because both examination cards are already known.

Problem C. Education Reform

Author's solution: http://pastebin.com/eZhJYGpC

This problem can be solved by dynamic programming. Let's sort all subjects in order of complexity's non-increasing. Let d <  / span > [ < spanstyle = "" > i <  / span > ][ < spanstyle = "" > j <  / span > ][ < spanstyle = "" > z <  / span > ] is the greatest summary number of exercises, that can be given, if timetable contains exactly z subjects from among of first i subjects (in order of sort), involves ith subject and number of exercises in ith subject is equal to a_i + j. Recurrent correlations are based on search of subject that will occupy ( < spanstyle = "" > z <  / span >  - 1)th day in timetable.

For restoration of answer you should save source numbers of subjects.

Asymptotic complexity is O(m²·n·max(b_i - a_i)).

Problem D. String Transformation

Author's solution: http://pastebin.com/puGK1WYh

If lengths of input strings aren't equal, we can at once output "-1 -1" and complete execution of a program. Otherwise let number n is equal to the length of input strings.

Let's iterate through the number i. We should find (in O(1)) the such smallest number j, that substing b[0... n - i - 1] can be represented as a[i + 1... j - 1] + r(a[j... n - 1]). In order to do that, let's calculate the prefix function (p[i]) for string s₁ = r(a) + ' 0' + b and z-function (z[i]) for string s₂ = b + ' 0' + a. It's clear that for fixed i value of j is equal to n - p[2n - i - 1], and substrings a[i + 1... j - 1], b[0... j - i] must coincide at that (1). The last condition can be easily verified through using of calculated z-function. You can also trivial prove the next statement: if the property (1) is not satisfied by fixed i for the chosen j, then it will not meet for bigger j.

Asymptotic complexity is O(n).

Hello everyone!

Welcome to the Codeforces Beta Round #90! I (Sergey Sukhov) and Alexander Ignatyev (aiMR) have prepared for you today's contest. We thank Artem Rakhov (RAD) for help and useful hints, Mariya Belova (Delinur) for translation of statements, as well as Michael Mirzayanov (MikeMirzayanov) for opportunity to conduct this round.

Good luck and high rating!