2189.md (21228B)
1 Source: https://codeforces.com/blog/entry/150452 2 3 Thank you for participating in our round! We hope you enjoyed the problems. We are really sorry for the inconveniences caused by the English statement of problem B. 4 5 **Fun facts** 6 7 1. A total of 30 problems were proposed for this round 8 2. E was proposed as C, and C as B 9 10 [2189A - Table with Numbers](/contest/2189/problem/A "Codeforces Round 1075 (Div. 2)") 11 12 Idea: [Fakewave](/profile/Fakewave "Master Fakewave") 13 14 **Solution** 15 16 Note that maximizing the sum of numbers in the table is equivalent to maximizing the number of chosen pairs that specify a valid cell. 17 18 Without loss of generality, we assume that $h \leq l$. For any cell of the table $(x, y)$, $1 \leq x \leq h$, $1 \leq y \leq l$. Let $cnt_h$ be the number of elements in the array not exceeding $h$, and $cnt_l$ be the number of elements in the array not exceeding $l$. Then, firstly, the answer does not exceed $cnt_h$, since each pair must contain a number not exceeding $h$. Conversely, the answer does not exceed $\displaystyle \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$, since both numbers in each pair must not exceed $l$. It remains to be seen that $\displaystyle min(cnt_h, \Big\lfloor \frac{cnt_l}{2} \Big\rfloor)$ pairs can be obtained. To do this, let's consider two cases. 19 20 * if $\displaystyle cnt_h \leq \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$, then it is sufficient to pair each number $x \leq h$ with its own number $h \lt y \leq l$, and there will be $cnt_h$ pairs. This can be done since there are at least as many suitable numbers $y$ as there are suitable $x$. 21 * if $\displaystyle cnt_h \gt \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$, then we need to pair each number $h \lt y \leq l$ with its own number $x \leq h$. After this, split the remaining numbers $x \leq h$ into pairs (there may be one extra number left over). We'll get exactly $\displaystyle \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$ pairs. 22 23 **Code** 24 25 [359457886](/contest/2189/submission/359457886 "Submission 359457886 by Akulyat") 26 27 **Rate the problem** 28 29 Amazing 30 31 Good 32 33 Ok 34 35 Bad 36 37 Terrible 38 39 [2189B - The Curse of the Frog](/contest/2189/problem/B "Codeforces Round 1075 (Div. 2)") 40 41 Idea: [furt1ve](/profile/furt1ve "Specialist furt1ve"), [Fakewave](/profile/Fakewave "Master Fakewave") 42 43 **Solution** 44 45 Note that the problem is equivalent to minimizing the number of rollbacks to reach a point with a number $\geq x$. (Consider the moment when the frog first reached the point $\geq x$. Instead of a full jump, the frog could have jumped not the full distance, but exactly to the point $x$). We then assume that the frog always jumps $a_i$ units forward using the $i$-th type of jump. 46 47 First, the frog can use the $i$-th type of jump $b_i-1$ times without any rollbacks. Let $r$ be the number of units remaining to the number $x$ after these jumps (if $r \leq 0$, then $0$ rollbacks are required). 48 49 Now, any jump will cause a rollback. However, note that after one jump with rollback, if we used the $i$th type of jump, we can use the same jump $b_i-1$ more times without rollbacks. After that, we'll find ourselves in the same situation (any jump creates a rollback), but we have moved $a_ib_i-c_i$ units. Therefore, it's always worth using the jump with the maximum value of $a_ib_i-c_i$. 50 51 Let $m = \max(a_ib_i-c_i)$ over all $i$ from $1$ to $n$. Then, if $m \leq 0$, we can't move forward (as we first get a rollback of $c_i$, and only then move by $a_ib_i$), and the answer is $-1$. Otherwise, $\displaystyle \Big\lceil \frac{r}{m} \Big\rceil$ rollbacks will be required. 52 53 **Code** 54 55 [359458220](/contest/2189/submission/359458220 "Submission 359458220 by Akulyat") 56 57 **Rate the problem** 58 59 Amazing 60 61 Good 62 63 Ok 64 65 Bad 66 67 Terrible 68 69 [2189C1 - XOR Convenience (Easy Version)](/contest/2189/problem/C1 "Codeforces Round 1075 (Div. 2)") 70 71 Idea: [Fakewave](/profile/Fakewave "Master Fakewave") 72 73 **Solution** 74 75 First, note that $p_i = p_j \oplus i$ is equivalent to $p_i \oplus i = p_j$. For $i = n-1$, the only possible $j$ is $j = n$. Let's try to construct a permutation such that for all $i$, the corresponding $j$ is $j = n$. That is, we want to ensure that for all $i \geq 2$, the condition $p_i \oplus i = p_n$ holds. Take $p_n = 1$. Then we notice that at position $2k$, the value must be $2k \oplus 1= 2k+1$, and at position $2k+1$, the value must be $(2k+1) \oplus 1 = 2k$. Thus, the numbers split into pairs $2k$ and $2k+1$. 76 77 Let's examine two cases: 78 79 1. If $n$ is even, take $p_1 = n$, $p_{2k} = 2k+1$, $p_{2k+1} = 2k$ ($1 \leq k \leq \frac{n}{2} - 1$); 80 2. If $n$ is odd, take $p_1 = n-1$, $p_{2k} = 2k+1$ ($1 \leq k \leq \frac{n-1}{2}$), $p_{2k+1} = 2k$ ($1 \leq k \leq \frac{n-3}{2}$). 81 82 The cases differ in the number remaining for $p_1$. 83 84 For example, for $n = 9$: $[8, 3, 2, 5, 4, 7, 6, 9, 1]$, for $n = 10$: $[10, 3, 2, 5, 4, 7, 6, 9, 8, 1]$. 85 86 **Code** 87 88 [359458251](/contest/2189/submission/359458251 "Submission 359458251 by Akulyat") 89 90 **Rate the problem** 91 92 Amazing 93 94 Good 95 96 Ok 97 98 Bad 99 100 Terrible 101 102 [2189C2 - XOR-convenience (Hard Version)](/contest/2189/problem/C2 "Codeforces Round 1075 (Div. 2)") 103 104 **Solution** 105 106 First, let's prove that no example exists when $n = 2^x$ ($x$ is an integer). 107 108 Suppose $n$ is at position $i$. Assume $i \lt n$. Then $p_i \oplus i = p_j$ for some $j$. But $p_i \oplus i \ge n$, since $p_i = n = 2^x$, while $p_j \lt n$---a contradiction. Hence $i = n$. But then $p_{n-1} = p_n \oplus (n-1)$. However $p_n \oplus (n-1)$ is larger than $n$, while $p_{n-1}$ is smaller---again a contradiction. 109 110 For $n \neq 2^x$, we show that an example does exist. 111 112 Consider the examples from part C1. Notice that for odd $n$, the example works, because $p_1 = n-1$, and somewhere later the number $n$ occurs, and $n \oplus 1 = (n-1)$. Now consider the example for even $n$. 113 114 Write $n = 2^x + r$, where $r \lt 2^x$ (in other words, $x$ is the highest bit of $n$). Then let us swap $p_1$ and $p_r$. Let's see what has changed. Since for all $i \ge 2$ earlier the only $j$ was $n$, the only number that could be broken is the one at position $r$. But now $p_r = n$. Notice that $2^x \oplus r = n$, and the number $2^x$ is at position $2^x+1$. Thus, for $i = r$, a suitable $j$ is now $j = 2^x+1 \gt r$. 115 116 It remains to check that $i = 1$ has a suitable $j$. Take $j = r + 1$. Since $n$ is even, $r$ is even. Then $p_j = r$ and $p_1 = r+1$. Indeed: $r+1 = r \oplus 1$. 117 118 **Code** 119 120 [359458288](/contest/2189/submission/359458288 "Submission 359458288 by Akulyat") 121 122 **Rate the problem** 123 124 Amazing 125 126 Good 127 128 Ok 129 130 Bad 131 132 Terrible 133 134 [2189D1 - Little String (Easy Version)](/contest/2189/problem/D1 "Codeforces Round 1075 (Div. 2)") 135 136 Idea: [Fakewave](/profile/Fakewave "Master Fakewave"), [yanb0](/profile/yanb0 "Master yanb0") 137 138 **Solution** 139 140 Let's consider which permutations $p$ satisfy the condition of the string $w$. It is obvious that if $w_1 = \texttt{0}$ or $w_n = \texttt{0}$, there are no suitable $p$ (in any permutation, there is a subsegment with only the number $0$ and a subsegment with all numbers), so we will assume that $w_1 = w_n = \texttt{1}$. Let's construct $p$, starting with $p = [0]$ and sequentially inserting the numbers $1, 2, \ldots, n - 1$ into some positions. 141 142 Suppose we have placed the numbers $0, 1, \ldots, k - 1$ and are now going to insert the number $k$ relative to them. We have $k + 1$ options for where to insert it. 143 144 If we insert $k$ before all the numbers or after all the numbers, we can always choose all remaining numbers as a segment and get $\operatorname{mex} = k$ (note that inserting subsequent numbers will not affect the $\operatorname{mex}$ of this segment, since all subsequent values are $ \gt k$). 145 146 However, if we insert $k$ between some values, we will have a situation where there is a value $ \lt k$ both to the left and to the right of $k$. Then, to achieve $\operatorname{mex} = k$, we need to collect all numbers $ \lt k$, but since they exist both to the left and to the right, we will include $k$, resulting in $\operatorname{mex} \gt k$. 147 148 In total, we have $2$ options for ensuring $w_k=1$, and $k-1$ options for $w_k=0$. We have derived that 149 150 $f(w) = \prod_{i = 1}^{n - 1}\begin{cases} 2 &\text{if } w_i = \texttt{1} \\ i - 1 &\text{otherwise}\end{cases}$ 151 152 In this version of the problem, $w = s$, so we only need to check whether $f(w)$ is divisible by $c$. To do this, we will iterate through all $i$ and reduce $c$ by the greatest common divisor of the current factor and the number $c$. If we end up with $c = 1$, then the answer is $-1$. Otherwise, the answer is $f(w)$. 153 154 **Code** 155 156 [359458322](/contest/2189/submission/359458322 "Submission 359458322 by Akulyat") 157 158 **Rate the problem** 159 160 Amazing 161 162 Good 163 164 Ok 165 166 Bad 167 168 Terrible 169 170 [2189D2 - Little String (Hard Version)](/contest/2189/problem/D2 "Codeforces Round 1075 (Div. 2)") 171 172 **Solution** 173 174 From D1 we have: 175 176 $f(w) = \prod_{i = 1}^{n - 1}\begin{cases} 2 &\text{if } w_i = \texttt{1} \\ i - 1 &\text{otherwise}\end{cases}$ 177 178 We will calculate the product of the multiplicative terms for all symbols $s$ that are given (\texttt{0} or \texttt{1}), and we will call this number $b$; the product of the remaining terms will be called $x$. The remaining symbols can be chosen, so we need to find the smallest value 179 180 $bx = b\prod_{i \in [1, n - 1], s_i = \texttt{?}}\begin{cases} 2 \\ i - 1\end{cases}$ 181 182 that is not divisible by $c$. We can eliminate $b$, $x$ must not be divisible by $c' = \frac{c}{\gcd(b, c)}$. (In the implementation, to obtain $c'$, we divide $c$ by the gcd with each term of the product $b$ to avoid overflow.) If we can choose $s_2$, we will choose $s_2 = \texttt{1}$, which will make one of the terms in the product equal to $1$ — this will not cause divisibility and will not increase the number. In the end, we need to choose for several $j \ge 2$ (for $j = i - 1$, where $s_i = \texttt{?}$) to multiply $x$ either by $2$ or by $j$, so that the product is minimal and not divisible by $c'$, and the answer will be $bx$. 183 184 Let's consider two cases. 185 186 1. $c'$ is a power of $2$. For all even $j$, we will choose to multiply by $2$, since multiplying by $2$ instead of a positive even number will not cause divisibility and will not increase the product. We will greedily choose to multiply by $2$ for the largest of the remaining $j$ as long as possible (while $c'$ still does not divide $x$) to minimize $x$. 187 2. $c'$ is not a power of $2$. Then, by choosing to multiply by $2$ each time, $x$ will not be divisible by $c'$, and the product will be minimal, since each time we chose the smaller of the possible factors ($2 \le j$). 188 189 Final asymptotic complexity: $\mathcal{O}(n \log n)$. 190 191 **Code** 192 193 [359458348](/contest/2189/submission/359458348 "Submission 359458348 by Akulyat") 194 195 **Rate the problem** 196 197 Amazing 198 199 Good 200 201 Ok 202 203 Bad 204 205 Terrible 206 207 [2189E - Majority Wins?](/contest/2189/problem/E "Codeforces Round 1075 (Div. 2)") 208 209 Idea: [Fakewave](/profile/Fakewave "Master Fakewave"), [furt1ve](/profile/furt1ve "Specialist furt1ve") 210 211 **Solution** 212 213 Let's start by saying the answer is $-1$ if the string consists only of $0$'s. 214 215 Suppose we performed $k$ operations, where the $i$-th operation cost $a_i$. Then 216 217 $(a_1 - 1) + (a_2 - 1) + \dots + (a_k - 1) = n - 1$ (the number of characters that need to be removed), so 218 219 $cost = a_1 + a_2 + \dots + a_k = n - 1 + k$. 220 221 Thus the problem reduces to finding the minimal number of operations $k$ needed to achieve the goal. The answer will be $n - 1 + k$. 222 223 We show that $k \le 4$. 224 Let $s_i = 1$. Replace substrings $[1, i-1]$ and $[i+1, n]$ with some characters. Now we have the string $x 1 y$. Replace the substring $[1, 2]$ with $1$, giving $1 y$. Finally replace it with the string $1$. 225 226 Now we determine when the minimal number of operations is $k = 0, 1, 2, 3$ (otherwise $k = 4$). 227 228 By the **difference** of a string we mean the difference between the number of $1$'s and $0$'s. 229 230 It is claimed that $k$ operations are sufficient if: 231 232 1. **$k = 0$** When $s = 1$. 233 2. **$k = 1$** The string's difference is nonnegative. 234 3. **$k = 2$** Either the string has a prefix or suffix with positive difference (then the remaining part can be replaced with any symbol, after which the whole string can be turned into $1$ in one move), 235 or the string's difference equals $-1$ (if the first condition does not hold, then we can replace substring $[1, n-1]$ with $1$ — its difference is $0$ because $s_n = 0$ — obtaining the string $10$, which can be changed to $1$ in one operation). 236 4. **$k = 3$** Either the string has a prefix or suffix with nonnegative difference (then the remaining part can be replaced by $0$, that part can be turned into $1$, resulting in string $10$ or $01$, after which one operation suffices), 237 or there are two consecutive $1$'s (then replace the prefix before them and the suffix after them with something, obtaining a string with difference $\ge 0$, which can be turned into $1$). 238 5. **$k = 4$** Otherwise. 239 240 --- 241 242 Now we proceed to the proofs for $k \ge 2$: 243 244 #### **$k = 2$** 245 246 Assume the goal cannot be achieved in $k \lt 2$ operations, but can in $k = 2$, under the conditions that the difference is not $-1$ and there is no prefix/suffix with positive difference. 247 248 If the first operation is on a prefix or suffix, then that substring's difference is $\ge 0$. To finish in one more operation, the remaining part must have difference $-1$ (if it had difference $\ge 0$, the whole original string would have nonnegative difference; if $ \lt -1$, the total after the first operation would be $ \lt 0$). In this case the whole original string's difference would also be $-1$. 249 250 If the first operation is on some middle substring, then after it the difference $\le -1 + 1 + (-1) = -1$, so winning becomes impossible. 251 252 #### **$k = 3$** 253 254 Assume the goal cannot be achieved in $k \lt 3$ operations, but can in $k = 3$, under the conditions that no prefix/suffix has nonnegative difference and there are no two consecutive $1$'s. 255 256 Let the initial difference be $z$. Suppose the first operation is on substring $[l, r]$. Let the difference in $[1, l-1]$ be $a \lt 0$, in $[l, r]$ be $b$, and in $[r+1, n]$ be $c \lt 0$. 257 258 **Case $b = 0$** 259 Now the difference becomes $a + 1 + c$. 260 If $a + c + 1 = -1$, then $a + c = -2$ with $a, c \le -1$, so $a = c = -1$. But then if substring $[l, r]$ starts and ends with $0$ (otherwise prefix $[1\ldots l]$ or suffix $[r\ldots n]$ would have nonnegative difference). Then substring $[l+1, r-1]$ has difference $2$, so its length is even (if zeros $= x$, ones $= 2 + x$, total $= 2 + 2x$). Group adjacent pairs $(l+1, l+2), \dots, (r-2, r-1)$. In each pair difference $\le 0$ (since no two consecutive $1$'s), so difference of the whole sub-substring cannot be $2$ — contradiction. 261 262 Otherwise, suppose a positive prefix/suffix emerges after the operation (w.l.o.g., a prefix). 263 Let $T$ be that positive prefix. It contains the $1$ produced from $b$ plus some part $M$ from suffix $[r+1\ldots n]$ with difference $d \gt 0$. Then $T$'s difference is $a + 1 + d \ge 1$, so $a + d \le 0$. We already know $d \le 1$ (otherwise there would be two consecutive $1$'s), so $a \ge -1$, hence $a = -1$. Then $M$ starts with $0$ (otherwise $a + b + 1 = 0$ giving a prefix with nonnegative difference). Thus the used part $M$ must have difference $2$, so it contains two consecutive $1$'s — contradiction. 264 265 **Case $b \lt 0$** If difference becomes $-1$, then $a - 1 + c = -1 \implies a + c = 0$, impossible. 266 Otherwise, suppose a positive prefix emerges (w.l.o.g., a prefix). 267 268 * If $l = 1$, then suffix $[r+1\ldots n]$ remains. We get $0$ + a prefix from $M$, so that prefix must have difference $\ge 2 \implies$ two consecutive $1$'s — contradiction. 269 * Otherwise, the new prefix includes $[1\ldots l-1]$ + $0$ (from $b$) + prefix $M$ from $[r+1\ldots n]$. That prefix would need difference $\ge 3$ (since $[1\ldots l-1]$ has difference $\le -1$ and we add a $0$), so again two consecutive $1$'s — contradiction. 270 271 **Code** 272 273 [359458367](/contest/2189/submission/359458367 "Submission 359458367 by Akulyat") 274 275 **Rate the problem** 276 277 Amazing 278 279 Good 280 281 Ok 282 283 Bad 284 285 Terrible 286 287 [2189F - Zhora the Vacuum Cleaner](/contest/2189/problem/F "Codeforces Round 1075 (Div. 2)") 288 289 Idea: [yanb0](/profile/yanb0 "Master yanb0") 290 291 **Solution** 292 293 We call a vertex dead if it has $0$ nuts, and if we root the tree in it, among the subtrees of its children, there is at most one subtree with a positive sum of the numbers of nuts. 294 295 We denote the movement operation for a vertex $v$ as $\operatorname{c}(v)$. 296 297 Let $A$ be the forest consisting of all living vertices. We prove that $A$ is always connected, i.e., it is a tree. Suppose for a contradiction, $A$ has at least two connected components, then the path between them must contain a dead vertex $v$. However, $v$ is alive, since both connected components are in different subtrees of $v$'s children when the tree's rooted in $v$, a contradiction, q.e.d. 298 299 Let $\deg(v)$ be the degree of $v$ in $A$. It's easy to see that when applying $\operatorname{c}(v)$, $a_v := a_v + \deg(v)$, and for all other vertices $u \in A$, $a_u := a_u + \deg(u) - 2$. If $v \not \in A$, then $a_v := a_v + 1$, $a_u := a_u + \deg(u) - 2$, $a_p := a_p + \deg(p) - 1$, where $p$ is the closest vertex from $A$ to $v$. $[*]$ 300 301 For a sequence of operations, we define the tree $L$ as $A$ at the moment after all $\operatorname{c}(v)$ operations and before the nuts are eaten. 302 303 Suppose we have a sequence of operations (including the eating) that results in no nuts remaining. Let us prove that the last operation $\operatorname{c}(v)$, where $v \not \in L$, can be replaced by $\operatorname{c}(u)$, where $u \in L$. In this case, $A$ becomes a non-strict subset of itself, and again, there are no nuts left. Consider the moment before applying $\operatorname{c}(v)$. There are two options: 304 305 1. $v$ is alive. Then, when replacing $\operatorname{c}(v)$ with $\operatorname{c}(u)$, $a_v$ decreases by $2$, and $a_u$ increases by $2$ according to $[*]$. 306 2. $v$ is dead. Let $p$ be the closest vertex in $A$ to $v$. Then, when replacing $\operatorname{c}(v)$ with $\operatorname{c}(u)$, $a_v$ and $a_u$ will decrease by $1$ (become equal to $0$), and $a_p$ will increase by $1$ according to $[*]$. 307 308 In both cases, all $a_x$ for $x \not \in L$ will decrease, and it is easy to see that the sequence of operations after $\operatorname{c}(v)$ will also bring all nuts into $L$, after which the same eating operations will remove all nuts, q.e.d. Thus, all operations of type $\operatorname{c}(v)$, where $v \not \in L$, can be (sequentially from the end) replaced by $\operatorname{c}(u)$ for some $u \in L$. 309 310 Now we have to solve the following problem: 311 312 We need to choose a subtree $L$ of the original tree, then repeatedly apply $\operatorname{c}(u)$, $u \in L$, to make all vertices not in $L$ dead, and then apply the eat operation to all $v \in L$. Note that by $[*]$, all vertices not in $L$ will become dead regardless of which vertices in $L$ we choose; in other words, we can apply all $\operatorname{c}(v)$ to only one vertex $v$. 313 314 Consider the dynamics along directed edges $xy$, $dp[x][y]$: the smallest number of $\operatorname{c}(v)$ operations, where $v$ is on the $x$ side of $xy$, needed to make all vertices on the $y$ side (including $y$) of $xy$ dead. The value of $a_y$ can only decrease when $\deg(y) = 1$, so $dp[x][y] = \sum_{i=0}^{k}dp[y][ch[i]]$, that is, $dp[x][y]$ is equal to the sum of $a_v$ over all $v$ in the subtree $y$, if we hang the entire tree on $x$. 315 316 For all vertices $v \not \in L$, at some point and always after that, $a_v = 0$. It is also possible that $a_v = 0$ before all operations; $a_v$ is never equal to $0$ again. 317 318 We define $zero[y]$ to be the smallest number of $\operatorname{c}(v)$ operations required for $a_y = 0$ after any number of $\operatorname{c}(v)$ operations at least equal to $zero[y]$. $zero[y] = \min_x({dp[x][y]})$ for all $x$ adjacent to $y$, and $zero[y] = 0$ if $a_y = 0$ and $\deg(y) = 2$ initially. This is true because if $a_y \ne 0$ or $\deg(y) \ne 2$, $y$ will finally "zero out" only when it becomes dead. $\min_x({dp[x][v]})$ is greater than $dp[v][u]$ for all, possibly except one, vertices $u$ adjacent to $v$, and therefore is greater than $\min_t({dp[t][u]})$ for $t$ adjacent to $u$ adjacent to $v$. Therefore, applying $\operatorname{c}(v)$ to $v$ with the largest $zero[v]$, each $a_u$ will become equal to $0$ after $zero[u]$ operations. 319 320 Thus, either there are no $\operatorname{c}(x)$ operations, and the eating operation must be applied to all $y$ with initial $a_y = 0$, or there are $\operatorname{c}(x)$ $k$ operations, and the eating operation must be applied to all vertices $y$ with $zero[y] \ge k$. For the first case, we simply calculate the cost of this sequence of operations. For the second case, we sort $zero$ in $O(n \log n)$, then iterate over the number of "zeroed" vertices, iterating over $zero$, and calculate the answer as $(n - i) \cdot q + zero[i - 1] \cdot p$. The answer to the problem will be the minimum of the obtained ones. 321 322 Total complexity: $O(n \log n)$. 323 324 **Code** 325 326 [359458396](/contest/2189/submission/359458396 "Submission 359458396 by Akulyat") 327 328 **Rate the problem** 329 330 Amazing 331 332 Good 333 334 Ok 335 336 Bad 337 338 Terrible