Editorial of Educational Codeforces Round 6

Правка en4, от Edvard, 2016-01-22 00:51:22

620A - Professor GukiZ's Robot

Easy to see that the answer is max(|x1 - x2|, |y1 - y2|).

С++ solution

Complexity: O(1).

620B - Grandfather Dovlet’s calculator

Let's simply iterate over all the values from a to b and add to the answer the number of segments of the current value x. To count the number of segments we should iterate over all the digits of the number x and add to the answer the number of segments of the current digit d. These values can be calculated by the image from the problem statement and stored in some array in code.

C++ solution

Complexity: O((b - a)logb).

620C - Pearls in a Row

Let's solve the problem greedily. Let's make the first segment by adding elements until the segment will be good. After that let's make the second segment in the same way and so on. If we couldn't make any good segment then the answer is  - 1. Otherwise let's add all uncovered elements at the end to the last segment. Easy to prove that our construction is optimal: consider the first two segments of the optimal answer, obviously we can extend the second segment until the first segment will be equal to the first segment in our construction.

C++ solution

Complexity: O(nlogn).

620D - Professor GukiZ and Two Arrays

We can process the cases of zero or one swap in O(nm) time. Consider the case with two swaps. Note we can assume that two swaps will lead to move two elements from a to b and vice versa (in other case it is similar to the case with one swap). Let's iterate over all the pairs of the values in a and store them in some data structure (in C++ we can user map). Now let's iterate over all the pairs bi, bj and find in out data structure the value v closest to the value x = sa - sb + 2·(bi + bj) and update the answer by the value |x - v|. Required sum we can find using binary search by data structure (*map* in C++ has lower_bound function).

C++ solution

Сложность: O((n2 + m2)log(n + m)).

620E - New Year Tree

Let's run dfs on the tree and write out the vertices in order of their visisiting by dfs (that permutation is called Euler walk). Easy to see that subtree of any vertex is a subsegment of that permutation. Note that the number of different colours is 60, so we can store the set of colours just as mask of binary bits in 64-bit type (*long long* in C++, long in Java). Let's build the segment tree over the permutation which supports two operations: paint subsegment by some colour and find the mask of colours of some segment.

С++ solution

Complexity: O(nlogn).

Теги education round 6, editorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский Edvard 2016-01-22 02:01:59 2211
en4 Английский Edvard 2016-01-22 00:51:22 646
en3 Английский Edvard 2016-01-21 23:59:52 785
ru8 Русский Edvard 2016-01-21 23:58:33 6 Мелкая правка: '2 \cdot (b[i] + b[j])$ и обнов' -> '2 \cdot (b_i + b_j)$ и обнов'
ru7 Русский Edvard 2016-01-21 23:52:05 3 Мелкая правка: 'б (за $O(n^2)$). Тепер' -> 'б (за $O(nm)$). Тепер'
en2 Английский Edvard 2016-01-21 23:50:53 647
ru6 Русский Edvard 2016-01-21 23:44:22 2 Мелкая правка: 'новый хорощий подотре' -> 'новый хороший подотре'
en1 Английский Edvard 2016-01-21 23:34:37 694 Initial revision for English translation
ru5 Русский Edvard 2016-01-21 23:33:29 2 Мелкая правка: 'гментов, наобходимой ' -> 'гментов, необходимой '
ru4 Русский Edvard 2016-01-21 23:29:31 2 Мелкая правка: 'x(|x_1-x_2, y_1-y_2|)$' -> 'x(|x_1-x_2|, |y_1-y_2|)$'
ru3 Русский Edvard 2016-01-21 23:25:46 1987 Мелкая правка: 'но делать делать во' -
ru2 Русский Edvard 2016-01-21 22:22:44 615
ru1 Русский Edvard 2016-01-21 20:03:21 2438 Первая редакция (опубликовано)