Codeforces Round #586 Editorial

Правка en1, от wrg0ababd, 2019-09-19 22:31:30

Problem A

It's easy to see that letter $$$\text{z}$$$ contains only in $$$\text{zero}$$$ and $$$\text{n}$$$ contains only in $$$\text{one}$$$, so we should print $$$1$$$ $$$count(\text{n})$$$ times and then $$$0$$$ $$$count(\text{z})$$$ times.

Problem B

Let's note that $$$\frac{(xy) \cdot (xz)}{(yz)} = x^2$$$ if $$$x, y, z > 0$$$. In this problem $$$n \ge 3$$$, so we can get each value this way.

Problem C

The main idea of this task is that Mike never moves. Lets fix $$$k$$$, there two cases:

1) $$$s[k] \ge s[i]$$$ for all $$$i < k$$$, in this case $$$s[k, k] \le s[l, r]$$$ for all $$$l \le k$$$ и $$$r \ge k$$$, so Ann can't make her first move (Mike wins).

2) There is $$$i < k$$$ such that $$$s[i] < s[k]$$$. In this case Ann can move with substring $$$s[i, r]$$$. If we choose the least possible $$$i < k$$$ such that $$$s[i]$$$ is minimal, we will deprive Misha of the opportunity to make a move (Ann wins)

Final solution: for all $$$k$$$ we should check whether $$$s[k]$$$ is the least on substring $$$s[0, k]$$$. It can be done with one for in wich we should maintain a minimum on prefix. Complexity $$$O(|s|)$$$.

Problem D

Let all numbers in $$$B$$$ be odd. If two vertices $$$i$$$ and $$$j$$$ are connected, then they have different parity, hence our graph is already bipartite (first part is even vertices, second -- odd vertices).

Now let's see that if we choose an integer $$$k > 0$$$, multiply all elements of the set by $$$2^k$$$ and build a new graph on this set, our new graph will also be bipartite. Proof: consider $$$k$$$-th bit. An edge connects only vertices with different $$$k$$$-th bit, so partition is clear.

So, we found out that if all elements in $$$B$$$ have equal power of $$$2$$$ in their factorization, then this set builds a bipartite graph. What about other cases? Let $$$a, b \in B$$$. They form a cycle with $$$len = \frac{lcm(a, b)}{a} + \frac{lcm(a, b)}{b} = \frac{a}{gcd(a, b)} + \frac{b}{gcd(a, b)}$$$. It's easy to see that $$$len$$$ is odd iff $$$a$$$ and $$$b$$$ contain different powers of $$$2$$$ in their factorization, so we just proved that there is no other cases.

Finally, the solution is to find maximum power of $$$2$$$ that divides $$$B_i$$$ for all $$$1 \le i \le n$$$, find the largest subset $$$B'$$$ with equal power of $$$2$$$ and drop $$$B \setminus B'$$$. Complexity $$$O(n \log{maxB})$$$.

Problem E

Let's note that if you visit a vertex $$$u$$$ located on a loop, you can always add the numbers on vertices in this loop to answer and you can also add the numbers on vertices between $$$u$$$ and $$$s$$$. It is true because you can just visit $$$u$$$, go through the vertices of the cycle, return to $$$u$$$ and then go back to $$$s$$$. But if from the given vertex we can't get to the cycle, then we can't return back. So the problem is to сhoose the best branch leading only to the leaves. And from this point there are several solutions for this problem. Let's discuss one of them:

Let $$$e_u$$$ be the maximum extra value we could get, if we are in $$$u$$$ and we want to go only to leaves. First of all just put all the leaves except $$$s$$$ in stack or queue. Then we choose the next vertex $$$u$$$ from our queue and look at its parent $$$v$$$. Let's decrease $$$v$$$'s degree and update $$$e_v = \max(e_v, e_u + w_u)$$$. If $$$v$$$'s deegre became $$$1$$$, it means that $$$v$$$ is the leave now, so let's push it in our queue, if it isn't $$$s$$$. It looks like at each step, we just erase one leave from our graph and recompute $$$e$$$ value for its parent.

At the end, we considered all vertexes which are not belong to the cycles and not belong to the pathes from $$$s$$$ to one of the cycles. So we need to sum up the biggest $$$e_u$$$ with the sum of all $$$w_v$$$, where $$$v$$$ wasn't considered during our leaves removing.

There are also solutions that build edge-connectivity components and compute the value using DP on tree.

Problem F

Notice that element $$$a$$$ is an ancestor of an element $$$b$$$ when it's minimum on a subsegment from $$$a$$$ to $$$b$$$. Count amount of ancestors for every element in initial permutation. Now, when you remove element $$$l$$$ from the left, all elements between it and the leftmost element smaller than $$$l$$$ now have one ancestor less. When you move it to the right, all elements between it and the rightmost element smaller than it have one ancestor more. You can store amounts of ancestors in a segment tree with lazy propagation.

Problem G

Not ready yet

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский wrg0ababd 2019-09-21 20:38:37 38 Tiny change: '[tutorial:' -> '**Update: editorial for G is out**\n\n[tutorial:'
ru10 Русский wrg0ababd 2019-09-21 20:38:14 34 Мелкая правка: '[tutorial:' -> '**Обновление: разбор G готов**\n\n[tutorial:'
en4 Английский wrg0ababd 2019-09-20 17:48:17 4475
ru9 Русский wrg0ababd 2019-09-20 17:47:58 4888
ru8 Русский wrg0ababd 2019-09-19 23:37:30 8 Мелкая правка: 'едков для элемента.' -> 'едков для каждого элемента.'
ru7 Русский wrg0ababd 2019-09-19 23:18:11 142
ru6 Русский wrg0ababd 2019-09-19 23:13:45 11 Мелкая правка: ', где $u$ ~--- рассмо' -> ', где $u$ --- рассмо'
ru5 Русский wrg0ababd 2019-09-19 23:10:57 2 Мелкая правка: 'ветствующи[ букв.\n\n' -> 'ветствующих букв.\n\n'
en3 Английский wrg0ababd 2019-09-19 23:05:22 4 Tiny change: 'ew amount ancestor for eleme' -> 'ew amount of ancestors for eleme'
en2 Английский wrg0ababd 2019-09-19 23:04:44 184
ru4 Русский wrg0ababd 2019-09-19 23:03:11 183
ru3 Русский wrg0ababd 2019-09-19 22:56:39 78
ru2 Русский wrg0ababd 2019-09-19 22:55:15 9087 Мелкая правка: 'ветствующий букв.\n\n' -> 'ветствующи[ букв.\n\n'
en1 Английский wrg0ababd 2019-09-19 22:31:30 4364 Initial revision for English translation
ru1 Русский wrg0ababd 2019-09-19 22:30:55 4364 Первая редакция (опубликовано)