2218.md (13554B)
1 Source: https://codeforces.com/blog/entry/152680 2 3 I hope you all enjoyed the contest! Special thanks to: 4 5 * [damamila](/profile/damamila "Эксперт damamila"), for creating problem G 6 * [chromate00](/profile/chromate00 "Эксперт chromate00"), [AG-88301](/profile/AG-88301 "Эксперт AG-88301"), [simplelife](/profile/simplelife "Эксперт simplelife"), [SpyrosAliv](/profile/SpyrosAliv "Кандидат в мастера SpyrosAliv"), [reirugan](/profile/reirugan "Кандидат в мастера reirugan") and [damamila](/profile/damamila "Эксперт damamila") for editorials for B-G respectively. 7 * [cry](/profile/cry "Международный мастер cry"), for helping answer clarifications. 8 9 **Rate the contest!** 10 11 **Quality** 12 13 * Excellent contest 14 * Good contest 15 * Average contest 16 * Bad contest 17 * Horrible contest 18 19 **Difficulty** 20 21 * Trivial contest 22 * Easy contest 23 * Average contest 24 * Hard contest 25 * Impossible contest 26 27 #### [A — The 67th Integer Problem](https://codeforces.com/contest/2218/problem/A) 28 29 **Solution** 30 31 Many solutions exist here, and they are all trivial to find. Consider the value of $\min(x, y)$ when $x$ is constant, and you vary $y$. When $y \gt = x$, the value is $x$, and when $y \lt x$ the value is $y$. Therefore, the largest that $\min(x, y))$ can get for any value of $y$ is $x$. Therefore, outputting $y$ as any integer greater than or equal to $x$ works. 32 33 A common mistake was to output $y=x+1$, which fails because $68$ is greater than $67$, therefore not a valid output. 34 35 **Code (Python)** 36 37 ``` 38 for _ in range(int(input())): 39 print(67) 40 ``` 41 42 **Rate the problem!** 43 44 **Quality** 45 46 * Excellent problem 47 * Good problem 48 * Average problem 49 * Bad problem 50 * Horrible problem 51 52 **Difficulty** 53 54 * Trivial problem 55 * Easy problem 56 * Average problem 57 * Hard problem 58 * Impossible problem 59 60 #### [B — The 67th 6-7 Integer Problem](https://codeforces.com/contest/2218/problem/B) 61 62 **Solution** 63 64 Note how negating 6 out of 7 numbers is equivalent to negating all of them, and then negating one out of 7 numbers. Therefore, you can negate all 7 numbers, and then negate the least one afterwards. 65 66 **Code (Python)** 67 68 ``` 69 for i in range(int(input())): 70 nums = list(map(int, input().split())) 71 print(2 * max(nums) - sum(nums)) 72 ``` 73 74 **Rate the problem!** 75 76 **Quality** 77 78 * Excellent problem 79 * Good problem 80 * Average problem 81 * Bad problem 82 * Horrible problem 83 84 **Difficulty** 85 86 * Trivial problem 87 * Easy problem 88 * Average problem 89 * Hard problem 90 * Impossible problem 91 92 #### [C — The 67th Permutation Problem](https://codeforces.com/contest/2218/problem/C) 93 94 **Solution** 95 96 Observe that the position of an element doesn't really matter: we are only interested in whether an element is a median, a large element or a small element (in its triple). 97 98 Since $3n$ has no elements larger than it, it must be a large element. Similarly, since $1$ has no elements smaller than it, it must be a small element. 99 100 To maximise the sum of medians, we should pick the largest possible median available, which is $3n-1$. Since $1 \lt 3n-1 \lt 3n$, this forms a valid triple. 101 102 Now we can repeat the process on the subset ${2, 3, ... 3n-2}$, yielding the construction 103 104 $\{1, 3n-1, 3n\}, \{2, 3n-2, 3n-3\}, \cdots , \{n, 2n-1, 2n\}$ 105 106 **Proof that this is optimal** 107 108 Let the $i^{th}$ triple be ${l_i, m_i, r_i}$, with $l_i \lt m_i \lt r_i$, and wlog let $m_1 \lt m_2 \lt \cdots \lt m_n$ be the $n$ medians. 109 110 Each median needs an element strictly larger than it not used in any other triple. So there should be at least $1$ element larger than $m_n$, at least $3$ elements larger than $m_{n-1}$ (namely $m_n$, $r_n$, $r_{n-1}$), and more generally, at least $2k - 1$ elements larger than $m_{n-k+1}$. 111 112 In the set $1 \ldots 3n$, there are $3n - m_{n-k+1}$ elements larger than m_{n-k+1} (namely $m_{n-k+1}+1 \ldots 3n$), and so we need 113 114 $2k-1 \leq 3n - m\_{n-k+1}$ 115 116 Rearranging, we get $m_{n-k+1} \leq 3n - 2k + 1$, as in the optimal construction. 117 118 **Code (Python)** 119 120 ``` 121 for _ in range(int(input())): 122 n = int(input()) 123 k = 3 * n 124 for i in range(1,n+1): 125 print(i, k-1, k, end=" ") 126 k -= 2 127 print() 128 ``` 129 130 **Rate the problem!** 131 132 **Quality** 133 134 * Excellent problem 135 * Good problem 136 * Average problem 137 * Bad problem 138 * Horrible problem 139 140 **Difficulty** 141 142 * Trivial problem 143 * Easy problem 144 * Average problem 145 * Hard problem 146 * Impossible problem 147 148 #### [D — The 67th OEIS Problem](https://codeforces.com/contest/2218/problem/D) 149 150 **Hint 1** 151 152 Think something related to coprime numbers. 153 154 **Solution** 155 156 There are many ways to construct the array — we will provide two ways to do it. 157 158 Let's take $n+1$ distinct numbers $b_1,b_2,\ldots,b_{n+1}$. 159 160 Now let $a_i=b_i\cdot b_{i+1}$ for all $i$. 161 162 Now $\operatorname{gcd}(a_i,a_{i+1})=b_{i+1}\cdot \operatorname{gcd}(b_i,b_{i+2})$. 163 164 Now if $\operatorname{gcd}(b_i,b_{i+2})=1$ for all $i$, then we can obtain a distinct gcd for each adjacent pair and the construction is valid. 165 166 One way to obtain this is to let all $b_i$ be all primes starting from $2,3,5,\ldots$. Since all numbers are coprime to each other, their pairwise $gcd$ is $1$ and we get a valid construction. 167 168 Another way to obtain this to let all $b_i$ be odd numbers starting from $1,3,5,\ldots$. Since $\operatorname{gcd}(x,x+4)=1$ , where $x$ is odd, this construction is also valid. 169 170 **Code (Python)** 171 172 ``` 173 for _ in range(int(input())): 174 n = int(input()) 175 k = 1 176 for i in range(1,n+1): 177 print(k * (k+2), end=" ") 178 k += 2 179 print() 180 ``` 181 182 **Rate the problem!** 183 184 **Quality** 185 186 * Excellent problem 187 * Good problem 188 * Average problem 189 * Bad problem 190 * Horrible problem 191 192 **Difficulty** 193 194 * Trivial problem 195 * Easy problem 196 * Average problem 197 * Hard problem 198 * Impossible problem 199 200 #### [E — The 67th XOR Problem](https://codeforces.com/contest/2218/problem/E) 201 202 **Hint 1** 203 204 What happens after two operations? Does the first operation matter? 205 206 **Hint 2** 207 208 Remember the propery that $x \oplus x = 0$. 209 210 **Solution** 211 212 We have an array $a = [a_1, a_2, a_3, \ldots, a_n]$. Suppose we performed the operations from left to right, to see how operations affect the array. 213 214 After the first operation, the array becomes: $a = [a_2 \oplus a_1, a_3 \oplus a_1, \ldots, a_n \oplus a_1]$. Note that the first element was removed. 215 216 After the second operation, the array becomes $a = [(a_3 \oplus a_1) \oplus (a_2 \oplus a_1), \ldots, (a_n \oplus a_1) \oplus (a_2 \oplus a_1)]$. Due to Hint $2$, this is the same as $a = [a_3 \oplus a_2, \ldots, a_n \oplus a_2]$. 217 218 Note that this new array is independent of $a_1$. In fact, after any two operations, the value of the element chosen in the first operation does not matter. Taking this a step further: when doing three operations, the elements chosen for the first two operations do not matter. Inductively, the only thing that matters is the element we choose last for an operation (let it be $x$) and which element we never choose for an operation (let it be $y$). The final value of the array is going to be $x \oplus y$. 219 220 Since $n$ is small, it is enough to brute force all possible pairs $(x, y)$. The answer is the maximum value of $a_x \oplus a_y$ among all pairs. 221 222 **Code (Python)** 223 224 ``` 225 for _ in range(int(input())): 226 n = int(input()) 227 a = list(map(int, input().split())) 228 m = 0 229 for i in range(n): 230 for j in range(i+1, n): 231 m = max(m, a[i] ^ a[j]) 232 233 print(m) 234 ``` 235 236 **Bonus** 237 238 The problem of finding the integers $a$ and $b$ from an array such that $a \oplus b$ is maximized can be done in $O(n \log n)$ using a trie. 239 240 You can see in detail how this would work on [this](https://threadsiiithyderabad.quora.com/Tutorial-on-Trie-and-example-problems) post. Roughly speaking, we insert the binary representation of each number in the trie. After that, for each number we try to find which other number gives maximum xor, which can be done with a greedy walk on the trie. 241 242 **Rate the problem!** 243 244 **Quality** 245 246 * Excellent problem 247 * Good problem 248 * Average problem 249 * Bad problem 250 * Horrible problem 251 252 **Difficulty** 253 254 * Trivial problem 255 * Easy problem 256 * Average problem 257 * Hard problem 258 * Impossible problem 259 260 #### [F — The 67th Tree Problem](https://codeforces.com/contest/2218/problem/F) 261 262 **Hint 1** 263 264 We know that the number of vertices in the entire tree is $x+y$. Therefore, the subtree of the root has size $x+y$. So if $x+y$ is even and $x$ is zero, there is no valid tree. Similarly, if $x+y$ is odd and $y$ is zero, there is no valid tree. From this point onwards, we can now exclude the root by decrementing either $x$ or $y$, and only considering the other vertices. The root will be trivially satisfied. 265 266 **Hint 2** 267 268 We claim that for any vertex whose subtree has an even size, it must have at least one child with an odd size. Indeed, suppose all of its children have even size. Then the total number of vertices in the subtree will be the sum of some even numbers, plus one, the node itself. By contrapositive, this implies the desired claim. 269 270 Therefore, if the number of vertices with an even subtree size is larger than the number of vertices with an odd subtree size (excluding the root), there is no valid tree. 271 272 **Hint 3** 273 274 All other cases are possible. 275 276 **Solution** 277 278 Read the hints. 279 280 Now, we will try to make every vertex (excluding the root) have subtree size either $1$ or $2$. To do this, we will attach $x$ disjoint pairs of vertices. Then we will attach each pair, and all of the remaining vertices, to the root. Now, the number of vertices with an even subtree size is exactly $x$, the parent from each of the pairs, as desired. 281 282 **Code (Python)** 283 284 ``` 285 for _ in range(int(input())): 286 x, y = map(int, input().split()) 287 n = x + y 288 d = y - x 289 290 if (x == 0 and n % 2 == 0) or n//2<x: 291 print("NO") 292 continue 293 294 print("YES") 295 296 mm = 2 * x + (d % 2) 297 298 for i in range(2, mm + 1): 299 print(i - 1, i) 300 301 for i in range(mm + 1, n + 1): 302 print(mm, i) 303 ``` 304 305 **Rate the problem!** 306 307 **Quality** 308 309 * Excellent problem 310 * Good problem 311 * Average problem 312 * Bad problem 313 * Horrible problem 314 315 **Difficulty** 316 317 * Trivial problem 318 * Easy problem 319 * Average problem 320 * Hard problem 321 * Impossible problem 322 323 #### [G — The 67th Iteration of "Counting is Fun"](https://codeforces.com/contest/2218/problem/G) 324 325 **Hint 1** 326 327 When is there no valid $a$? 328 329 **Hint 2** 330 331 Remember for a person $i$ with $b_i \gt 0$ to be able to sit down, one of their neighbours already needs to be sat down. 332 333 **Hint 3** 334 335 What do you notice about people where $b_i = 0$? 336 337 **Hint 4** 338 339 If $b_i = 0$, then $a_i$ must also equal $0$. 340 341 **Solution** 342 343 If a person $i$ with $b_i \gt 0$ has no neighbour with a smaller $b_i$, they would never sit down so there is no valid $a$ so we output $0$. 344 345 We can observe that all $a_i$ are independent of each other so long as they are consistent with the array $b$. This means we can compute the number of possible $a_i$ for every $i$ separately. 346 347 Let $c_t$ be the number of people sat down at time $t$ or earlier. This is all people where $b_i \leq t$. For a time $t$, we can calculate $c_t$ using prefix sums as it is the sum of $c_{t-1}$ and the number of people that sit down at time $t$. 348 349 For a person to sit down at time $t$, two conditions had to be met: 350 351 1. At least $a_i$ people have already sat down strictly before time $t$. 352 2. At least one of their neighbors (person $i−1$ or $i+1$, if they exist) has already sat down strictly before time $t$. 353 354 We can now split people into $2$ types depending on which condition occurs first for them. 355 356 Type A: Condition $1$ is satisfied first. This means they are waiting for one of their neighbours to sit down so they can sit down. A person is of this type if the earliest time one of their neighbours sat down is exactly $1$ less than the time they sat down. This means their $a_i$ can be any value between $1$ and $c_{t-1}$ inclusive so there are $c_{t-1}$ possible values. 357 358 Type B: Condition $2$ is satisfied first. This means they are waiting for enough people to have sat down. A person is of this type if the time they sit down is at least $2$ greater than the earliest time one of their neighbours sat down. Since they did not sit down at time $t-1$, their $a_i$ must be greater than $c_{t-2}$. This means it must be between $c_{t-2}+1$ and $c_{t-1}$ inclusive, giving $c_{t-1}-c_{t-2}$ possibilities. 359 360 We can iterate over all people $i$ and look at the earliest time one of their neighbours sat down to find out which type of person they are, and then compute how many valid $a_i$ there are for them. 361 362 Finally, we can multiply the number of valid $a_i$ for every person, and output this modulo $676767677$. 363 364 **Code (Python)** 365 366 ``` 367 from itertools import accumulate 368 MOD = 676767677 369 370 for _ in range(int(input())): 371 n, m = map(int, input().split()) 372 b = [*map(int, input().split())] 373 cnt = [0] * m 374 for i in range(n): 375 cnt[b[i]] += 1 376 p = [0, *accumulate(cnt)] 377 ans = 1 378 for i in range(n): 379 if b[i] > 0: 380 t = float("inf") 381 for v in (i-1, i+1): 382 if v not in range(n): continue 383 t = min(t, b[v]) 384 t += 1 385 if b[i] > t: 386 ans = ans * cnt[b[i] - 1] % MOD 387 elif b[i] == t: 388 ans = ans * p[b[i]] % MOD 389 else: 390 ans = 0 391 print(ans % MOD) 392 ``` 393 394 **Rate the problem!** 395 396 **Quality** 397 398 * Excellent problem 399 * Good problem 400 * Average problem 401 * Bad problem 402 * Horrible problem 403 404 **Difficulty** 405 406 * Trivial problem 407 * Easy problem 408 * Average problem 409 * Hard problem 410 * Impossible problem