2085.md (15206B)
1 Source: https://codeforces.com/blog/entry/140933 2 3 **Fun Fact 0** 4 5 [Attention is all you need](https://arxiv.org/abs/1706.03762). 6 7 **Fun Fact 1** 8 9 The current problems are the original A A B C D E, respectively. 10 11 **Fun Fact 2** 12 13 The idea for problem D came up after eating at Sushiro, and the idea for problem E came up after eating at McDonald's. However, Sushiro is not a buffet restaurant. :( 14 15 **Fun Fact 3** 16 17 The intended solutions are short. 18 19 **Fun Fact 4** 20 21 Some (very) strong testers couldn't solve E when testing, and that's why we gave E so much score. 22 23 **Fun Fact suggested by testers** 24 25  26 27 #### [2085A - Serval and String Theory](/contest/2085/problem/A "Codeforces Round 1011 (Div. 2)") 28 29 **Hint 1** 30 31 When $s$ is lexicographically equal to or greater than the reversal of $s$, is it possible to make $s$ *universal* by performing the operations? 32 33 **Hint 2** 34 35 If possible, what is the minimum number of the operations required to make $s$ *universal*? 36 37 **Solution** 38 39 **Case 1.** If $s$ contains only one kind of letter, the answer will be `NO`. 40 41 **Case 2.** If $s$ is *universal* already, no operation is needed, and the answer will be `YES`. 42 43 Otherwise, $s$ falls into the following **Case 3**. 44 45 **Case 3.1.** When $s$ is not a palindrome, one can make $s$ *universal* in one operation by swapping the first pair of different letters of $s$ and its reversal. 46 47 $ \left.\begin{aligned} s ={}& \texttt{s}{\color{red}{\underline{\texttt{t}}}}\texttt{rings} \\ \text{reversal of } s ={}& \texttt{s}{\color{red}{\underline{\texttt{g}}}}\texttt{nirts} \end{aligned}\;\right\} \xrightarrow{\text{swap}} \boxed{\texttt{sgrints}} $ 48 49 **Case 3.2.** When $s$ is a palindrome, swapping any two distinct letters will make $s$ no longer a palindrome. Note that the reversal of $s$ after the swap can be obtained by swapping the letters in the symmetric positions of the original $s$. Since either $s$ or its reversal is *universal*, the original $s$ can be made *universal* in one operation. 50 51 $ s = \texttt{l}{\color{red}{\underline{\texttt{e}}}}{\color{blue}{\underline{\texttt{v}}}}\texttt{el} \xrightarrow{\text{swap}} \left\{\;\begin{aligned} s' ={}& \texttt{l}{\color{blue}{\underline{\texttt{v}}}}{\color{red}{\underline{\texttt{e}}}}\texttt{el} \\ \text{reversal of } s' ={}& \texttt{le}{\color{red}{\underline{\texttt{e}}}}{\color{blue}{\underline{\texttt{v}}}}\texttt{l} \end{aligned}\;\right\} \;\boxed{\texttt{leevl}} $ 52 53 Thus, for **Case 3**, the answer will be `NO` if no operation can be performed; otherwise, the answer will be `YES`. 54 55 **Code (Python)** 56 57 ``` 58 getint = lambda: int(input()) 59 getints = lambda: map(int, input().split()) 60 61 def solve(): 62 n, k = getints() 63 s = input().strip() 64 if s < s[::-1] or (k >= 1 and min(s) != max(s)): 65 print('YES') 66 else: 67 print('NO') 68 69 t = getint() 70 for _ in range(t): 71 solve() 72 ``` 73 74 #### [2085B - Serval and Final MEX](/contest/2085/problem/B "Codeforces Round 1011 (Div. 2)") 75 76 **Hint 1** 77 78 Before the last operation, what should the array be to obtain $0$? 79 80 **Hint 2** 81 82 How to make all the elements in the array non-zero? 83 84 **Solution** 85 86 Note that before the last operation, all the integers in the array should be positive. Thus, we aim to turn the zeroes in $a$ into non-zeroes. To achieve this, we split the given array $a$ into two halves and perform the operations on the halves that contain zeroes. After that, there will be no zeroes in either of the two halves. The final $0$ can be obtained by performing the last operation on the entire array. 87 88 $ [{\color{red}{\underline{1, 0, 1, 1}}}, {\color{blue}{2, 0, 8, 5}}] \to [{\color{red}{2}}, {\color{blue}{\underline{2, 0, 8, 5}}}] \to [\underline{{\color{red}{2}}, {\color{blue}{1}}}] \to [0] $ 89 90 **Another Hint** 91 92 In fact, the final element can be $0$ after the operations for any array of length $4$. Can you solve the problem under the constraint of $n=4$? 93 94 **Another Solution** 95 96 When $n \gt 4$, you can perform the operation on any subarray of length $(n-3)$. After the operation, the array $a$ will contain only $4$ integers, which can be solved by brute force. 97 98 **Code (Python)** 99 100 ``` 101 getint = lambda: int(input()) 102 getints = lambda: map(int, input().split()) 103 104 def solve(): 105 n = getint() 106 a = list(getints()) 107 op = [] 108 mid, r = n // 2, n 109 if 0 in a[mid:]: 110 op.append([mid + 1, n]) 111 r -= n - mid - 1 112 if 0 in a[:mid]: 113 op.append([1, mid]) 114 r -= mid - 1 115 op.append([1, r]) 116 print(len(op)) 117 for o in op: 118 print(*o) 119 120 t = getint() 121 for _ in range(t): 122 solve() 123 ``` 124 125 #### [2085C - Serval and The Formula](/contest/2085/problem/C "Codeforces Round 1011 (Div. 2)") 126 127 **Hint 1** 128 129 The formula $(x+k) + (y+k) = (x+k) \oplus (y+k)$ is equivalent to $(x+k) \mathbin{\&} (y+k) = 0$, where $\&$ denotes the bitwise AND operation. 130 131 **Hint 2** 132 133 Note that a power of $2$ shares no common bits with any positive integer less than it. 134 135 **Solution** 136 137 It can be shown that such an non-negative integer $k$ does not exist when $x=y$. 138 139 When $x\neq y$, one can show that $k = 2^n - \max(x, y)$ is a possible answer, where $2^n$ is a power of $2$ that is sufficiently large. 140 141 **Code (Python)** 142 143 ``` 144 getint = lambda: int(input()) 145 getints = lambda: map(int, input().split()) 146 147 def solve(): 148 x, y = getints() 149 if x == y: 150 print(-1) 151 else: 152 print(2 ** 48 - max(x, y)) 153 154 t = getint() 155 for _ in range(t): 156 solve() 157 ``` 158 159 #### [2085D - Serval and Kaitenzushi Buffet](/contest/2085/problem/D "Codeforces Round 1011 (Div. 2)") 160 161 **Hint 1** 162 163 Do not go for DP. 164 165 **Hint 2** 166 167 How many plates of sushi can be taken? 168 169 **Hint 3** 170 171 What are the constraints on the time of taking plates of sushi? 172 173 **Solution** 174 175 Note that the last $i$-th time taking a plate of sushi should be no later than the $(n - i\cdot(k+1) + 1)$-th minute. This constraint limits the time that a taking action can be performed. Therefore, we enumerate the $n$ minutes in chronological order, and greedily take the untaken plates delivered before with the greatest *deliciousness* when we reach a constraint, i.e., the current minute is the $(n - i\cdot(k+1) + 1)$-th minute for a certain $i$. The *deliciousnesses* of the untaken plates can be maintained by a heap. The total complexity is $O(n \log n)$. 176 177 **Code (C++)** 178 179 ``` 180 #include <cstdio> 181 #include <queue> 182 183 using namespace std; 184 185 const int N = 2e5 + 5; 186 187 int n, k; 188 int d[N]; 189 long long ans; 190 191 void solve() { 192 scanf("%d%d", &n, &k); 193 ans = 0; 194 priority_queue <int> q; 195 for (int i = 1; i <= n; i++) { 196 scanf("%d", &d[i]); 197 q.push(d[i]); 198 if ((n - i + 1) % (k + 1) == 0) { 199 ans += q.top(); 200 q.pop(); 201 } 202 } 203 printf("%lld\n", ans); 204 } 205 206 int main() { 207 int t; 208 scanf("%d", &t); 209 while (t--) 210 solve(); 211 return 0; 212 } 213 ``` 214 215 #### [2085E - Serval and Modulo](/contest/2085/problem/E "Codeforces Round 1011 (Div. 2)") 216 217 **Hint 1** 218 219 What happens when an integer $a_i$ mods $k$? 220 221 **Hint 2** 222 223 Note that the difference between $a_i$ and $b_i$ is a multiple of $k$. 224 225 **Hint 3** 226 227 The same holds for the difference between the sum of $a_i$ and the sum of $b_i$. 228 229 **Hint 4** 230 231 Notice that $d(n) \leq 2304$ holds for all $n \leq 10^{10}$, where $d(n)$ denotes the number of divisors of $n$. 232 233 **Solution** 234 235 Note that if such a magic number $k$ exists, it will be a divisor of $\Delta = \sum a_i - \sum b_i$ when $\Delta \neq 0$, or it can be any integer greater than all the $a_i$. Thus, we can check all the divisors of $\Delta$, resulting in a solution of $O\left(\sum (n \cdot d(\sum a_i) + \sqrt{\sum a_i})\right)$ time, where $d(n)$ denotes the number of divisors of $n$. 236 237 **Code (C++)** 238 239 ``` 240 #include <cstdio> 241 242 using namespace std; 243 244 const int N = 1e4 + 5; 245 const int C = 1e6 + 5; 246 247 int n; 248 int a[N], b[N]; 249 int cnt[C]; 250 long long s; 251 252 bool check(int k) { 253 for (int i = 1; i <= n; i++) 254 cnt[a[i] % k]++; 255 for (int i = 1; i <= n; i++) 256 if (--cnt[b[i]] < 0) { 257 cnt[b[i]] = 0; 258 for (int i = 1; i <= n; i++) 259 cnt[a[i] % k] = 0; 260 return 0; 261 } 262 return 1; 263 } 264 265 void solve() { 266 scanf("%d", &n); 267 s = 0; 268 for (int i = 1; i <= n; i++) { 269 scanf("%d", &a[i]); 270 s += a[i]; 271 } 272 for (int i = 1; i <= n; i++) { 273 scanf("%d", &b[i]); 274 s -= b[i]; 275 } 276 if (s == 0) { 277 printf("%d\n", check(0xc0ffee) ? 0xc0ffee : -1); 278 return; 279 } 280 for (int i = 1; 1ll * i * i <= s; i++) 281 if (s % i == 0) { 282 if (check(i)) { 283 printf("%d\n", i); 284 return; 285 } 286 if (i < C && check(s / i)) { 287 printf("%d\n", (int)(s / i)); 288 return; 289 } 290 } 291 printf("-1\n"); 292 } 293 294 int main() { 295 int t; 296 scanf("%d", &t); 297 while (t--) 298 solve(); 299 return 0; 300 } 301 ``` 302 303 #### [2085F1 - Serval and Colorful Array (Easy Version)](/contest/2085/problem/F1 "Codeforces Round 1011 (Div. 2)") 304 305 **Hint 1** 306 307 Consider the integers in the *colorful* subarray after swapping. 308 309 **Hint 2** 310 311 How to gather these integers together, forming a *colorful* subarray, with the minimum number of swaps? 312 313 **Hint 3** 314 315 Consider the middle one among all the the elements in the *colorful* subarray. 316 317 **Solution** 318 319 Consider the elements in the *colorful* subarray after swapping. The first observation is as follows. 320 321 **Observation.** Mark the elements in the *colorful* subarray. Before swapping, to make these marked elements continuous, gathering them toward the middle one among them minimizes the number of swaps. 322 323 **Proof.** It is not optimal to swap two marked elements. Thus, the leftmost $x$ elements will move to their right, and the rightmost $(k-x)$ elements will move to their left. They will meet at some point between the $x$-th element and the $(x+1)$-th element. If $x \lt {k\over 2}$, adjusting the meeting point to its right reduces $(k-x)-x \gt 0$ swaps. If $x \gt {k\over 2}$, we can adjust it to its left and reduce the number of swaps similarly. Therefore, one can show that setting the meeting point to the middle of them is optimal through adjustments. $\square$ 324 325 From the observation we can also conclude that, the minimum number of swaps required to make the marked elements continuous is the difference between the sum of the distances from each marked element to the middle position before swapping and that sum after swapping, if the marked elements are swapped toward the middle position. Notice that the latter sum is a fixed constant only related to $k$. 326 327 Focusing on the middle position of the *colorful* subarray, we enumerate all the positions in the array as possible middle positions. For each possible middle position $p$, to form the *colorful* subarray whose middle position is $p$, we should choose ${k\over 2}$ distinct integers from its left and the other $k\over 2$ from its right. The rounding of $k\over 2$ will not affect the correctness as long as the sum of the rounded numbers is $k$. 328 329 For each $1\leq i\leq k$, we should determine whether $i$ should be chosen from the left side of $p$ or the right side of $p$. Let the distance from $p$ to the rightmost integer $i$ on its left be $l_i$, and the distance for the right side be $r_i$. We should choose either $l_i$ or $r_i$ for each $i$ under the constraint that both the number of chosen $l_i$ and that of $r_i$ are $k\over 2$, minimizing the sum of the distances we choose. This can be done by first forcing to choose all the $l_i$, and then choosing the smallest $k\over 2$ elements of $(r_i-l_i)$ greedily. 330 331 In implementation, when enumerating the middle position $p$, both $l_i$ and $r_i$ can be simply calculated in $O(n)$ time, and then sort $(r_i - l_i)$ in $O(n\log n)$ time. The total complexity is $O(n^2\log n)$. 332 333 **Code (C++)** 334 335 ``` 336 #include <cstdio> 337 #include <algorithm> 338 339 using namespace std; 340 341 const int N = 3005; 342 const long long oo = 1e18; 343 344 int n, k; 345 int a[N], l[N], r[N], d[N]; 346 long long ans; 347 348 void solve() { 349 scanf("%d%d", &n, &k); 350 for (int i = 1; i <= n; i++) 351 scanf("%d", &a[i]); 352 ans = oo; 353 for (int i = 1; i <= n; i++) { 354 for (int j = 1; j <= k; j++) 355 l[j] = r[j] = n + 1; 356 for (int j = i; j; j--) 357 l[a[j]] = min(l[a[j]], i - j); 358 for (int j = i; j <= n; j++) 359 r[a[j]] = min(r[a[j]], j - i); 360 long long s = 0; 361 for (int j = 1; j <= k; j++) { 362 s += l[j]; 363 d[j] = r[j] - l[j]; 364 } 365 sort(d + 1, d + k + 1); 366 for (int j = 1; j <= (k + 1) / 2; j++) 367 s += d[j]; 368 ans = min(ans, s); 369 } 370 for (int i = 1; i <= k; i++) 371 ans -= abs(i - (k + 1) / 2); 372 printf("%lld\n", ans); 373 } 374 375 int main() { 376 int T; 377 scanf("%d", &T); 378 while (T--) 379 solve(); 380 return 0; 381 } 382 ``` 383 384 #### [2085F2 - Serval and Colorful Array (Hard Version)](/contest/2085/problem/F2 "Codeforces Round 1011 (Div. 2)") 385 386 **Hint 1** 387 388 Is it possible to simplify the constraints? 389 390 **Hint 2** 391 392 Is it possible to remove the constraint that exactly $k\over 2$ elements should be chosen from both sides of the enumerated position? 393 394 **Solution** 395 396 Optimizing the solution of F1 using (possibly, heavy) data structures results in a $O(n\log n)$ solution. 397 398 Here we introduce a linear approach for F2 came up by [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan"). In fact, the following proposition holds. 399 400 **Proposition.** The answer obtained is still correct without the constraint that exactly $k\over 2$ elements should be chosen from both sides of the enumerated position. 401 402 Without the constraint, when enumerating the position $p$, we can directly choose the smaller one between $l_i$ and $r_i$ for each $1\leq i\leq k$. 403 404 **Proof.** On the one hand, notice that the distance sum will not be smaller when $p$ is not the middle position among the chosen elements. On the other hand, consider the *colorful* subarray that produces the optimal answer, and mark the elements in it first. When $p$ enumerates to the middle position of the marked elements before swapping, the minimal distance sum without the constraint is no greater than that under the constraint. Therefore, all the considered candidates are no less than the real answer, and the real answer can be reached, completing the proof. $\square$ 405 406 In implementation, we consider the contribution to each position $p$ for each integer $1\leq i\leq k$. For a certain $i$, it can be shown that the delta of the contribution will be one of $-1$, $0$, or $+1$ when $p$ moves to an adjacent position. The delta of the contribution remains unchanged for most positions, and only changes either at the position where $i$ placed, or at the midpoint between two adjacent $i$. By pre-calculating the changes of contribution deltas over all the $i$ and performing the prefix sum on the array twice, we can obtain the distance sums, resulting in an $O(n)$ solution. 407 408 **Code (C++)** 409 410 ``` 411 #include <cstdio> 412 #include <algorithm> 413 414 using namespace std; 415 416 const int N = 4e5 + 5; 417 const long long oo = 1e18; 418 419 int n, k; 420 int a[N]; 421 int last[N], dd[N]; 422 long long s, d, ans; 423 424 void solve() { 425 scanf("%d%d", &n, &k); 426 for (int i = 1; i <= n; i++) 427 last[i] = dd[i] = 0; 428 s = 0; 429 for (int i = 1; i <= n; i++) { 430 scanf("%d", &a[i]); 431 if (!last[a[i]]) 432 s += i - 1; 433 else { 434 int pre = last[a[i]]; 435 int mid = (pre + i) / 2; 436 if ((pre + i) & 1) { 437 dd[mid]--; 438 dd[mid + 1]--; 439 } else 440 dd[mid] -= 2; 441 } 442 dd[i] += 2; 443 last[a[i]] = i; 444 } 445 ans = oo; 446 d = -k; 447 for (int i = 1; i <= n; i++) { 448 ans = min(ans, s); 449 d += dd[i]; 450 s += d; 451 } 452 for (int i = 1; i <= k; i++) 453 ans -= abs(i - (k + 1) / 2); 454 printf("%lld\n", ans); 455 } 456 457 int main() { 458 int T; 459 scanf("%d", &T); 460 while (T--) 461 solve(); 462 return 0; 463 } 464 ```