2157.md (21177B)
1 Source: https://codeforces.com/blog/entry/148631 2 3 [2157A - Dungeon Equilibrium](/contest/2157/problem/A) 4 5 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 6 Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 7 8 **Hint 1** 9 10 Each value $x$ is independent of the others; only its own frequency matters. 11 12 **Hint 2** 13 14 In a balanced array, value $x$ must appear either $0$ times or **exactly** $x$ times. 15 16 **Solution** 17 18 * Each value $x$ is independent of the others; only its own frequency matters. In particular, for each value, find its frequency $f[x]$. 19 * In a balanced array, value $x$ must appear either $0$ times or **exactly** $x$ times. Specifically, if it appears $ \lt x$ times at the beginning, you have to delete all its occurrences, otherwise you should keep $x$ occurrences. Specifically, for each $x$, add $f[x]$ to the answer if $f[x] \lt x$, else add $f[x] - x$. 20 21 Complexity: $O(n)$ time. Slower solutions (e.g., $O(n^2)$) are allowed. 22 23 **Code** 24 25 [350380351](/contest/2157/submission/350380351 "Submission 350380351 by Dominater069") 26 27 [2157B - Expansion Plan 2](/contest/2157/problem/B) 28 29 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 30 Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 31 32 **Hint 1** 33 34 The order of operations does not matter. Only the number of $\texttt{4}s$ and $\texttt{8}s$ in the substring matters. 35 36 **Hint 2** 37 38 The black cells are the positions we can reach starting from $(0, 0)$, if we can move orthogonally (using a $\texttt{4}$) and diagonally (using an $\texttt{8}$). 39 40 **Hint 3** 41 42 A move with an $\texttt{8}$ is equivalent to two moves with a $\texttt{4}$, in different directions. 43 44 **Solution** 45 46 * The order of operations does not matter. So count the number of $\texttt{4}s$ and $\texttt{8}s$, and assume there are $a$ $\texttt{4}$s and $b$ $\texttt{8}s$. 47 * The grid is symmetrical. We can assume $x, y \geq 0$ (by making $x := |x|$, $y := |y|$). 48 * The black cells are the positions we can reach starting from $(0, 0)$, if we can move orthogonally (using a $\texttt{4}$) and diagonally (using an $\texttt{8}$). 49 * In particular, since $x, y \geq 0$, a $\texttt{4}$ is a step either up or right while an $\texttt{8}$ consists of two steps, one up and one right. 50 * So you make $a+2b$ steps in total, and only $a+b$ of them can be in the same direction. 51 * The necessary and sufficient conditions are 52 * + $a+2b \geq x+y$ (you need to be able to perform $x+y$ steps, either up or right, to reach $(x, y)$); 53 * + $a+b \geq \max(x, y)$ (you need to be able to perform $y$ steps up and $x$ steps right). 54 55 **Code** 56 57 [350380442](/contest/2157/submission/350380442 "Submission 350380442 by Dominater069") 58 59 [2157C - Meximum Array 2](/contest/2157/problem/C) 60 61 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 62 Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 63 64 **Hint 1** 65 66 For each element, determine whether it belongs to a $\texttt{MEX}$ constraint, a $\min$ constraint, both, or none. 67 68 **Hint 2** 69 70 If an element belongs to both a $\texttt{MEX}$ constraint and a $\min$ constraint, it is useless for both constraints. 71 72 **Hint 3** 73 74 If an element only belongs to a $\min$ constraint, you can set it to $k$ for convenience. 75 76 **Hint 4** 77 78 What's the "fastest" way to satisfy a $\texttt{MEX}$ constraint? What about several constraints simultaneously? 79 80 **Solution** 81 82 For each element, determine whether it belongs to a $\texttt{MEX}$ constraint, a $\min$ constraint, both, or none. 83 84 * If an element is covered by a $\min$ constraint, it must be $\geq k$, and ideally it should be $= k$ (so that the constraint is immediately satisfied). 85 * If an element is covered by a $\texttt{MEX}$ constraint, it must be $\neq k$, and ideally it should be $ \lt k$ (to make the constraint easier to satisfy). 86 87 Then 88 89 * If an element is not covered by any constraints, it does not matter, and you can set it to any value. 90 * If an element belongs to both a $\texttt{MEX}$ constraint and a $\min$ constraint, it is useless for both constraints, but you must set it to something both $\neq k$ and $\geq k$. For example, you can set it to $k+1$. 91 * If an element only belongs to a $\min$ constraint, it is optimal to set it to $k$. 92 * The remaining elements are the ones which are only covered by a $\texttt{MEX}$ constraint. In order to be satisfied, a $\texttt{MEX}$ constraint must contain at least $k$ such elements (because it must contain all the elements between $0$ and $k-1$, which would violate a $\min$ constraint). In particular, assigning $i \text{ mod } k$ at the $i$-th such element works (if a $\texttt{MEX}$ constraint contains $k$ such elements, their values are $[0, 1, \ldots, k-1]$, possibly shifted). 93 94 Complexity: $O(nq)$ or $O(n+q)$ per test case. 95 96 Bonus: in the above solution, we assign $i \text{ mod } k$ to the $i$-th element only covered by $\texttt{MEX}$ constraints. However, assigning $a_i = i \text{ mod } k$ to such elements (where $i$ is the position in the whole array, instead of the position only considering such elements) also works. Can you prove it? 97 98 **Code** 99 100 [350380521](/contest/2157/submission/350380521 "Submission 350380521 by Dominater069") 101 102 [2157D - Billion Players Game](/contest/2157/problem/D) 103 104 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 105 Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 106 107 **Hint 1** 108 109 The worst case is either $x = l$ or $x = r$. So you can assume that $x$ is either $l$ or $r$, but you don't know which one. 110 111 **Hint 2** 112 113 There exists an optimal strategy where a prefix of offers (after sorting) is accepted using the third option, and a suffix of elements is accepted using the second option. 114 115 **Hint 3** 116 117 There exists an optimal strategy where (in addition to the previous properties) at most one offer is rejected. 118 119 **Solution** 120 121 The worst case is either $x = l$ or $x = r$. 122 **Sketch of proof.** After fixing the strategy, the number of coins as a function of $x$ is a straight line. 123 Then, in order to test a strategy, it is enough to evaluate it at $x = l$ and $x = r$ and pick the minimum. 124 125 There exists an optimal strategy where a prefix of elements (after sorting) is red, and a suffix of elements is blue. 126 **Sketch of proof.** Use exchange argument. For example, if $y \leq z$, $y$ is white and $z$ is red, then we get $x-z$ coins. If we make $y$ red and $z$ white, we make $x-y$ coins instead. 127 128 There exists an optimal strategy where (in addition to the previous properties) at most one element is white. 129 **Sketch of proof.** If $x \leq y$, and they are both white, we can make $x$ red and $y$ blue instead. 130 131 * Try all possibilities for the white element. So there are $O(n)$ candidate strategies. 132 * We can test a strategy in $O(1)$: find the number of coins as a function of $x$ using prefix sums, and evaluate it in $l$ and $r$ to check the actual worst case. 133 134 Complexity: $O(n \log n)$ 135 136 **Code** 137 138 [350380713](/contest/2157/submission/350380713 "Submission 350380713 by Dominater069") 139 140 [2157E - Adjusting Drones](/contest/2157/problem/E) 141 142 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 143 Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 144 145 **Hint 1** 146 147 The order of the elements does not matter. 148 149 **Hint 2** 150 151 Solve the problem with $k = 1$. 152 153 **Hint 3** 154 155 Iterate over elements from right to left and find their final value if $k = 1$. 156 157 **Hint 4** 158 159 Find the value of each element over time. Can you calculate the value of some element after a fixed number $m$ of operations? 160 161 **Hint 5** 162 163 Binary search the answer. 164 165 **Solution** 166 167 The order of the elements does not matter. So let's sort the elements in increasing order. Also, we have the freedom to choose the tiebreaker rule (i.e., which elements are increased by $1$). 168 169 * Assume the process stops when all the elements are distinct (i.e., $k = 1$). Let's find the configuration $b_1, b_2, \ldots, b_n$ at that point. If some elements are equal, the **rightmost** does not increase. 170 * From right to left, if the initial value is $a_i$, then $b_i$ is the smallest $x \geq a_i$ not present in $b$ yet. 171 * If we look at a single element over time, it has values $a_i, a_i + 1, \ldots, b_i, b_i, \ldots, b_i$. 172 173  174 175 * The maximum number of occurences of one element does not increase after one operation (if value $x$ appeared $\leq k$ times, it produces $\leq k-1$ copies of $x+1$, and at most one other copy of $x+1$ survives). 176 * So we can binary search the answer. Using the process described earlier, we can retrieve the configuration after $m$ moves in $O(n)$. 177 178 Complexity: $O(n \log n)$ time (there also exist "magical" $O(n)$ solutions!) 179 180 **Code** 181 182 [350380783](/contest/2157/submission/350380783 "Submission 350380783 by Dominater069") 183 184 [2157F - Git Gud](/contest/2157/problem/F) 185 186 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 187 Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 188 189 **Hint 1** 190 191 How would you write the checker for this problem? (How to check efficiently whether a submission gets AC or WA)? 192 193 **Hint 2** 194 195 After you choose $y$, calculating the optimal $l$ is easy. From now, let's denote the operations only using $y$. 196 197 **Hint 3** 198 199 Consider some naive strategies: for example, $[1, 2, \ldots, n-1]$, or $[n-1, n-2, \ldots, 1]$. Why are they bad? How to improve them? 200 201 **Hint 4** 202 203 You can fix your skill modulo $2$, then modulo $4$, then modulo $8$, etc., but that's still a bit too inefficient. 204 205 **Hint 5** 206 207 Try with a different modulo. 208 209 **Solution** 210 211 As a warm-up, think about how we would write the checker for this problem. 212 213 We can store the set of all the possible skills (initially, all integers in $[1, n]$), and perform operations in $O(1)$ (we have to remove $y$ and insert $y+l$). 214 215 As a consequence, the optimal value of $l$ is the smallest one such that $y+l$ is already in the set. Since we know how to determine the optimal $l$ for a fixed $y$, let's denote the operations only using $y$. 216 217 * Naive strategy 1: use operations $1, 2, \ldots, n-1$. Unfortunately, they are too "increasing". 218 * Naive strategy 2: use operations $n-1, n-2, \ldots, 1$. Unfortunately, they are too long. 219 220 Better strategy: 221 222 * Fix our skill modulo $2$ using operations $n-1, n-3, n-5, \ldots$ 223 * Fix our skill modulo $4$ using operations $n-2, n-6, n-10, \ldots$ 224 * $\ldots$ 225 226 The cost is $O(n \log n)$ ($\approx \log_2 n$ layers, $O(n)$ per layer). We use very few "increasing" operations ($1$ per layer): we can try to use more (and maybe use less layers). 227 228 Generalization: 229 230 * Fix our skill modulo $3$ using operations $n-2, n-5, n-8, \ldots, n-1, n-4, n-7, \ldots$ 231 * Fix our skill modulo $9$ using operations $n-6, n-18, n-30, \ldots, n-3, n-12, n-21, \ldots$ 232 * $\ldots$ 233 234 Now we have $\approx \log_3 n$ layers and $2$ "increasing" operations per layer. 235 236  237 238  239 240  241 242 If we use modulo $m$, we have $\approx \log_m n$ layers, each with cost $\approx n$, and $m-1$ "increasing" operations per layer, each with cost $1000$. 243 244 We should choose $m \approx \sqrt[3]{n}$. So the total cost is around 245 246 $(\log_m n)(n + 1000 m) = 3(n + 1000 \sqrt[3]{n}) \lt 4n$ 247 248 if $n = 250\,000$. 249 250 **Code** 251 252 [350380837](/contest/2157/submission/350380837 "Submission 350380837 by Dominater069") 253 254 [2157G - Isaac's Queries](/contest/2157/problem/G) 255 256 Author: [KLPP](/profile/KLPP "International Grandmaster KLPP") 257 Preparation: [KLPP](/profile/KLPP "International Grandmaster KLPP") 258 259 **Hint 1** 260 261 Apply prefix XOR. So, instead of information about $a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$, assume you can ask information about $a_l \oplus a_r$. 262 263 **Hint 2** 264 265 Find whether the highest bit of every $a_i$ (viewed as $30$-bit integer) is $0$ or $1$. You can assume that $a_1$ has highest bit $0$. 266 267 **Hint 3** 268 269 You get two blocks. Recurse. 270 271 **Hint 4** 272 273 Solve every block in the most efficient way possible. 274 275 **Solution** 276 277 Apply prefix XOR. So, instead of information about $a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$, we assume we can ask information about $a_l \oplus a_r$. 278 279 Let's build a trie containing the $a_i$. Specifically, each node corresponds to a prefix of the binary representation, and contains positions $i$ such that $a_i$ has that prefix. It is not possible to recover the $a_i$ uniquely, but we can set bits to $0$ without loss of generality if they do not impact any queries. Then, in order to calculate the answer for some $(l, r)$, we have to find the LCA of the corresponding nodes. 280 281 Suppose we are in some node of the trie containing $k$ values. We want to recurse into two children, depending on the next bit. This is possible by asking the query. 282 283 Specifically, suppose that a node contains positions $p_1, p_2, \ldots, p_k$. In order to recurse, we need to ask queries between some pairs. We choose this pairs greedily, by calculating a minimum spanning tree (the edges have cost $\frac{1}{p_j-p_i+1}$). It can be also shown that, in the minimum spanning tree, the picked edges contain either $p_1$ or $p_k$, which makes the implementation easier. 284 285 Empirically, this solution requires around $8$ robocoins per test case with $n = 100$. 286 287 Bonus: prove the asymptotic behavior of the solution (idea: for each $(i, j)$, estimate the probability that the query is performed). 288 289 **Code** 290 291 [350380944](/contest/2157/submission/350380944 "Submission 350380944 by Dominater069") 292 293 [2157H - Keygen 3](/contest/2157/problem/H) 294 295 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 296 Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse"), [Dominater069](/profile/Dominater069 "Legendary Grandmaster Dominater069") 297 298 **Hint 1** 299 300 Start with some "easy" pairs $(n, m)$. Which ones can you solve? 301 302 **Hint 2** 303 304 If you have a solution to $(n, m)$, can you transform it into a solution to $(n+1, m+1)$? 305 306 **Hint 3** 307 308 If you have a solution to $(n, m)$, can you transform it into a solution to $(n+1, m)$? 309 310 **Hint 4** 311 312 Find small $(n, m)$ with at least $2000$ solutions, and propagate these solutions to some bigger pairs. 313 314 **Hint 5** 315 316 Now some pairs are missing. They either have small $n$, or small $n-m$. 317 318 **Hint 6** 319 320 If $n-m$ is small, what can you say about the amount of $p_i = i$? 321 322 **Hint 7** 323 324 If $n-m$ is small, then $p_n$ must be large. 325 326 **Solution** 327 328 For convenience, let's find "anti-bitonic" permutations instead (decreasing, then increasing). There is a bijection between bitonic and anti-bitonic permutations. 329 330 ``` 331 vector<int> f(vector<int> p) { 332 int n = p.size(); 333 reverse(p.begin(), p.end()); 334 for (auto &u : p) u = n - u + 1; 335 return p; 336 } 337 ``` 338 339 We can transform a solution to $(n, m)$ into a solution to $(n+1, m+1)$: just append $n+1$ at the end. 340 341 We can also transform a solution to $(n, m)$ into a solution to $(n+1, m)$: append $n+1$ at the end, and swap $p_1$ with $p_1 + 1$. 342 343 Let's divide into three cases: 344 345 1. $n \le 18$; 346 2. $n \ge 19$, $n - m \ge 10$; 347 3. $n \ge 19$, $n - m \le 9$. 348 349 They can be solved as follows. 350 351 1. We can find all the anti-bitonic permutations and test them in $O(n \cdot 2^n)$. 352 2. First, solve $(18, i)$ for $1 \leq i \leq 8$ (for each $i$, we have $\geq 2000$ solutions). Transform these solutions into solutions to $(n, m)$. 353 3. $p_1, p_2, \ldots, p_n$ must have at least $n-9$ cycles, so it must have at least $n-18$ fixed points (i.e., $p_i = i$). The permutation structure is $[p_1, \ldots, p_1+1, p_1+2, \ldots, n]$: the highlighted square has at most $1$ fixed point, so there are at most $n-p_1+1$ fixed points. Therefore, $p_1 \leq 19$, and we can iterate over all such permutations. 354 355  356 357 **Code** 358 359 [350381048](/contest/2157/submission/350381048 "Submission 350381048 by Dominater069") 360 361 [2157I - Hyper Smawk Bros](/contest/2157/problem/I) 362 363 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 364 Full solution: [dario2994](/profile/dario2994 "International Grandmaster dario2994") 365 Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse"), [Dominater069](/profile/Dominater069 "Legendary Grandmaster Dominater069") 366 367 **Hint 1** 368 369 Solve the problem with even $m$. 370 371 **Hint 2** 372 373 Solve the problem with $t = 1$. 374 375 **Hint 3** 376 377 For a fixed $n$, how do "losing" $m$ look like? 378 379 **Hint 4** 380 381 Let $(n, l)$ ($0 \leq m$) be losing if you lose if it's your turn, the current integer is $n$, and you cannot subtract $l$. 382 If $(n, l)$ is losing, then $(n+l, l')$ with $l' \neq l$ is winning. This means that the number of losing $l$ for a fixed $n$ is either $0$, $1$, or $m+1$. Let's call $n$ "good", "neutral", and "evil", respectively. 383 384 **Hint 5** 385 386 How do the losing states $(n, l)$ look like? 387 388 **Hint 6** 389 390 Our goal is to solve $t = 1$ in $O(n/m)$. 391 392 **Hint 7** 393 394 How to determine efficiently whether some $n$ is good or neutral? 395 396 **Hint 8** 397 398 In order to determine whether some $n$ is good or neutral, you can write a recursive function which terminates in $O(1)$ on average. 399 400 **Solution** 401 402 #### Losing positions. 403 404 Let $(n, l)$ ($0 \leq m$) be losing if you lose if it's your turn, the current integer is $n$, and you cannot subtract $l$ (if $l$ is $0$, you can subtract everything). 405 406 #### Evil $n$. 407 408 Let $n$ be evil if $(n, 0)$ is losing (i.e., you lose even without constraints on the number you subtract). 409 410 #### Bound on the evil $n$ (I). 411 412 There are $O(N/m)$ evil $n$. Specifically, let $v_1, v_2, \ldots, v_k$ be the evil $n \leq N$. Then, $v_i - v_{i-1} \geq m+1$ (otherwise you would be able to move from an evil $n$ to another, contradiction). 413 414 #### Structure of losing positions and solution in $O(t(N+m))$. 415 416 If $(n, l)$ is losing, then $(n+l, l')$ with $l' \neq l$ is winning. This means that the number of losing $l$ for a fixed $n$ is either $0$, $1$, or $m+1$. Let's call $n$ "good", "neutral", and "evil", respectively. 417 Note that the losing states are $O(N+m)$ in total. 418 419 #### Even $m$. 420 421 For even $m$, only the multiples of $m+1$ are evil. In order to win, you can ensure that the last two moves have sum $m+1$. Since $m+1$ is odd, the last move will never be the same as the second last. 422 423 From now, let's only consider odd $m$. 424 425 #### More structure. 426 427 Let $f(n)$ be the distance from the largest evil $n' \leq n$. 428 429 There are three types of losing states. 430 431 * $(n, l)$ with $f(n) = 0$. 432 * $(n, f(n))$. 433 * $(n, f(n)/2)$ with $f(n) = m+1$. 434 435 This is a consequence of the slow solution described above. If $s$ is evil: 436 437 * the losing states $(s, l)$ propagate to $n$ in $[s+1, s+m]$; 438 * only the losing state $(s + \frac{m+1}{2}, \frac{m+1}{2})$ can propagate to $(s+m+1, \frac{m+1}{2})$, and in that case $s+m+2$ is evil. 439 440 So $s+m+1$ cannot be good (it is either neutral or evil). 441 442 #### Bound on the evil $n$ (II). 443 444 Let $v_1, v_2, \ldots, v_k$ be the evil $n \leq N$. Then, $m+1 \leq v_i - v_{i-1} \leq m+2$. 445 446  447 448 #### Our goal. 449 450 Let $v_1, v_2, \ldots, v_k$ be the evil $n \leq N$. We want to find them in $O(k) = O(N/m)$. In this way, we can solve the problem for all $m$ in $O(\sum_{1 \leq m \leq M} N/m) = O(N \log M)$. 451 452 #### Finding $v_{i+1}$. 453 454 We have $v_1, v_2, \ldots, v_i$, and we want to find $v_{i+1}$ in $O(1)$. It is enough to check whether $v_i + m + 1$ is evil. It's easier to check whether it is **not** evil, i.e., whether there exists a winning move. 455 Let's start from some $n$ which satisfies $v_j \leq n \leq v_{j+1}$. A winning move must ensure that the opponent cannot move to an evil state (necessary condition). So there are three candidate winning moves. 456 457 * Subtracting $n-v_j+1$ (so that the opponent is too far from $v_{j-1}$; this can only work if $v_j-v_{j-1} = m+2$). 458 * Subtracting $\frac{n-v_j}{2}$ (so that the opponent would have to subtract $\frac{n-v_j}{2}$ again to reach $v_j$). 459 * Subtracting $\frac{n-v_{j-1}}{2}$ (so that the opponent would have to subtract $\frac{n-v_{j-1}}{2}$ again to reach $v_{j-1}$). 460 461 #### Finding $v_{i+1}$ efficiently. 462 463 The previous observation provides a recursive function which can call itself up to $3$ times. 464 The recursive function answers the question "can we win starting from $(n, n-v_j)$?" (i.e., it is forbidden to make the move which would win immediately). This is equivalent to "is $n$ good or neutral?" 465 We want to make the average number of recursive calls less than $1$, so that the function terminates in $O(1)$. 466 467 * We do not need the first call, because $v_{j-1}+m+1$ is neutral (proved before). 468 * The second call happens with probability $\lesssim 1/2$ ($n-v_j$ must be even, and the first case must not apply). 469 * The third call happens with probability $\lesssim 3/8$ ($n-v_{j-1}$ must be even, the first case must not apply, and the second call must not succeed). 470 471 So the function calls itself $\lesssim 7/8$ times on average. This is fast enough for all $m$ (it can be tested locally). 472 473 **Code** 474 475 [350381246](/contest/2157/submission/350381246 "Submission 350381246 by Dominater069")