1854.md (21466B)
1 Source: https://codeforces.com/blog/entry/118540 2 3 The official implementations of all the problems are [here](https://drive.google.com/file/d/1stkidhN_ftTOzK4qcMYxkUAlwWWb3AqF/view?usp=sharing). 4 5 [1855A - Dalton the Teacher](/contest/1855/problem/A "Codeforces Round 889 (Div. 2)") 6 7 Author: [Kaey](/profile/Kaey "Master Kaey") 8 Preparation: [akifpatel](/profile/akifpatel "International Master akifpatel") 9 10 **Hint 1** 11 12 What's the most efficient way to make the sad students happy? 13 14 **Hint 2** 15 16 In most cases, you can make $2$ sad students happy in $1$ move. 17 18 **Solution** 19 20 Let $s$ be the number of sad students at the beginning. The answer is $\lceil \frac{s}{2} \rceil$. 21 22 In one move, you can make at most $2$ sad students happy (because you can change the position of at most two students), so you need at least $\lceil \frac{s}{2} \rceil$ moves. 23 24 In fact, you can make everyone happy in exactly $\lceil \frac{s}{2} \rceil$ moves: 25 26 * while there are at least $2$ sad students, you can swap them and both of them will be happy; 27 * if there is exactly $1$ sad student left, you can swap it with any other student. 28 29 Complexity: $O(n)$ 30 31 [1855B - Longest Divisors Interval](/contest/1855/problem/B "Codeforces Round 889 (Div. 2)") 32 33 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 34 Preparation: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 35 36 **Hint 1** 37 38 What's the answer if $n$ is odd? 39 40 **Hint 2** 41 42 Try to generalize Hint 1. 43 44 **Hint 3** 45 46 What's the answer if $n$ is not a multiple of $3$? 47 48 **Hint 4** 49 50 If the answer is not a multiple of $x$, the answer is $ \lt x$. If the answer is a multiple of $1, \dots, x$, the answer is $\geq x$. 51 52 **Solution** 53 54 Suppose you find a valid interval $[l, r]$. Note that the interval $[l, r]$ contains at least one multiple of $x$ for each $1 \leq x \leq r-l+1$ (you can find it out by looking at the values in $[l, r]$ modulo $x$). Then, the interval $[1, r-l+1]$ is also valid and has the same length. 55 56 So, it's enough to check intervals with $l = 1$, i.e., find the smallest $x$ that does not divide $n$. The answer is $x-1$. 57 58 Complexity: $O(\log(\max n))$ 59 60 [1854A1 - Dual (Easy Version)](/contest/1854/problem/A1 "Codeforces Round 889 (Div. 1)") 61 62 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 63 Preparation: [akifpatel](/profile/akifpatel "International Master akifpatel") 64 65 **Hint 1** 66 67 There are several solutions to the easy version. In any case, how to get $a_i \leq a_{i+1}$? 68 69 **Hint 2** 70 71 For example, you can try making $a_{i+1}$ bigger using a positive element. 72 73 What to do if all the elements are negative? 74 75 **Hint 3** 76 77 If all the elements are negative, you can win in $n-1$ moves. 78 79 If there is a positive element, you can try to make $a_1 \leq a_2$, then $a_2 \leq a_3$, etc. 80 81 **Hint 4** 82 83 Make a big positive element using moves $(i, i)$, then make $a_2$ bigger. 84 85 **Solution** 86 87 If all the elements are negative, you can make suffix sums (they are nondecreasing) with moves $(n-1, n), (n-2, n-1), \dots$ 88 89 If there is at least one positive element $a_x$, 90 91 * make $a_x \gt 20$ using $5$ moves $(x, x)$; 92 * make $a_2$ the biggest element using $2$ moves $(2, x)$; 93 * make $a_3$ the biggest element using $2$ moves $(3, 2)$; 94 * ... 95 96 This strategy requires $5 + 2(n-1) \leq 43$ moves. 97 98 Complexity: $O(n)$ 99 100 [1854A2 - Dual (Hard Version)](/contest/1854/problem/A2 "Codeforces Round 889 (Div. 1)") 101 102 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 103 Preparation: [akifpatel](/profile/akifpatel "International Master akifpatel"), [dario2994](/profile/dario2994 "International Grandmaster dario2994") 104 105 The hints and the solution continue from the easy version. 106 107 **Hint 5** 108 109 You can win in $n-1$ moves if all the elements are negative, but also if all the elements are positive. 110 111 **Hint 6** 112 113 Again, make a big positive / negative element, then use it to make everything positive / negative. 114 115 **Hint 7** 116 117 In how many moves can you either make everything positive or make everything negative? 118 119 **Hint 8** 120 121 Assume the positive elements are at least as many as the negative elements. Can you win in $34$ moves? 122 123 **Hint 9** 124 125 The bottleneck is making the big positive element. Is it always necessary? Can you find a better bound on the "best" number of moves? 126 127 **Solution** 128 129 If you either make everything positive or make everything negative, you can win in $n-1 \leq 19$ moves by making prefix sums or suffix sums, respectively. So, you have to reach one of these configurations in $12$ moves. 130 131 How to make everything positive? First, you create a big element with the maximum absolute value (this requires $x_1$ moves), then you add it to every negative element (this requires $x_2$ moves). $y_1$ and $y_2$ are defined similarly in the negative case. 132 133 So, 134 135 * one of $x_1$ and $y_1$ is $0$ (because the element with the maximum absolute value at the beginning is either positive or negative), and the other one is $\leq 5$ (because you can make $|a_i| \geq 32$ in $5$ moves); 136 * $x_2$ is the number of negative elements, $y_2$ is the number of positive elements. So, $x_2 + y_2 \leq n \leq 20$. 137 138 Therefore, you need additional $\min(x_1 + x_2, y_1 + y_2)$ moves. Since $x_1 + x_2 + y_1 + y_2 \leq 25$, $\min(x_1 + x_2, y_1 + y_2) \leq \lfloor \frac{25}{2} \rfloor = 12$, as we wanted. Now you can simulate the process in both cases (positive and negative), and choose one that requires $\leq 31$ moves in total. 139 140 Complexity: $O(n)$ 141 142 [1854B - Earn or Unlock](/contest/1854/problem/B "Codeforces Round 889 (Div. 1)") 143 144 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 145 Preparation: [akifpatel](/profile/akifpatel "International Master akifpatel") 146 147 **Hint 1** 148 149 The order of used cards doesn't matter. So, you can assume you always use the card on the top. 150 151 **Hint 2** 152 153 Suppose that you unlock $x$ cards in total. How many points can you get? 154 155 **Hint 3** 156 157 If you unlock $x$ cards, it means you end up making moves with the first $x$ cards. So, you know the total number of (cards + points) that you get. 158 159 **Hint 4** 160 161 If you unlock $x$ cards, the number of points is uniquely determined. It's convenient to assume that $x \leq 2n$ and the cards $n+1, \dots, 2n$ have value $0$. 162 163 **Hint 5** 164 165 Now you have to determine the unlockable prefixes of cards (i.e., the values of $x$ you can reach). It looks similar to knapsack. 166 167 **Hint 6** 168 169 You can optimize the solution using a bitset. Be careful not to use locked cards. 170 171 **Solution** 172 173 First, note that the order of used cards doesn't matter. If you use at least once a card that is not on the top on the deck, you can prove that using the cards in order (from the top) would give the same number of victory points. 174 175 Let's add $n$ cards with value $0$ at the end of the deck. Then, it's optimal to unlock $x \leq 2n$ cards, and use cards $1, \dots, x$, getting $a_1 + \dots + a_x - x + 1$ points. 176 177 Let's find the reachable $x$. Let $dp_i$ be a bitset that stores the reachable $x$ after using the first $i$ cards. 178 179 * Base case: $dp_{0,1} = 1$. 180 * Transitions: first, $dp_{i}$ `|=` $dp_{i-1}$ `<<` $a_i$. If $dp_{i,i} = 1$, you can update the answer with $a_1 + \dots + a_i - i + 1$, but you can't unlock any other card, so you have to set $dp_{i,i} = 0$ before transitioning to $i+1$. 181 182 Complexity: $O(n^2/w)$ 183 184 [1854C - Expected Destruction](/contest/1854/problem/C "Codeforces Round 889 (Div. 1)") 185 186 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 187 Preparation: [akifpatel](/profile/akifpatel "International Master akifpatel") 188 189 **Hint 1** 190 191 Consider $n$ blocks in positions $S_1, S_2, \dots, S_n$. After how much time does block $x$ disappear? It may be convenient to put a fake "static" block in position $m+1$. 192 193 **Hint 2** 194 195 Block $x$ disappears when it reaches block $x+1$. But what if block $x+1$ disappears before block $x$? 196 197 **Hint 3** 198 199 From the perspective of block $x$, it's convenient to assume that block $x+1$ never disappears: when it touches another block $y$, it's $y$ that disappears. 200 201 **Hint 4** 202 203 When you consider the pair of blocks $x, x+1$, the other blocks don't really matter, and you can use linearity of expectation to calculate the contribution of each pair independently. 204 205 A reasonable interpretation is given by considering an $(n+1) \times (m+1)$ grid, where the $i$-th row initially contains a block in column $S_i$. Then, you are calculating the expected time required for the blocks $1, \dots, m$ to have another block immediately below them (in the same column). 206 207 **Hint 5** 208 209 Blocks $x, x+1$ both move with probability $1/2$, unless block $x+1$ has reached position $m+1$. 210 211 **Hint 6** 212 213 $dp_{i,j} =$ expected number of moves of block $x$ before it disappears, if the block $x$ is in position $i$ and the block $x+1$ is in position $j$. 214 215 **Solution** 216 217 Consider an $(n+1) \times (m+1)$ grid, where the $i$-th row initially contains a block in column $S_i$, and row $n+1$ contains a block in column $m+1$. 218 219 * The set is empty if all the blocks are in column $m+1$; i.e., if every block has reached the block in the following row. 220 * Every "connected component" of blocks (except the last one) represents an element in the set. These components move equiprobably. 221 222 Let's calculate the expected time required for the block in row $x$ to "reach" the block in row $x+1$. If you consider a single pair of blocks, every block moves with probability $1/2$, unless block $x+1$ is in column $m+1$. 223 224 So, you can calculate $dp_{i,j} =$ expected number of moves of the block $x$ before it reaches the block $x+1$, if the block $x$ is in position $i$ and the block $x+1$ is in position $j$. 225 226 The base cases are $dp_{i,m+1} = (m+1)-i$ (because only the block $x$ can move) and $dp_{i,i} = 0$ (because block $x$ has already reached block $x+1$). In the other cases, $dp_{i,j} = ((dp_{i+1,j} + 1) + dp_{i,j+1})/2$. 227 228 By linearity of expectation, the answer is the sum of $dp_{S_i, S_{i+1}}$. 229 230 Complexity: $O(m^2)$ 231 232 [1854D - Michael and Hotel](/contest/1854/problem/D "Codeforces Round 889 (Div. 1)") 233 234 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 235 Preparation: [akifpatel](/profile/akifpatel "International Master akifpatel") 236 237 **Hint 1** 238 239 You can find any $a_i$ in $9$ queries. 240 241 **Hint 2** 242 243 Find the nodes in the cycle in the component with node $1$. What happens if you know the whole cycle? 244 245 **Hint 3** 246 247 Suppose you already know some nodes in the cycle. Can you find other nodes faster? 248 249 **Hint 4** 250 251 Can you "double" the number of nodes in the cycle? 252 253 **Solution** 254 255 The component with node $1$ contains a cycle. If you know the whole cycle (of length $x$), you can win in $n-x$ queries by asking for each node if it ends up in the cycle after $n$ moves. 256 257 You can get a node in the cycle in $9$ queries, doing a binary search on the $n$-th successor of node $1$. 258 259 How to find the rest of the cycle? 260 261 * First, find $k$ nodes in the cycle, doing a binary search on the successor of the last node found. These nodes make a set $C$. 262 * Then, check for each node if it's "sufficiently close" to $C$, by asking $(i, k, C)$. Now, you know either $2k$ nodes in the cycle, or the whole cycle. 263 * Repeat until you get the whole cycle. 264 265 If you choose $k = 63$, you spend at most $9 \cdot 63 + (500 - 63) + (500 - 126) + (500 - 252) + (500 - 252) = 1874$ queries. 266 267 [1854E - Game Bundles](/contest/1854/problem/E "Codeforces Round 889 (Div. 1)") 268 269 Author: [dario2994](/profile/dario2994 "International Grandmaster dario2994") 270 Preparation: [akifpatel](/profile/akifpatel "International Master akifpatel"), [dario2994](/profile/dario2994 "International Grandmaster dario2994") 271 272 **Hint 1** 273 274 Go for a randomized approach. 275 276 **Hint 2** 277 278 Many ones are useful. 279 280 **Hint 3** 281 282 Either you go for a greedy or for a backpack. 283 284 **Solution** 285 286 We describe a randomized solution that solves the problem for $m$ up to $10^{11}$ (and, with some additional care, may be able to solve also $m$ up to $10^{12}$). We decided to give the problem with the smaller constraint $m\le 10^{10}$ to make the problem more accessible and because there may be some rare cases below $10^{11}$ for which our solution is too slow (even though we could not find any). We don't know any provably correct solution, if you have one we would be curious to see it. We expect to see many different solutions for this problem. 287 288 **Main idea:** Choose suitably the values $a_1, a_2, \dots, a_h$ that belong to $[1,29]$ and then find $a_{h+1}, a_{h+2},\dots,a_k$ in $[31,60]$ by solving a backpack-like problem. 289 290 Let us describe more precisely the main idea. Assume that $a_1, a_2, \dots, a_h\le 30$ are fixed and they satisfy $a_1+a_2+\cdots+a_h \lt 60$. For any $s=0,1,2,\dots,29$, let $f(s)$ be the number of subsets $I\subseteq{1,2,\dots,h}$ so that $\sum_{i\in I}a_i=s$. If we can find some values $0\le s_1,s_2,\dots,s_{k-h}\le 29$ so that $f(s_1)+f(s_2)+\cdots+f(s_{k-h})=s$, then by setting $a_{h+i} = 60-s_i$ for $i=1,2,\dots, k-h$ we have found a valid solution to the problem. 291 292 There are two main difficulties: 293 294 * How can we find $s_1, s_2,\dots, s_{k-h}$? 295 * How should we choose $a_1, a_2,\dots, a_h$? 296 297 Since it is important to get a good intuitive understanding of the computational complexity of the algorithm, let us say now that we will choose $h\le 44$ and (accordingly) $k-h=16$. These values are flexible (the solution would still work with $h\le 45$ and $k-h=45$ for example). We will say something more about the choice of these values when we will describe how $a_1,a_2,\dots, a_h$ shall be chosen. 298 299 **The backpack problem to find $s_1, s_2,\dots, s_{k-h}$.** 300 301 The naive way to find $s_1,\dots, s_{k-h}$ would be to try all of them. There are $\binom{k-h + 29}{29}$ possible ways (up to order, which does not matter). Since $k-h=16$ this number is $\approx 2\cdot 10^{11}$ which is too much to fit in the time limit. 302 303 To speed up the process, we will do as follows. Partition randomly $A\cup B={0,1,\dots, 29}$ into two sets of size $15$. We iterate over all possible $s_1, s_2, \dots, s_{(k-h)/2}\in A$ and over all possible $s_{(k-h)/2+1},\dots, s_{k-h}\in B$ and check whether the sum of one choice from the first group and one choice from the second group yields the result. This is a standard optimization for the subset sum problem. What is its complexity? It can be implemented in linear time in the size of the two groups we have to iterate over, which have size $\binom{(k-h)/2+15}{15}\approx 5\cdot 10^5$. Notice that in this faster way we will not visit all the $\binom{k-h+29}{29}$ possible choices $s_1,s_2,\dots, s_{k-h}$ because we are assuming that exactly half of them belong to $A$ and exactly half of them belong to $B$. This is not a big deal because with sufficiently high probability we will find a solution in any case. 304 305 **The choice of $a_1, a_2,\dots, a_{h}$.** 306 307 It remains to decide how we should select $a_1, a_2, \dots, a_{h}$. The following choice works: 308 309 * Approximately the first $\log_2(m)$ values are set equal to $1$. 310 * Five additional values are chosen randomly from $[1, 6]$ so that the total sum stays below $60$. 311 312 One should repeat the whole process until a solution is found. 313 314 **Some intuition on the construction.** The choice of $a_1, \dots, a_{h}$ may seem arbitrary; let us try to justify it. The goal is to generate a set of values $f(0), f(1),\dots, f(29)$ that are simultaneously ``random enough'' and with size smaller but comparable to $m$. These two conditions are necessary to expect that the backpacking problem finds a solution with high enough probability. 315 316 If $a_1=a_2=\cdots=a_{h}=1$, then $f(s) = \binom{k-h}{s}$ and these numbers have size comparable to $m$ if $2^{h}$ is comparable to $m$. This observation explains why we start with approximately $\log_2(m)$ ones. The issue is that we need some flexibility in the process as we may need to repeat it many times, this flexibility is provided by the addition of some additional random elements which don't change the magnitude of the values $f(0), f(1), \dots, f(29)$ but that modify them as much as possible (if we added a large number it would not affect many $f(s)$ and thus it would not be very useful). 317 318 [1854F - Mark and Spaceship](/contest/1854/problem/F "Codeforces Round 889 (Div. 1)") 319 320 Author: [dario2994](/profile/dario2994 "International Grandmaster dario2994") 321 Preparation: [akifpatel](/profile/akifpatel "International Master akifpatel"), [dario2994](/profile/dario2994 "International Grandmaster dario2994") 322 323 **Hint 1** 324 325 Solve the 2d version first. 326 327 **Hint 2** 328 329 The 4d version is not too different from the 2d one. 330 331 **Hint 3** 332 333 Find all the points such that the expected number of necessary moves is wrong. 334 335 **Solution** 336 337 ### **The $2$-dimensional case.** 338 339 Let us begin by cpnsidering the $2$-dimensional version of the problem. The solution to this simpler version provides the idea of the approach for the $4$-dimensional version. 340 341 We want to reach $(a, b)$. Can we do it with exactly $k$ moves? Two simple necessary conditions are: 342 343 * $|a|+|b|\le 1 + 2 + \cdots + k$, 344 * $a+b$ and $1 + 2 + \cdots + k$ shall have the same parity. 345 346 It turns out that this two conditions are also sufficient! One can prove it by induction on $k$ as follows. If $k=0$ or $k=1$ or $k=2$ the statement is simple, thus we may assume $k\ge 3$. 347 348 Without loss of generality we may assume $0\le a\le b$. If $|a|+|b-k| \le 1 + 2 + \cdots + k-1$, then the statement follows by inductive hypothesis. Assume by contradiction that such inequality is false. If $b\ge k$ then we have a contradiction because $|a|+|b-k| = |a|+|b|-k \le (1 + 2 + \cdots + k) - k$. Otherwise $b \lt k$ and the contradiction is $|a|+|b-k| = a + k-b \le k \le 1 + 2 + \cdots + k-1$. 349 350 Hence, we have shown: 351 352 **Lemma 1:** The point $(a, b)$ is reachable with exactly $k$ moves if and only if $|a|+|b| \le 1 + 2 + \cdots + k$ and $a+b$ has the same parity of $1+2+\cdots + k$. 353 354 ### **The $4$-dimensional case.** 355 356 One may expect statement analogous to the one of Lemma 1 to hold also when there are $4$ coordinates. It does not, but it *almost* does and this is the crucial idea of the solution. More precisely, the number of counter examples to such statement is rather small and we can find all of them. This is the intuition behind the following definition. 357 358 **Definition:** For $k\ge 0$, let $A_k$ be the set of points $(a, b, c, d)$ such that $|a|+|b|+|c|+|d|\le 1 + 2 + \cdots + k$ and $a+b+c+d$ has the same parity of $1 + 2 + \cdots + k$ but $(a, b, c, d)$ is not reachable with exactly $k$ moves. 359 360 As an immediate consequence of the definition, we have 361 362 **Observation:** The point $(a, b, c, d)$ is reachable with exactly $k$ moves if and only if $|a|+|b|+|c|+|d| \le 1 + 2 + \dots + k$ and $a+b+c+d$ has the same parity of $1+2+\cdots + k$ and $(a, b, c, d)\not\in A_k$. 363 364 Thanks to this observation, if one is able to efficiently find $A_k$ for all interesting values of $k$, then solving the problem is (comparatively) easy. The following lemma is our main tool for this purpose. 365 366 **Lemma 2:** Assume that $(a, b, c, d) \in A_k$ with $0\le a\le b\le c\le d$. Then, either $k\le 6$ or $(a, b, c, d - k) \in A_{k-1}$. 367 368 **Proof:** The strategy is the same adopted to show Lemma 1. In some sense, we are saying that the inductive step works also in dimension $4$, but the base cases don't. 369 370 If $|a|+|b|+|c|+|d-k|\le 1 + 2 + \cdots + k-1$, then it must be $(a, b, c, d-k)\in A_{k-1}$ because if $(a, b, c, d-k$ were reachable with $k-1$ moves then $(a, b, c, d)$ were reachable with $k$ and we know that this is not true. 371 372 Assume by contradiction that $|a|+|b|+|c|+|d-k| \gt 1 + 2 + \cdots + k-1$. If $d\ge k$ then we reach the contradiction $|a|+|b|+|c|+|d-k| = a+b+c+d-k \le (1 + 2 + \dots + k) - k$. Otherwise, $d \lt k$ and thus we reach the contradiction $|a|+|b|+|c|+|d-k| = a+b+c+k-d\le a+b+k\le 3k-2\le 1 + 2 + \dots + k-1$ (for $k\ge 7$). 373 374 We can now describe the solution. Assume that we know $A_{k-1}$. First of all, notice that it is then possible to determine in $O(1)$ whether a point belongs to $A_k$ or not. To generate a list of candidate elements for $A_k$ we proceed as follows: 375 376 * If $k\le 6$, we simply iterate over all points with $|a|+|b|+|c|+|d|\le 1 + 2 + \cdots + k$. 377 * Otherwise, we iterate over the points in $A_{k-1}$ and we consider as candidate elements for $A_k$ the points that can be obtained by changing the value of one coordinate by $k$. 378 379 Thanks to Lemma 2, we know that this process finds all the elements in $A_k$. Once $A_0, A_1, A_2, A_3,\dots$ are known, the problem boils down to a (relatively) simple counting argument that we skip. 380 381 One can verify that to handle correctly all points with coordinates up to $1000$ it is necessary to compute $A_k$ for $0\le k \le 62$. 382 383 One additional cheap trick is required to make $A_k$ sufficiently small and get a sufficiently fast solution. Given $(a, b, c, d)$, the instance of the problem is equivalent if we change the signs of the coordinates or we change the order of the coordinates. Hence we shall always ``normalize'' the point so that $0\le a \le b\le c\le d$. If we do this consistently everywhere in the process, the solution becomes an order of magnitude faster. In particular, this trick guarantees $|A_k|\le 5000$ for all $0\le k\le 62$. 384 385 **Bonus question:** Find an explicit closed form for the elements in $A_k$ for any $k$. (in this way one can solve the problem also with larger constraints on $A, B, C, D$; but it is tedious)