codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1632.md (8326B)


      1 Source: https://codeforces.com/blog/entry/99442
      2 
      3 You can also find video editorials for problems B-D on [competitive__programmer](/profile/competitive__programmer "Specialist competitive__programmer")'s [Youtube channel](https://www.youtube.com/channel/UCnZ5rC2_JY0EuYMGMiAbISg)!
      4 
      5 #### [1632A — ABC](https://codeforces.com/contest/1632/problem/A)
      6 
      7 **Hint 1**
      8 
      9 Only a few strings have the answer "YES".
     10 
     11 **Hint 2**
     12 
     13 For $n \ge 3$, the answer is "NO".
     14 
     15 **Solution**
     16 
     17 Let $n \ge 3$ and the resulting string be $a$. For there to be no palindromes of length greater than $1$, at least all of these inequalities must be true: $a_1 \neq a_2$, $a_2 \neq a_3$, and $a_1 \neq a_3$. Since our string is binary, this is impossible, so the answer is "NO".
     18 
     19 For $n \le 2$, there are 4 strings that have the answer "YES": $0$, $1$, $01$, and $10$; as well as 2 strings that have the answer "NO": $00$ and $11$.
     20 
     21 Time complexity: $O(n)$
     22 
     23 **Solution codes**
     24 
     25 * [C++ code](https://codeforces.com/problemset/submission/1632/144584864).
     26 * [Python code](https://codeforces.com/problemset/submission/1632/144585149).
     27 
     28 #### [1632B — Roof Construction](https://codeforces.com/contest/1632/problem/B)
     29 
     30 **Hint 1**
     31 
     32 The cost of construction is a power of two.
     33 
     34 **Hint 2**
     35 
     36 The cost of construction is $2 ^ k$, where $k$ is the highest set bit in $n - 1$.
     37 
     38 **Solution**
     39 
     40 Let $k$ be the highest set bit in $n - 1$. There will always be a pair of adjacent elements where one of them has the $k$-th bit set and the other one doesn't, so the cost is at least $2^k$. A simple construction that reaches it is $2^k - 1$, $2^k - 2$, $\ldots$, $0$, $2^k$, $2^k + 1$, $\ldots$, $n - 1$.
     41 
     42 Time complexity: $O(n)$
     43 
     44 Bonus: count the number of permutations with the minimum cost.
     45 
     46 **Solution codes**
     47 
     48 * [C++ code](https://codeforces.com/problemset/submission/1632/144585341).
     49 * [Python code](https://codeforces.com/problemset/submission/1632/144585411).
     50 
     51 #### [1632C — Strange Test](https://codeforces.com/contest/1632/problem/C)
     52 
     53 **Hint**
     54 
     55 It is optimal to apply the third operation at most once.
     56 
     57 **Solution**
     58 
     59 It is optimal to apply the third operation at most once, because is does not decrease $a$ and always makes $b \le a$. This means that after we use it, we can only apply the second operation.
     60 
     61 If we don't apply the third operation, the answer is $b - a$.
     62 
     63 Suppose we do apply it. Before that, we used the first and second operations some number of times, let the resulting values of $a$ and $b$ be $a'$ and $b'$ respectively $(a \le a', b \le b')$. The answer in this case will be $(a' - a) + (b' - b) + ((a' \ | \ b') - b') + 1$ $=$ $a' + (a' \ | \ b') + (1 - a - b)$. This is equivalent to minimizing $a' + (a' \ | \ b')$, since $(1 - a - b)$ is constant.
     64 
     65 To do that, we can iterate $a'$ from $a$ to $b$. For a fixed $a'$, we have to minimize $a' \ | \ b'$, the optimal $b'$ can be constructed like this:
     66 
     67 Set $b'$ to zero and iterate over bits from highest to lowest. There are 4 cases:
     68 
     69 * If current bit of $a'$ is $0$ and $b$ is $1$, set the current bit of $b'$ to $1$.
     70 * If current bit of $a'$ is $0$ and $b$ is $0$, set the current bit of $b'$ to $0$.
     71 * If current bit of $a'$ is $1$ and $b$ is $1$, set the current bit of $b'$ to $1$.
     72 * If current bit of $a'$ is $1$ and $b$ is $0$, set the current bit of $b'$ to $1$ and stop.
     73 
     74 This works in $O(\log b)$ and can also be sped up to $O(1)$ using bit manipulation.
     75 
     76 Time complexity: $O(b)$ or $O(b \log b)$
     77 
     78 Bonus 1: solve the problem in $O(\log b)$ or faster.
     79 
     80 Bonus 2: prove that is optimal to have either $a' = a$ or $b' = b$.
     81 
     82 **Solution codes**
     83 
     84 * [C++ code](https://codeforces.com/problemset/submission/1632/144585749) with complexity $O(b \log b)$.
     85 * [C++ code](https://codeforces.com/problemset/submission/1632/144585575) with complexity $O(b)$.
     86 * [Python code](https://codeforces.com/contest/1632/submission/144585797) with complexity $O(b \log b)$.
     87 
     88 #### [1632D — New Year Concert](https://codeforces.com/contest/1632/problem/D)
     89 
     90 **Hint 1**
     91 
     92 Let's call a segment $[l, r]$ bad if $\gcd(a_l \ldots a_r) = r - l + 1$. There at most $n$ bad segments.
     93 
     94 **Hint 2**
     95 
     96 For a fixed $l$, as $r$ increases, $\gcd(a_l \ldots a_r)$ does not increase.
     97 
     98 **Hint 3**
     99 
    100 Suppose you change $a_i$ into a big prime. How does this affect the bad segments?
    101 
    102 **Solution**
    103 
    104 Read the hints above.
    105 
    106 Let's find all of the bad segments. For a fixed $l$, let's find the largest $r$ that has $\gcd(a_l \ldots a_r) \ge r - l + 1$. This can be done with binary search and a sparse table / segment tree. If $\gcd(a_l \ldots a_r) = r - l + 1$, then the segment $[l, r]$ is bad.
    107 
    108 If we change $a_i$ into a big prime, no new bad segments will appear. And all bad segments that have $i$ inside of them will disappear. So we have to find the minimum number of points to cover all of them. This is a standard problem, which can be solved greedily: choose the segment with the smallest $r$, delete all segments that have $r$ in them, and repeat. In our case, this is easy to do because our segments are not nested.
    109 
    110 Time complexity: $O(n \log n \log A)$ with a sparse table, where $A$ is the maximum value of $a_i$.
    111 
    112 Notes:
    113 
    114 There are many different modifications to the previous solution, some of them use two pointers (since segments are not nested) and some of them update the answer on the fly while searching for the bad segments. Using a segment tree and two pointers you can get the complexity $O(n (\log n + \log A))$.
    115 
    116 You can also use the fact that for a prefix, there at most $O(\log A)$ different suffix $\gcd$ values. This leads to another way to find the bad segments.
    117 
    118 **Solution codes**
    119 
    120 * [C++ code](https://codeforces.com/contest/1632/submission/144585868) with segment tree and binary search with complexity $O(n \log n (\log n + \log A))$.
    121 * [C++ code](https://codeforces.com/contest/1632/submission/144585920) with sparse table and two pointers with complexity $O(n \log n \log A)$.
    122 * [Python code](https://codeforces.com/contest/1632/submission/144586001) with segment tree and two pointers with complexity $O(n (\log n + \log A))$.
    123 
    124 #### [1632E2 — Distance Tree (hard version)](https://codeforces.com/contest/1632/problem/E2)
    125 
    126 **Hint 1**
    127 
    128 It is optimal to add edges of type $(1, v)$.
    129 
    130 **Hint 2**
    131 
    132 Try to check if for a fixed $x$ the answer is at most $ans$.
    133 
    134 **Hint 3**
    135 
    136 For a fixed $x$ and answer $ans$, find the distance between nodes that have $depth_v \gt ans$.
    137 
    138 **Hint 4**
    139 
    140 For each node, find two children with the deepest subtrees.
    141 
    142 **Solution**
    143 
    144 Read the hints above.
    145 
    146 Let $f_{ans}$ be the maximum distance between two nodes that have $depth_v \gt ans$. If for some $x$ the answer is at most $ans$, then either $ans \ge depth$ or $\lceil \frac{f_{ans}}{2} \rceil + x \le ans$, since we can add an edge $(1, u)$ where $u$ is in the middle of the path connecting the two farthest apart nodes with $depth_v \gt ans$. Since $f_{ans}$ decreases as $ans$ increases, we can use binary search. Also note that we can use two pointers and increase $ans$ as we increase $x$.
    147 
    148 How to calculate $f_{ans}$? Let's find for each node its two children with the deepest subtrees. Let $a_v$ and $b_v$ be the depths of their subtrees ($a_v \ge b_v$). If there are not enough children, set this values to $depth_v$. If $b_v \gt 0$, do $f_{b_v-1} := \max(f_{b_v - 1}, a_v + b_v - 2 \cdot depth_v)$. After this, iterate $i$ from $n - 2$ to $0$ and do $f_i = \max(f_i, f_{i + 1})$.
    149 
    150 Time complexity: $O(n)$ or $O(n \log n)$ with binary search.
    151 
    152 Note: To solve E1, it is enough to calculate $f_{ans}$ in $O(n)$ or $O(n \log n)$ for each $ans$. One way to do that is to find the diameter of the resulting tree after repeatedly deleting any leaf that has $depth_v \le ans$ ($1$ is also considered a leaf).
    153 
    154 **Solution codes**
    155 
    156 * [C++ code](https://codeforces.com/contest/1632/submission/144586133) for E1 with complexity $O(n ^ 2)$.
    157 * [Python code](https://codeforces.com/contest/1632/submission/144586223) for E1 with complexity $O(n ^ 2)$.
    158 * [C++ code](https://codeforces.com/contest/1632/submission/144586286) for E2 with complexity $O(n)$.
    159 * [Python code](https://codeforces.com/contest/1632/submission/144586358) for E2 with complexity $O(n)$.
    160 
    161 P. S. Solution codes will be published a little later.
    162 
    163 P. P. S. Do not forget to evaluate the problems in the announcement.
    164 
    165 **UPD**: Solution codes have been posted.