1713.md (20248B)
1 Source: https://codeforces.com/blog/entry/105419 2 3 **Before the round starts** 4 5 Great efforts have been put over last year. We want to say thanks to everybody who helped us to make this round as it is. Cannot wait to see you guys on the next one! 6 7 **Testers' predictions** 8 9 | Tester | A | B | C | D | E | F | 10 | --- | --- | --- | --- | --- | --- | --- | 11 | [tfg](/profile/tfg "Grandmaster tfg") | 800 | 1100 | 1500 | 1600 | 1900 | 2400 | 12 | [neko_nyaaaaaaaaaaaaaaaaa](/profile/neko_nyaaaaaaaaaaaaaaaaa "Grandmaster neko_nyaaaaaaaaaaaaaaaaa") | 800 | 1100 | 1700 | 1900 | 2100 | 2600 | 13 | [BucketPotato](/profile/BucketPotato "International Master BucketPotato") | 800 | 1000 | 1400 | 1800 | 2400 | - | 14 | [LetterC67](/profile/LetterC67 "Master LetterC67") | 800 | 1200 | 1400 | 1600 | 2100 | - | 15 | [FireGhost](/profile/FireGhost "Master FireGhost") | 800 | 1100 | 1500 | 1900 | 2000 | 2400 | 16 | [fextivity](/profile/fextivity "Grandmaster fextivity") | 800 | 1000 | 1400 | 1700 | 2000 | 2400 | 17 | [generic_placeholder_name](/profile/generic_placeholder_name "Grandmaster generic_placeholder_name") | 800 | 1100 | 1600 | 1900 | 2200 | - | 18 19 **Some comments from testers and authors** 20 21 **From BucketPotato** 22 23  24 25 **From tfg** 26 27  28 29 **Shower thoughts from vangtrangtan** 30 31  32 33 **From Fireghost** 34 35  36 37 **Also from Fireghost** 38 39  40 41 **From thenymphsofdelphi** 42 43  44 45 **From antontrygubO_o** 46 47  48 49 **Huge help from Vladithur when polishing our statements** 50 51   52 53 **From hydroshiba** 54 55  56 57 **From thanhchauns2** 58 59  60 61 **From me** 62 63  64 65 **From errorgorn** 66 67  68 69 [1713A - Traveling Salesman Problem](https://codeforces.com/contest/1713/problem/A) 70 71 **Hint 1** 72 73 Do we actually need to go off the axis? 74 75 **Hint 2** 76 77 How to avoid visiting an axis more than once? 78 79 **Tutorial** 80 81 ### [1713A - Traveling Salesman Problem](https://codeforces.com/contest/1713/problem/A) 82 83 Suppose we only have boxes on the $Ox+$ axis, then the optimal strategy is going in the following way: $(0, 0), (x_{max}, 0), (0, 0)$. There is no way to do in less than $2 \cdot |x_{max}|$ moves. 84 85 What if we have boxes on two axis? Let's assume it is $Oy+$, suppose we have a strategy to go in the following way: $(0, 0), (x_{max}, 0),..., (0, y_{max}), (0, 0)$. In this case it is optimal to fill the three dots with $(0, 0)$, which is just solving each axis independently. 86 87 Therefore, the number of axis does not matters. For each axis that has at least one box, go from $(0, 0)$ to the farthest one, then come back to $(0, 0)$. 88 89 Time complexity: $O(n)$ 90 91 **Solution** 92 93 ``` 94 def solve(): 95 n = int(input()) 96 minX, minY, maxX, maxY = 0, 0, 0, 0 97 for i in range(n): 98 x, y = list(map(int, input().split())) 99 minX = min(x, minX) 100 maxX = max(x, maxX) 101 minY = min(y, minY) 102 maxY = max(y, maxY) 103 print(2 * (maxX + maxY - minX - minY)) 104 105 test = int(input()) 106 while test > 0: 107 test -= 1 108 solve() 109 ``` 110 111 **Feedback** 112 113 * Didn't solve 114 * Good problem 115 * Average problem 116 * Bad problem 117 118 [1713B - Optimal Reduction](https://codeforces.com/contest/1713/problem/B) 119 120 **Hint 1** 121 122 How to calculate $f(a)$? 123 124 **Hint 2** 125 126 What if $a$ is intially sorted? 127 128 **Hint 3** 129 130 Consider $a$ has $3$ elements. What if $a_1 \gt a_2$ and $a_2 \lt a_3$? 131 132 **Tutorial** 133 134 ### [1713B - Optimal Reduction](https://codeforces.com/contest/1713/problem/B) 135 136 Let's call $M = max(a_1, a_2, \dots, a_n)$. 137 138 The problem asks us to make all its elements become $0$ in some operations. And for each operation, we subtract each elements in an subarray by $1$. Thus, every largest elements of the array have to be decreased in at least $M$ operations. And also because of that, $min(f(p))$ over all permutations $p$ of $a$ is never less than $M$. 139 140 Every permutations $p$ of $a$ such that $f(p) = M$ have the same construction. That is, they can be divided into $2$ subarrays where the **left subarray** is sorted in **non-decreasing order**, and the **right subarray** is sorted in **non-increasing order**. In other words, the elements of the array should form a mountain. 141 142 **Why?** 143 144 This is how to perform the operations: assign $l$ equal to the index of the leftmost element whose value is not $0$, and assign $r$ equal to the index of the rightmost element whose value is also not $0$, then subtract each element $a_l, a_{l+1}, \dots, a_r$ by $1$. Repeat the operation until all elements become $0$. The thing is each element of the array is always greater or equal than every elements in the left side or the right side of it so it can never become negative at some point of performing the operations. Besides, all the largest elements are also included in each operation that we perform, which mean we've achieved the goal to make all elements of the array become $0$ in $M$ operations. 145 146 So how to check whether $f(a) = M$ or not? Well, we can define $preLen$ equal to the length of the longest prefix which is sorted in non-decreasing order. Then define $sufLen$ equal to the length of the longest suffix which is sorted in non-increasing order. If $preLen + sufLen \ge n$, the answer is *YES*. 147 148 Time complexity: $O(n)$ 149 150 **Solution** 151 152 ``` 153 #include <bits/stdc++.h> 154 using namespace std; 155 156 const int N = 1e5 + 5; 157 158 int n, a[N]; 159 160 int main() { 161 int tc; 162 for (cin >> tc; tc--; ) { 163 cin >> n; 164 for (int i = 1; i <= n; i++) 165 cin >> a[i]; 166 167 int preLen = 1; 168 while (preLen < n && a[preLen] <= a[preLen + 1]) 169 preLen++; 170 171 int sufLen = 1; 172 while (sufLen < n && a[n-sufLen] >= a[n-sufLen + 1]) 173 sufLen++; 174 175 if (preLen + sufLen >= n) 176 cout << "YES" << endl; 177 else 178 cout << "NO" << endl; 179 } 180 } 181 ``` 182 183 **Feedback** 184 185 * Didn't solve 186 * Good problem 187 * Average problem 188 * Bad problem 189 190 [1713C - Build Permutation](https://codeforces.com/contest/1713/problem/C) 191 192 **Hint 1** 193 194 Is there any case that the answer doesn't exist? 195 196 **Hint 2** 197 198 **What if:** $n \le 5$ 199 200 **Hint 3** 201 202 Construct the suffix instead of the prefix. 203 204 **Hint 4** 205 206 With any positive integer $x$, there is at least one square number in $[x, 2x]$. [Proof.](https://math.stackexchange.com/questions/1190737/proving-that-there-is-a-perfect-square-between-n-and-2n) 207 208 **Tutorial** 209 210 ### [1713C - Build Permutation](https://codeforces.com/contest/1713/problem/C) 211 212 First, let's prove that the answer always exists. Let's call the smallest square number that is not smaller than $k$ is $h$. Therefore $h \leq 2 \cdot k$, which means $h - k \leq k$. [Proof.](https://math.stackexchange.com/questions/1190737/proving-that-there-is-a-perfect-square-between-n-and-2n) 213 214 So we can fill $p_i = h - i$ for $(h - k \leq i \leq k)$. Using this method we can recursively reduce $k$ to $h - k - 1$, then all the way down to $-1$. 215 216 We can prove that $h - k \geq 0$, as $h \geq k$. 217 218 Time complexity: $O(n)$ 219 220 **Solution** 221 222 ``` 223 #include <bits/stdc++.h> 224 using namespace std; 225 226 const int N = 1e5 + 5; 227 228 int n, ans[N]; 229 230 void recurse(int r) { 231 if (r < 0) return; 232 int s = sqrt(2*r); s *= s; 233 int l = s - r; recurse(l - 1); 234 for (; l <= r; l++, r--) { 235 ans[l] = r; ans[r] = l; 236 } 237 } 238 239 int main() { 240 int tc; cin >> tc; 241 while (tc--) { 242 cin >> n; recurse(n - 1); 243 for (int i = 0; i < n; i++) 244 cout << ans[i] << ' '; 245 cout << '\n'; 246 } 247 } 248 ``` 249 250 **Feedback** 251 252 * Didn't solve 253 * Good problem 254 * Average problem 255 * Bad problem 256 257 [1713D - Tournament Coundown](https://codeforces.com/contest/1713/problem/D) 258 259 **Hint 1** 260 261 We made sure that almost every $2^{n - 1}$ solutions cannot pass. 262 263 **Hint 2** 264 265 Did you use the $0$ query? 266 267 **Hint 3** 268 269 $\frac{2^{n + 1}}{3} = 2^n \cdot \frac{2}{3}$, what is the conclusion? 270 271 **Tutorial** 272 273 ### [1713D - Tournament Coundown](https://codeforces.com/contest/1713/problem/D) 274 275 There is a way to erase $3$ participants in every $2$ queries. Since there are $2^n - 1$ participants to be removed, the number of queries will be $\left \lceil (2^n - 1) \cdot \frac{2}{3} \right \rceil = \left \lfloor \frac{2^{n + 1}}{3} \right \rfloor$. Suppose there are only $4$ participants. In the first query we will ask the judge to compare the $1^{st}$ and the $3^{rd}$ participants. There are three cases: 276 277 * The $1^{st}$ participant wins more game than the $3^{rd}$ one: the $2^{nd}$ and $3^{rd}$ cannot be the winner. 278 * The $3^{rd}$ participant wins more game than the $1^{st}$ one: the $1^{st}$ and $4^{th}$ cannot be the winner. 279 * The $1^{st}$ and $3^{rd}$ participants' numbers of winning games are equal: both the $1^{st}$ and $3^{rd}$ cannot be the winner. 280 281 Ask the remaining two participants, find the winner between them. 282 283 If there are more than $4$ participants, we can continuously divide the number by $4$ again and again, until there are at most $2$ participants left. Now we can get the winner in one final query. 284 285 **Solution** 286 287 ``` 288 #include <bits/stdc++.h> 289 290 using namespace std; 291 292 int ask(vector<int> &k) 293 { 294 cout << "? " << k[0] << ' ' << k[2] << endl; 295 int x; 296 cin >> x; 297 if (x == 1) 298 { 299 cout << "? " << k[0] << ' ' << k[3] << endl; 300 cin >> x; 301 if (x == 1) return k[0]; 302 return k[3]; 303 } 304 else if (x == 2) 305 { 306 cout << "? " << k[1] << ' ' << k[2] << endl; 307 cin >> x; 308 if (x == 1) return k[1]; 309 return k[2]; 310 } 311 else 312 { 313 cout << "? " << k[1] << ' ' << k[3] << endl; 314 cin >> x; 315 if (x == 1) return k[1]; 316 return k[3]; 317 } 318 } 319 320 void solve() 321 { 322 int n; 323 cin >> n; 324 vector<int> a, b; 325 for (int i = 1; i <= (1LL << n); i++) 326 { 327 a.push_back(i); 328 } 329 while (a.size() > 2) 330 { 331 while (!a.empty()) 332 { 333 vector<int> k(4); 334 k[0] = a.back(); 335 a.pop_back(); 336 k[1] = a.back(); 337 a.pop_back(); 338 k[2] = a.back(); 339 a.pop_back(); 340 k[3] = a.back(); 341 a.pop_back(); 342 int win = ask(k); 343 b.push_back(win); 344 } 345 a = b; 346 b.clear(); 347 } 348 if (a.size() == 2) 349 { 350 cout << "? " << a[0] << ' ' << a[1] << endl; 351 int x; 352 cin >> x; 353 if (x == 2) a[0] = a[1]; 354 } 355 cout << "! " << a[0] << endl; 356 } 357 358 int main(int argc, char ** argv) 359 { 360 int tests; 361 cin >> tests; 362 while(tests--) solve(); 363 } 364 ``` 365 366 **Feedback** 367 368 * Didn't solve 369 * Good problem 370 * Average problem 371 * Bad problem 372 373 [1713E - Cross Swapping](https://codeforces.com/contest/1713/problem/E) 374 375 **Hint 1** 376 377 Think of the most to the least significant cell of the matrix. 378 379 **Hint 2** 380 381 How many positions in the matrix can a cell travel to after performing the operations? 382 383 **Hint 3** 384 385 And for each position that that cell can travel to, how many ways are there we can make it? 386 387 **Tutorial** 388 389 ### [1713E - Cross Swapping](https://codeforces.com/contest/1713/problem/E) 390 391 Let's take a look at what the lexicographically smallest matrix is. Let's call $(x, y)$ a cell that is in the intersection of row $x$ and column $y$ of the matrix, and the integer written on that cell is $A_{x, y}$. A cell $(x_p, y_p)$ of this matrix is called more significant than the another cell $(x_q, y_q)$ if and only if $x_p \lt x_q$, or $x_p = x_q$ and $y_p \lt y_q$. The problem asks us to find the smallest matrix so the best suitable way to solve this problem is to traverse through the most to the least significant cell of the matrix, then determine if the current cell can be minimized or not. 392 393 Suppose the current cell we are looking at is $(x, y)$. If $x = y$ then its position will not change after performing the operations. But if $x \neq y$, there are exactly $2$ operations that swap $(x, y)$ with another cell, that is $k = x$ and $k = y$. Both of these operations swap $(x, y)$ with the same cell $(y, x)$. So the only way we can minimize the value of $(x, y)$ is to try swapping it with $(y, x)$ (if $x \lt y$ and $A_{x, y} \gt A_{y, x}$) in some way. 394 395 As a result we have our constructive algorithm. Remind that for each operation $k = i$ of the matrix ($1 \le i \le n$), there are $2$ states: it is being performed and not being performed. Suppose we have traversed to the cell $(x, y)$. If $x \ge y$, ignore it. If $x \lt y$ then we try to make $A_{x, y} = min(A_{x, y}, A_{y, x})$ by deciding to swap or not to swap the cells. If $A_{x, y} \gt A_{y, x}$, try to swap $(x, y)$ with $(y, x)$ by making $2$ operations $k = x$ and $k = y$ having different states. And if $A_{x, y} \lt A_{y, x}$ then we should keep their positions unchanged by making $2$ operations $k = x$ and $k = y$ having the same state. Note that if $A_{x, y} = A_{y, x}$, we do nothing. 396 397 Let's implement this algorithm using a simple DSU where the $ith$ node represents the operation $k = i$. We define the value $par[u]$ in such a way that, suppose $p$ is the root of the $u$ node's component, $par[u] = p$ if $2$ operations $k = u$ and $k = p$ should have the same state, or $par[u] = -p$ if $2$ operations $k = u$ and $k = p$ should have different states. Define another function $join(i, j)$ to union $2$ nodes $i$ and $j$ to the same component. Note that $u$ and $-u$ are always in the same component and $par[-u] = -par[u]$. Thus, for the current cell $(x, y)$, we want to swap it with $(y, x)$ by calling $join(x, -y)$, or keep its position unchanged by calling $join(x, y)$. 398 399 After constructing the graphs, the last thing to do is to determine which operations should be performed. One way to do so is for each root of the components of the DSU, we perform the operation which this root represents for. Then for other nodes just check $par[i] \gt 0$ for the $ith$ node and if it is true, the $k = i$ operation should be performed. When we have the list of the operations that need to be performed, we can bruteforcely perform each operation from the list one by one and the final matrix will be the lexicographically smallest matrix. 400 401 Time complexity: $O(n^2)$ 402 403 **Solution** 404 405 ``` 406 #include <bits/stdc++.h> 407 using namespace std; 408 409 const int N = 2e3 + 5; 410 411 int n, a[N][N]; 412 413 int par[N]; 414 int getPar(int u) { 415 if (u < 0) return -getPar(-u); 416 if (u == par[u]) return u; 417 return par[u] = getPar(par[u]); 418 } 419 void join(int u, int v) { 420 u = getPar(u); v = getPar(v); 421 if (abs(u) != abs(v)) { 422 if (u > 0) par[u] = v; 423 else par[-u] = -v; 424 } 425 } 426 427 int main() { 428 cin.tie(nullptr) -> sync_with_stdio(false); 429 430 int tc; cin >> tc; 431 while (tc--) { 432 cin >> n; 433 for (int i = 1; i <= n; i++) 434 for (int j = 1; j <= n; j++) { 435 cin >> a[i][j]; 436 } 437 438 iota(par + 1, par + n + 1, 1); 439 // set par[i] == i for i in [1, n] 440 441 for (int i = 1; i <= n; i++) 442 for (int j = 1; j <= n; j++) { 443 if (a[i][j] < a[j][i]) join(i, j); 444 if (a[i][j] > a[j][i]) join(i, -j); 445 } 446 447 for (int i = 1; i <= n; i++) { 448 if (getPar(i) < 0) continue; 449 // we only perform the operation 450 // if and only if getPar(i) > 0 451 for (int j = 1; j <= n; j++) 452 swap(a[i][j], a[j][i]); 453 } 454 455 for (int i = 1; i <= n; i++) { 456 for (int j = 1; j <= n; j++) { 457 cout << a[i][j] << ' '; 458 } 459 cout << '\n'; 460 } 461 } 462 } 463 ``` 464 465 **Feedback** 466 467 * Didn't solve 468 * Good problem 469 * Average problem 470 * Bad problem 471 472 [1713F - Lost Array](https://codeforces.com/contest/1713/problem/F) 473 474 **Hint 0** 475 476 * Is there any case that the answer doesn't exist? 477 * If exist, are there multiple? 478 479 **Hint 1** 480 481 * How many times does $a_i$ contribute to $b_{j, n}$? 482 483 **Hint 1.1** 484 485 [Pascal's Triangle](https://en.wikipedia.org/wiki/Pascal%27s_triangle) 486 487 $\rightarrow$ Calculate value that $a_i$ contribute to $b_{j, n}$. 488 489 **Hint 1.2** 490 491 [SierpiĆski triangle](https://en.wikipedia.org/wiki/Sierpi%C5%84ski_triangle) 492 493 **Hint 2** 494 495 Consider the inverse problem: Given array $a$. Construct $b_{j, n}$ for all $j$. How can you solve this problem? 496 497 **Hint 3** 498 499 Consider easier problem: Let construct matrix $g$ of size $(2n + 1) \times (n + 1)$ same way as matrix $b$. Given $g_{i, n}$ $(1 \le i \le 2n)$, please reconstruct $a$. How can you solve this problem? 500 501 **Tutorial** 502 503 ### [1713F - Lost Array](https://codeforces.com/contest/1713/problem/F) 504 505 First, we can see that $a_i$ contribute $\binom{(n - i) + (j - 1)}{j - 1}$ times to $b_{j, n}$, which can calculate similar to [Pascal's Triangle](https://en.wikipedia.org/wiki/Pascal%27s_triangle). It's easy to see that the value that $a_i$ contribute to $b_{j, n}$ equal to $a_i$ when $\binom{(n - i) + (j - 1)}{j - 1}$ is odd, $0$ otherwise. 506 507 Let's solve the inverse problem: Given array $a$. Construct $b_{j, n}$ for all $j$. $(1 \le j \le n)$ 508 509 By [Lucas Theorem](https://en.wikipedia.org/wiki/Lucas%27s_theorem), $\binom{(n - i) + (j - 1)}{j - 1}$ is odd when $(n - i)\ AND\ (j - 1) = 0$ 510 511 $\rightarrow (n - i)$ is a submask of $\sim(j - 1)$ (with $\sim a$ is inverse mask of $a$). 512 513 Let define $m = 2^k$ with smallest $m$ satisfy $m \ge n$. Set $a'_i = a_i$ and $b'_j = b_{\sim(j - 1)} = b_{(m - 1) - (j - 1)}$ then $b'$ is the [Zeta transform](https://codeforces.com/blog/entry/45223) of $a'$. 514 515 So we could apply [Mobius transform](https://codeforces.com/blog/entry/72488) in $b'$ to get $a'$. Since the operation is xor, mobius transform is as same as zeta transform. But unlike the inverse problem, there are some differences. We don't know the value of $b'_i$ for $i$ in $[0, m - n)$. 516 517 Let $c$ be the sum over supermasks array of $b'$ (with $i$ is supermasks of $j$ when $i\ AND\ j = j)$, then set $c_k = 0$ for $k$ in $[m - n, m)$. After that, do another sum over supermasks on $c$ to get original value of $b'$. Now we can find $a'$ from $b'$ and $a$ from $a'$. 518 519 Complexity: $O(nlog_2(n))$ 520 521 **Solution** 522 523 ``` 524 #include <bits/stdc++.h> 525 #include <ext/pb_ds/assoc_container.hpp> 526 #include <ext/pb_ds/tree_policy.hpp> 527 using namespace std; 528 using namespace __gnu_pbds; 529 530 #define endl '\n' 531 #define fi first 532 #define se second 533 #define For(i, l, r) for (auto i = (l); i < (r); i++) 534 #define ForE(i, l, r) for (auto i = (l); i <= (r); i++) 535 #define FordE(i, l, r) for (auto i = (l); i >= (r); i--) 536 #define Fora(v, a) for (auto v: (a)) 537 #define bend(a) (a).begin(), (a).end() 538 #define isz(a) ((signed)(a).size()) 539 540 using ll = long long; 541 using ld = long double; 542 using pii = pair <int, int>; 543 using vi = vector <int>; 544 using vpii = vector <pii>; 545 using vvi = vector <vi>; 546 547 const int N = 1 << 19; 548 549 int n; 550 int a[N], b[N], ta[N], tb[N]; 551 int c[N]; 552 553 int m, lm, all1; 554 555 signed main(){ 556 cin >> n; 557 ForE(i, 1, n){ 558 cin >> b[i]; 559 } 560 561 m = 1 << __lg(n); 562 if (m < n){ 563 m *= 2; 564 } 565 lm = __lg(m); 566 all1 = m - 1; 567 memset(ta, -1, sizeof(ta)); 568 memset(tb, -1, sizeof(tb)); 569 ForE(i, 1, n){ 570 tb[all1 ^ (i - 1)] = b[i]; 571 ta[n - i] = -2; 572 } 573 574 For(i, 0, m){ 575 c[all1 ^ i] = max(tb[i], 0); 576 } 577 For(bit, 0, lm){ 578 For(msk, 0, m){ 579 if (msk >> bit & 1){ 580 c[msk] ^= c[msk ^ (1 << bit)]; 581 } 582 } 583 } 584 For(i, 0, m){ 585 if (tb[i] == -1){ 586 c[all1 ^ i] = 0; 587 } 588 } 589 For(bit, 0, lm){ 590 For(msk, 0, m){ 591 if (msk >> bit & 1){ 592 c[msk] ^= c[msk ^ (1 << bit)]; 593 } 594 } 595 } 596 For(i, 0, m){ 597 if (tb[i] == -1){ 598 tb[i] = c[all1 ^ i]; 599 } 600 } 601 602 For(i, 0, m){ 603 ta[i] = tb[i]; 604 } 605 For(bit, 0, lm){ 606 For(msk, 0, m){ 607 if (msk >> bit & 1){ 608 ta[msk] ^= ta[msk ^ (1 << bit)]; 609 } 610 } 611 } 612 ForE(i, 1, n){ 613 a[i] = ta[n - i]; 614 } 615 ForE(i, 1, n){ 616 cout << a[i] << ' '; 617 } cout << endl; 618 } 619 ``` 620 621 **Feedback** 622 623 * Didn't solve 624 * Good problem 625 * Average problem 626 * Bad problem