1984.md (39522B)
1 Source: https://codeforces.com/blog/entry/130252 2 3 Thank you for participating! We put a lot of effort into this contest. Special thanks to [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") for contributing to these problems. 4 5 **Rating Predictions** 6 7 | Person | A | B | C1 | C2 | D | E | F | G | H | 8 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 9 | [null_awe](/profile/null_awe "Grandmaster null_awe") | 800 | 1000 | 1200 | 1700 | 2200 | 2400 | 2500 | 2900 | 3400 | 10 | [buffering](/profile/buffering "Expert buffering") | 800 | 1000 | 1300 | 1800 | 2300 | 2400 | 2600 | 3100 | 3500 | 11 | [redpanda](/profile/redpanda "Expert redpanda") | 800 | 1100 | 1200 | 1800 | | | | | | 12 | [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") | 800 | 1000 | 1200 | 1600 | 2200 | 2500 | 2500 | 3100 | 3400 | 13 | [bronze_coder](/profile/bronze_coder "Grandmaster bronze_coder") | 800 | 1000 | 1600 | 1800 | 2400 | | | 2700 | 3500 | 14 | [awesomeguy856](/profile/awesomeguy856 "Master awesomeguy856") | 800 | 1100 | 1300 | 1700 | 2200 | 2300 | 2600 | | | 15 | [flamestorm](/profile/flamestorm "Master flamestorm") | 800 | 1100 | 1200 | 1600 | 2200 | 2400 | 2500 | 3100 | 3200 | 16 | [Ste](/profile/Ste "Master Ste") | 800 | 1100 | 1000 | 1600 | 2000 | 2400 | 2400 | | | 17 18 | | A | B | C1 | C2 | D | E | F | G | H | 19 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 20 | Average | 800 | 1050 | 1250 | 1700 | 2214 | 2400 | 2516 | 2980 | 3400 | 21 | Actual | 800 | 1100 | 1300 | 1700 | 2000 | 2400 | 2500 | 3200 | 3300 | 22 23 Also, check out this video editorial for problems A through C2 by one of our testers! <https://www.youtube.com/watch?v=hS8Z3k57f6Q> 24 25 #### Solutions 26 27 ##### [1984A - Strange Splitting](/contest/1984/problem/A "Codeforces Global Round 26") 28 29 Problem Credits: [buffering](/profile/buffering "Expert buffering") 30 Analysis: [buffering](/profile/buffering "Expert buffering") 31 32 **Hint 1** 33 34 When is it impossible? 35 36 **Answer** 37 38 When $a = [x, x \dots x]$ for some $x$. 39 40 **Hint 2** 41 42 Only color one element red to make the range $0$. Which one do you pick to make the blue range different? 43 44 **Solution** 45 46 Read the hints. 47 48 It is impossible to color the array when all the elements are the same, because the range for the red and blue elements will always be $0$. 49 50 Otherwise, notice there will always be at least $2$ distinct values in the array. This means there is a way to get a positive range for the blue elements, by taking the maximum value and the minimum value and coloring them blue. This works because $n \geq 3$, so there is at least one element left. 51 52 Since we can get a positive range, we can then try to get the red elements to have a range of $0$, by coloring exactly one value red. So, we can color any $a_i$ for $2 \leq i \leq n - 1$ red since it will not affect the positive range we constructed for the blue elements. For simplicity sake, our solution chooses $i = 2$. Then, the remaining elements can be colored blue. 53 54 Therefore, our final solution is to check if it is impossible, or color $a_2$ red and the rest blue. 55 56 **Code (C++)** 57 58 ``` 59 #include <iostream> 60 using namespace std; 61 int main(){ 62 int T; cin >> T; 63 64 while (T--) { 65 66 int n; cin >> n; 67 68 vector<int> a(n); 69 for (int i = 0; i < n; i++) { 70 cin >> a[i]; 71 } 72 73 if (a[0] == a[n - 1]) { 74 cout << "NO" << "\n"; 75 } 76 else { 77 cout << "YES" << "\n"; 78 string s(n, 'R'); 79 s[1] = 'B'; 80 cout << s << "\n"; 81 82 } 83 84 85 } 86 } 87 ``` 88 89 ##### [1984B - Large Addition](/contest/1984/problem/B "Codeforces Global Round 26") 90 91 Problem Credits: [flamestorm](/profile/flamestorm "Master flamestorm") 92 Analysis: [null_awe](/profile/null_awe "Grandmaster null_awe") 93 94 Solution 1 95 96 **Hint 1** 97 98 What must the first (largest) digit be? 99 100 **Hint 2** 101 102 What must the other non-unit digits be? 103 104 **Hint 3** 105 106 What must the last digit be? 107 108 **Solution** 109 110 Because every digit is large, every two digits being added together will carry to the next digit. The two addends have the same length, so the sum must be one greater in length, with the largest digit equal to $1$. 111 112 For all other digits except for the units digit, we have the value to be the sum of two large digits, plus $1$ being carried over from the previous column. This makes the acceptable range of values be from $1$ to $9$, inclusive. 113 114 For the units digit, there is no previous column to carry over a $1$, so the acceptable range of values is from $0$ to $8$, inclusive. 115 116 **Code (C++)** 117 118 ``` 119 #include <iostream> 120 using namespace std; 121 122 #define ll long long 123 124 void solve() { 125 ll n; cin >> n; 126 n = n - n % 10 + (n % 10 + 1) % 10; 127 while (n > 9) { 128 if (n % 10 == 0) { 129 cout << "NO\n"; 130 return; 131 } 132 n /= 10; 133 } 134 cout << (n == 1 ? "YES\n" : "NO\n"); 135 } 136 137 int main() { 138 ios_base::sync_with_stdio(false); cin.tie(NULL); 139 int t; cin >> t; 140 for (int i = 0; i < t; ++i) solve(); 141 return 0; 142 } 143 ``` 144 145 ##### [1984C1 - Magnitude (Easy Version)](/contest/1984/problem/C1 "Codeforces Global Round 26") and [1984C2 - Magnitude (Hard Version)](/contest/1984/problem/C2 "Codeforces Global Round 26") 146 147 Problem Credits: [buffering](/profile/buffering "Expert buffering") 148 Analysis: [null_awe](/profile/null_awe "Grandmaster null_awe") 149 150 **Hint 1** 151 152 How many times do we need to pick option $2$? 153 154 **Hint 2** 155 156 We only need to pick it once. How can we calculate the final value for every position we can pick? 157 158 **Solution (Easy Version)** 159 160 We only need to pick option $2$ once. Why? Assume we picked option $2$ more than once, and consider the last two times it was picked. Both of these must occur when $c + a_i$ is negative, otherwise there is no reason to pick option $2$ over option $1$. Thus, if we chose option $1$ the first of these times instead of option $2$, that would cause the value of $c$ before the second operation to decrease. Because it was negative, this increases the magnitude, and thus it was more optimal to choose option $1$ for the first operation. 161 162 Because we only need to use option $2$ once, we can brute force where we use that operation and compute the final value of $c$ with prefix sums. 163 164 **Solution (Hard Version)** 165 166 Read the solution to the easy version first. 167 168 Let's think a bit more. Where do we actually end up using option $2$? We only use option $2$ when our prefix sum up to this point is minimum in the whole array. 169 170 Now, focus on each individual "important" use of option $2$ (where it actually makes a difference from option $1$), Let's say it is done at index $i$. Let's consider indices before. Since the operation at index $i$ is the only important option $2$, any option $2$'s we use before must not have been different from option $1$ (meaning that the value of $c + a_j$ has to be non-negative). Thus, we have the choice of using option $2$ or option $1$ at any index $j \lt i$ where the prefix sum is non-negative. Let's say there exists $x$ unique values of $j$. 171 172 Now, let's consider indices after. Since index $i$ is at a minimum prefix sum, that guarantees that all indices after will never have a lower value of $c$ than what $c$ is after doing the operation at index $i$. Thus, since we use option 2 at index $i$, we can use any of the two options moving forward. Thus, any index $j \gt i$ has two choices on which option to pick. Let's say there exists $y$ unique values of $j$. 173 174 The contribution of index $i$ to the answer is then $2^{x + y}$. 175 176 Special case: the prefix sum never becomes negative. What is the answer then? 177 178 **Code (C++)** 179 180 **Easy Version** 181 182 ``` 183 #include <iostream> 184 #include <vector> 185 #include <climits> 186 using namespace std; 187 188 #define ll long long 189 190 void solve() { 191 int n; cin >> n; 192 vector<int> arr(n); for (int i = 0; i < n; ++i) cin >> arr[i]; 193 ll sum = 0, mn = 0; 194 for (int i = 0; i < n; ++i) sum += arr[i], mn = min(mn, sum); 195 cout << sum - 2 * mn << '\n'; 196 } 197 198 int main() { 199 ios_base::sync_with_stdio(false); cin.tie(NULL); 200 int t; cin >> t; 201 for (int i = 0; i < t; ++i) solve(); 202 return 0; 203 } 204 ``` 205 206 **Hard Version** 207 208 ``` 209 #include <iostream> 210 #include <vector> 211 #include <climits> 212 using namespace std; 213 214 #define ll long long 215 216 const ll MAX_N = 400001; 217 const ll MOD = 998244353; 218 219 vector<ll> p2(MAX_N); 220 221 void solve() { 222 int n; cin >> n; 223 vector<int> arr(n); for (int i = 0; i < n; ++i) cin >> arr[i]; 224 ll sum = 0, mn = 0, ans = 0, abses = 0; 225 for (int i = 0; i < n; ++i) sum += arr[i], mn = min(mn, sum); 226 if (mn == 0) { 227 cout << p2[n] << '\n'; 228 return; 229 } 230 sum = 0; 231 for (int i = 0; i < n; ++i) { 232 sum += arr[i]; 233 if (sum == mn) { 234 ans = (ans + p2[n - i - 1 + abses]) % MOD; 235 } 236 if (sum >= 0) ++abses; 237 } 238 cout << ans << '\n'; 239 } 240 241 int main() { 242 ios_base::sync_with_stdio(false); cin.tie(NULL); 243 p2[0] = 1; 244 for (int i = 1; i < MAX_N; ++i) p2[i] = 2 * p2[i - 1] % MOD; 245 int t; cin >> t; 246 for (int i = 0; i < t; ++i) solve(); 247 return 0; 248 } 249 ``` 250 251 #### [1984D - ''a'' String Problem](/contest/1984/problem/D "Codeforces Global Round 26") 252 253 Problem Credits: [le0n](/profile/le0n "International Grandmaster le0n") 254 Analysis: [null_awe](/profile/null_awe "Grandmaster null_awe") 255 256 **Hint 1** 257 258 What does $t$ have to include? 259 260 **Solution** 261 262 Special case: the string consists of only "$\texttt{a}$", then answer is $n - 1$. 263 264 Otherwise, $t$ has to contain a character that is not "$\texttt{a}$". Let's consider one approach of counting. Let's force all $t$ to start with the first non-a character, and see how many work. 265 266 To see if one of these strings $t$ will work, we can start with $i = 0$. As long as $i$ does not point to the end of the string, we can find the next non-a character in $s$, and then see if the next $|t|$ characters in $s$ matches $t$. The last check mentioned can be done through hashing or using the Z-function. If it doesn't, this value of $t$ doesn't work. Otherwise, we update $i$ to the new current position and continue checking. 267 268 Now, if we find a string $t$ that does work, we need to count its contribution to the answer. We can just add $1$, but obviously not all working $t$ will start with a non-a character. Instead, we can find the minimum unused "$\texttt{a}$"s before all of the substrings equal to $t$ (call this $m$), and the current $t$ will be able to extend out up to $m$ "$\texttt{a}$"s at the beginning of the string. Thus, the contribution is $m + 1$ to the answer. 269 270 How fast is this? Because we are checking at most one string $t$ of each length, and the check itself can be made to take $O(\frac{n}{|t|})$, we have a total time complexity of $O(n\log{n})$ due to harmonic sums. 271 272 **Code (C++)** 273 274 ``` 275 #include <iostream> 276 #include <vector> 277 #include <climits> 278 #include <set> 279 using namespace std; 280 281 #define ll long long 282 283 vector<int> z_function(string s) { 284 int n = s.size(); 285 vector<int> z(n); 286 int l = 0, r = 0; 287 for(int i = 1; i < n; ++i) { 288 if (i < r) z[i] = min(r - i, z[i - l]); 289 while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i]; 290 if (i + z[i] > r) l = i, r = i + z[i]; 291 } 292 return z; 293 } 294 295 void solve() { 296 int n; // cin >> n; 297 string s; cin >> s; 298 n = s.length(); 299 vector<int> nona(n, n); 300 for (int i = n - 1; i >= 0; --i) { 301 if (s[i] != 'a') nona[i] = i; 302 else if (i + 1 < n) nona[i] = nona[i + 1]; 303 } 304 if (nona[0] == n) { 305 cout << n - 1 << '\n'; 306 return; 307 } 308 string s2 = ""; 309 int i1 = nona[0]; 310 for (int i = i1; i < n; ++i) s2 += s[i]; 311 vector<int> z = z_function(s2); 312 ll ans = 0; 313 for (int len = 1; i1 + len <= n; ++len) { 314 int cur = i1 + len; 315 int mn = i1; 316 bool works = true; 317 while (cur < n) { 318 if (nona[cur] == n) break; 319 int bt = nona[cur] - cur; 320 mn = min(mn, bt); 321 cur += bt; 322 if (z[cur - i1] < len) { 323 works = false; 324 break; 325 } 326 cur += len; 327 } 328 if (works) ans += mn + 1; 329 } 330 cout << ans << '\n'; 331 } 332 333 int main() { 334 int t; cin >> t; 335 for (int i = 0; i < t; ++i) solve(); 336 return 0; 337 } 338 ``` 339 340 #### [1984E - Shuffle](/contest/1984/problem/E "Codeforces Global Round 26") 341 342 Problem Credits: [null_awe](/profile/null_awe "Grandmaster null_awe"), thanks to [wavelets](/profile/wavelets "Grandmaster wavelets") for helping with brainstorming 343 Analysis: [null_awe](/profile/null_awe "Grandmaster null_awe") 344 345 **Solution** 346 347 Excluding the root, the maximum number of leaves we have is the maximum independent set (MIS) of the rest of the tree. Why? First of all, after rooting tree $T_2$, no two adjacent nodes can both be leaves. This is because, no matter which one you choose to add to $T_2$ first, it must be the ancestor of the other one. Thus, the first chosen node will not be a leaf. Furthermore, any chosen MIS of nodes can all become leaves. This is because we can essentially choose to add all of the nodes not in the MIS first to the tree, leaving all of the remaining nodes to be childless nodes, making them all leaves. 348 349 To find the answer, we want to find the maximum MIS of all subtrees that are missing one leaf. The answer will be one greater than this maximum MIS due to the root of $T_2$ being also a leaf. 350 351 There are multiple dynamic programming approaches to compute this efficiently, including rerooting and performing dynamic programming on tree edges. 352 353 Time complexity: $O(n)$ or $O(n \log{n})$, depending on implementation. 354 355 **Code (C++)** 356 357 ``` 358 #include <iostream> 359 #include <vector> 360 #include <map> 361 using namespace std; 362 363 #define pii pair<int, int> 364 365 int n; 366 vector<vector<int>> adj; 367 vector<pii> edges; 368 map<pii, int> mp; 369 370 vector<vector<int>> dp; 371 vector<vector<int>> from; 372 vector<int> miss; 373 374 void dfs(int e) { 375 if (dp[0][e] >= 0 || dp[1][e] >= 0) return; 376 int p = edges[e].first, v = edges[e].second; 377 dp[0][e] = 0, dp[1][e] = 1; 378 if (miss[v] < 0) { 379 for (int u : adj[v]) { 380 if (u == p) continue; 381 int ne = mp[{v, u}]; 382 dfs(ne); 383 from[0][v] += max(dp[1][ne], dp[0][ne]); 384 from[1][v] += dp[0][ne]; 385 } 386 miss[v] = p; 387 } 388 if (miss[v] != p && miss[v] != n) { 389 int ne = mp[{v, miss[v]}]; 390 dfs(ne); 391 from[0][v] += max(dp[1][ne], dp[0][ne]); 392 from[1][v] += dp[0][ne]; 393 miss[v] = n; 394 } 395 if (miss[v] == n) { 396 int nne = mp[{v, p}]; 397 dp[0][e] += from[0][v] - max(dp[1][nne], dp[0][nne]); 398 dp[1][e] += from[1][v] - dp[0][nne]; 399 } else if (miss[v] == p) { 400 dp[0][e] += from[0][v]; 401 dp[1][e] += from[1][v]; 402 } 403 } 404 405 void solve() { 406 cin >> n; 407 adj.clear(), edges.clear(); 408 adj.resize(n), edges.resize(2 * n - 2); 409 for (int i = 0; i < n - 1; ++i) { 410 int a, b; cin >> a >> b; --a, --b; 411 adj[a].push_back(b); 412 adj[b].push_back(a); 413 edges[2 * i] = {a, b}; 414 edges[2 * i + 1] = {b, a}; 415 mp[{a, b}] = 2 * i; 416 mp[{b, a}] = 2 * i + 1; 417 } 418 from = vector<vector<int>>(2, vector<int>(n)); 419 miss = vector<int>(n, -1); 420 dp = vector<vector<int>>(2, vector<int>(2 * n - 2, -1)); 421 for (int i = 0; i < 2 * n - 2; ++i) dfs(i); 422 int ans = 0; 423 for (int i = 0; i < n; ++i) { 424 if (adj[i].size() != 1) continue; 425 int e = mp[{i, adj[i][0]}]; 426 ans = max(ans, 1 + max(dp[0][e], dp[1][e])); 427 } 428 cout << ans << '\n'; 429 } 430 431 int main() { 432 ios_base::sync_with_stdio(false); cin.tie(NULL); 433 int t; cin >> t; 434 for (int i = 0; i < t; ++i) solve(); 435 return 0; 436 } 437 ``` 438 439 #### [1984F - Reconstruction](/contest/1984/problem/F "Codeforces Global Round 26") 440 441 Problem Credits: [buffering](/profile/buffering "Expert buffering") 442 Analysis: [buffering](/profile/buffering "Expert buffering") 443 444 **Hint 1** 445 446 Solve for no question marks in the string first. 447 448 **Hint 2** 449 450 Add a $0$ on both sides of $a$ and $b$, and add a $\texttt{P}$ before the start of the string and a $\texttt{S}$ after the string. Now you are guaranteed to have a $\texttt{PS}$ somewhere in the string. How does this help? 451 452 **Answer** 453 454 You know the sum of the array. 455 456 **Hint 3** 457 458 Look at adjacent elements in $b$, and its corresponding characters in the string, and see if you can determine anything about $a$. 459 460 **Hint 4** 461 462 Go back to the original problem, with question marks. We do not know the sum now, but how many possible ones can there be? 463 464 **Solution** 465 466 How to solve with no question marks? 467 468 To simplify things, let's extend all arrays both ways by 1 element. In array $a$ and $b$, we can keep both values at $0$, and in the string $s$, we can assign the left value to "$\texttt{P}$" and the right value to "$\texttt{S}$" (the other values will still be satisfied -- why?) 469 470 Now, somewhere within the string, we are guaranteed to see the combination "$\texttt{PS}$" because we now have a string that starts with "$\texttt{P}$" and ends with "$\texttt{S}$", therefore it must transition somewhere in between. 471 472 Notice, if we add the values in $b$ of the "$\texttt{PS}$", we can gather the sum of the array. 473 474 Now, solving becomes simpler. We can focus on adjacent elements in the array. Say we are currently examining indices $i$ and $i + 1$. There are four cases: 475 476 1. We are currently at a "$\texttt{PP}$". We then know $b_i + a_{i+1} = b_{i+1}$, so $a_{i+1}$ is now known. 477 2. We are currently at a "$\texttt{PS}$". Again, this must be the sum. All we have to do here is check that our sum is correct. 478 3. We are currently at an "$\texttt{SP}$". Here, we have $b_{i} + b_{i+1} - SUM = a_i + a_{i+1}$ (why?). Our left side is known, and the only requirement on the right side is that both $a_i$ and $a_{i+1}$ have to have a magnitude of at most $m$. Thus, to make their maximum magnitude as small as possible, we make them as close as possible to each other. If the left side is $x$, we assign $a_i = \text{floor}(x / 2)$, and $a_{i+1} = x - a_i$. 479 4. We are currently at an "$\texttt{SS}$". This is similar to the first case, as we know that $b_i = a_i + b_{i+1}$. Thus, $a[i]$ will be known. 480 481 If $a_i$ is always possible, then we know our answer exists. 482 483 Thus, this solves a version without question marks. For the version with question marks, we can only try to guess what the sum of the entire array is, since we don't know where "$\texttt{PS}$" might be for sure every time. There are only $n$ possibilities — the sum of every pair of adjacent numbers in $b$. 484 485 For every possibility, we can run a `dp[i][j]` where we are currently at index $i$ and the last character within "$\texttt{P}$" and "$\texttt{S}$" in string $s$ used was $j$. This dynamic programming will run in linear time because of constant-time transitions and linear amount of states. Note that this is only possible due to the independent nature of adjacent pairs as described earlier. 486 487 With this DP, we can calculate how many paths are possible, adding to our answer. 488 489 Time complexity $O(n^2)$ 490 491 **Code (C++)** 492 493 ``` 494 #include <iostream> 495 #include <vector> 496 #include <cstring> 497 #include <assert.h> 498 #include <set> 499 using namespace std; 500 501 #define ll long long 502 503 const int INF = 998244353; 504 // const int BOUND = 1e9; 505 506 void solve() { 507 int n; cin >> n; 508 int BOUND; cin >> BOUND; 509 string s; cin >> s; 510 s = "P" + s + "S"; 511 vector<ll> b(n + 2); 512 for (int i = 0; i < n; ++i) cin >> b[i + 1]; 513 ll ans = 0; 514 set<ll> done; 515 for (int i = 0; i < n + 1; ++i) { 516 ll sum = b[i] + b[i + 1]; 517 if (done.count(sum)) continue; 518 int dp[n + 2][2]; 519 for (int j = 0; j < n + 2; ++j) for (int k = 0; k < 2; ++k) dp[j][k] = -1; 520 // ["P", "S"] 521 dp[0][0] = 1; 522 for (int j = 1; j < n + 2; ++j) { 523 bool tr[2]; tr[0] = tr[1] = true; 524 if (s[j] == 'P') tr[1] = false; 525 else if (s[j] == 'S') tr[0] = false; 526 if (abs(b[j] - b[j - 1]) <= BOUND) { 527 for (int k = 0; k < 2; ++k) 528 if (dp[j - 1][k] > -1 && tr[k]) dp[j][k] = dp[j - 1][k]; 529 } 530 if (dp[j - 1][0] > -1 && tr[1] && sum == b[j] + b[j - 1]) { 531 // "P" -> "S": 532 if (dp[j][1] < 0) dp[j][1] = 0; 533 dp[j][1] = (dp[j][1] + dp[j - 1][0]) % INF; 534 } 535 if (dp[j - 1][1] > -1 && tr[0]) { 536 // "S" -> "P": 537 ll add = b[j] + b[j - 1] - sum; 538 ll large = max(abs(add / 2), abs(add - add / 2)); 539 if (large <= BOUND) { 540 if (dp[j][0] < 0) dp[j][0] = 0; 541 dp[j][0] = (dp[j][0] + dp[j - 1][1]) % INF; 542 } 543 } 544 } 545 if (dp[n + 1][1] < 0) continue; 546 ans = (ans + dp[n + 1][1]) % INF; 547 done.insert(sum); 548 } 549 cout << ans << '\n'; 550 } 551 552 int main() { 553 ios::sync_with_stdio(false); cin.tie(NULL); 554 int t; cin >> t; 555 for (int i = 0; i < t; ++i) solve(); 556 return 0; 557 } 558 ``` 559 560 #### [1984G - Magic Trick II](/contest/1984/problem/G "Codeforces Global Round 26") 561 562 Problem Credits: [null_awe](/profile/null_awe "Grandmaster null_awe") 563 Analysis: [null_awe](/profile/null_awe "Grandmaster null_awe") 564 565 **Hint 1** 566 567 Solve what the maximum $k$ will be for different types of arrays. 568 569 **Hint 2** 570 571 The maximum is always close to $n$. 572 573 **Solution** 574 575 There exists two trivial cases. If array is already sorted, $k = n$. If array is cyclic shift of sorted array, $k = n - 1$. Now, $k = n - 2$ and $k = n - 3$ is sufficient to sort any array. 576 577 Let's assume $n$ is odd first, and construct an answer in the general case with $k = n - 2$. Because $k$ is so large, our operations are limited in choices. If we represent the array as a cyclic array with a divider representing the end of the array, an operation can be seen as two choices: 578 579 1. Move the divider $2$ positions in any direction. 580 2. Swap the two numbers around the divider, then move the divider by $1$ position in any direction. 581 582 With this representation, the construction becomes quite easy. Because $n$ is odd, we can use the first type of operation to put the divider wherever we want. Then, using the second type of operation, if our divider is on the right side of a specific number, we can move it all the way to the right by swapping, then moving the divider right by $1$ position. 583 584 Because we are able to do this, we can bubble sort. For each number, position the divider in $O(n)$ moves, then move it to the very right in another $O(n)$ moves. There are $n$ numbers total, so this takes a total of around $2n^2$ operations, less if optimized. 585 586 What if $n$ is even? In this case $k = n - 2$ is not always guaranteed to work. The motivation for seeing this can come from the fact that you can't place the divider anywhere just by using type $1$ operations. 587 588 As a lower bound, we know that $k = n - 3$ will always work. We can use operations to move the largest number to the very end, then we basically have an array of length $n - 1$ with $k = n - 3$, which is the odd case we presented earlier. 589 590 So, when can we use $k = n - 2$ in the even case? Let's consider the number of inversions in the array at any given time. If $n$ is even, then $k = n - 2$ is also even, meaning that the parity of the number of inversions will never change with operations. Thus, since a sorted array will have no inversions, we cannot use $k = n - 2$ if the initial array had an odd number of inversions. 591 592 If we have an even number of inversions, we can sort in a similar manner. Except, now, if the inversion constraint prevents moving the divider to the immediate right of our current number with only type $1$ operations, we can use a few type $2$ operations to fix the position of the divider (many possible strategies for this, one possible way is shown in the implementation). Overall, this should also take around $2n^2$ operations total. 593 594 **Code (C++)** 595 596 ``` 597 #include <iostream> 598 #include <vector> 599 using namespace std; 600 601 #define pii pair<int, int> 602 603 bool sorted(vector<int> arr, int n) { 604 for (int i = 1; i < n; ++i) if (arr[i] < arr[i - 1]) return false; 605 return true; 606 } 607 608 bool cyclic(vector<int> arr, int n) { 609 for (int i = 1; i < n; ++i) if (arr[i] % n != (arr[i - 1] + 1) % n) return false; 610 return true; 611 } 612 613 void solve() { 614 int n; cin >> n; 615 vector<int> arr(n); for (int i = 0; i < n; ++i) cin >> arr[i]; 616 if (sorted(arr, n)) { 617 cout << n << "\n0\n"; 618 return; 619 } 620 if (cyclic(arr, n)) { 621 cout << n - 1 << '\n'; 622 int pos; 623 for (pos = 0; pos < n; ++pos) if (arr[pos] == 1) break; 624 cout << pos << '\n'; 625 for (int i = 0; i < pos; ++i) { 626 cout << "2 1\n"; 627 } 628 return; 629 } 630 vector<pii> ops; 631 if (n % 2 == 0) { 632 int inv = 0; 633 for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) if (arr[i] > arr[j]) ++inv; 634 if (inv & 1) { 635 int pos; 636 for (pos = 0; pos < n; ++pos) if (arr[pos] == n) break; 637 if (pos < 3) { 638 for (int i = 0; i <= pos; ++i) ops.push_back({2, 1}); 639 vector<int> tmp = arr; 640 for (int i = 0; i < n - 2; ++i) arr[i] = tmp[(i + pos + 1) % (n - 2)]; 641 } 642 for (pos = 0; pos < n; ++pos) if (arr[pos] == n) break; 643 for (int i = pos; i < n - 1; ++i) ops.push_back({3, 4}); 644 vector<int> tmp = arr; 645 for (int i = 2; i < n; ++i) arr[i] = tmp[((i + pos - 3) % (n - 2)) + 2]; 646 --n; 647 } 648 } 649 cout << n - 2 << '\n'; 650 int div = 0; 651 for (int i = n; i > 0; --i) { 652 int pos; 653 for (pos = 0; pos < n; ++pos) if (arr[pos] == i) break; 654 pos += 1; 655 if (pos == i) continue; 656 if (div % 2 != pos % 2) { 657 if (n & 1) { 658 while (div < n) { 659 ops.push_back({3, 1}); 660 div += 2; 661 } 662 div %= n; 663 } else { 664 while (div != pos - 1) { 665 if (div < pos - 1) { 666 ops.push_back({3, 1}); 667 div += 2; 668 } else { 669 ops.push_back({1, 3}); 670 div -= 2; 671 } 672 } 673 if (pos > 1) { 674 ops.push_back({2, 3}); 675 swap(arr[(div + n - 1) % n], arr[div]); 676 div = (div + n - 1) % n; 677 --pos; 678 } 679 ops.push_back({3, 1}); 680 div += 2; 681 ops.push_back({2, 3}); 682 swap(arr[(div + n - 1) % n], arr[div]); 683 div = (div + n - 1) % n; 684 } 685 } 686 while (div != pos) { 687 if (div < pos) { 688 ops.push_back({3, 1}); 689 div += 2; 690 } else { 691 ops.push_back({1, 3}); 692 div -= 2; 693 } 694 } 695 for (int j = pos; j < i; ++j) { 696 ops.push_back({2, 1}); 697 swap(arr[div - 1], arr[div]); 698 ++div; 699 } 700 } 701 if (div % 2 == 1) { 702 while (div < n) { 703 ops.push_back({3, 1}); 704 div += 2; 705 } 706 div %= n; 707 } 708 while (div > 0) { 709 ops.push_back({1, 3}); 710 div -= 2; 711 } 712 cout << ops.size() << '\n'; 713 for (pii p : ops) { 714 cout << p.first << ' ' << p.second << '\n'; 715 } 716 } 717 718 int main() { 719 ios_base::sync_with_stdio(false); cin.tie(NULL); 720 int t; cin >> t; 721 for (int i = 0; i < t; ++i) solve(); 722 return 0; 723 } 724 ``` 725 726 #### [1984H - Tower Capturing](/contest/1984/problem/H "Codeforces Global Round 26") 727 728 Problem Credits: [flamestorm](/profile/flamestorm "Master flamestorm") 729 Analysis: [flamestorm](/profile/flamestorm "Master flamestorm") 730 731 **Hint 1** 732 733 Are there any useless points? 734 735 **Hint 2** 736 737 Draw all triangles that contain all points inside their circumcircle. What do you notice? 738 739 **Solution** 740 741 **Claim.** We can't ever pick a tower inside the convex hull. 742 743 **Proof.** A circle can only contain all the points if the points on the circle are on the convex hull; otherwise, the circle will necessarily split the convex hull into two parts, one of which is outside. 744 745 It follows that if our initial two towers aren't on the convex hull, the answer is $0$. Also, we can safely ignore all points in the convex hull, since we'll capture them anyway, as the convex hull is the union of all triangles whose vertices are vertices of the convex hull. From now on we'll only consider points on the convex hull. 746 747 Now comes the key claim of the problem. 748 749 **Claim.** Call a triangle *covering* if its circumcircle contains all the points. Draw all covering triangles. We claim that these triangles form a triangulation of the convex hull. 750 751 **Proof.** Recall that a triangulation is a set of triangles with pairwise non-intersecting interiors whose union is the polygon. There are two parts to the proof: 752 753 1. the triangles are pairwise non-intersecting. 754 2. their union is the polygon. 755 756 Let's prove them separately. 757 758 First we'll prove point (1) directly. 759 760 Consider two circles through points $ABC$ and $DEF$. Of course, the convex hull needs to lie in the intersection of the two circles. In particular, the circle through $ABC$ must contain the points $DEF$, while the circle through $DEF$ must contain the points $ABC$. It follows that the two circumcircles (say, $\Omega$ and $\Psi$ respectively) have the following property: 761 762 * the points $A$, $B$, $C$ lie on an arc of $\Omega$ inside $\Psi$, and 763 * the points $D$, $E$, $F$ lie on an arc of $\Psi$ inside $\Omega$. 764 765 The claim follows. Formally, we can define $U$ and $V$ as the intersection points of $\Omega$ and $\Psi$. Then if we walk along the digon $UV$ (whose edges are arcs of $\Omega$ and $\Psi$), we will pass through $A$, $B$, $C$ along one of the arcs, and $D$, $E$, $F$ on the other. This means that there is some closed convex loop passing through the points $A$, $B$, $C$ before $D$, $E$, $F$, implying those two triangles don't intersect. The proof remains the same even if some of $A$, $B$, $C$, $D$, $E$, $F$ overlap. 766 767 Now we'll move on to the proof of (2). Consider any covering triangle $ABC$. WLOG suppose $AB$ is not an edge of the convex hull. Consider the points in the halfplane of $AB$ not containing $C$, and let $C'$ be the point among these such that $\angle AC'B$ is minimized. Then it follows that $ABC'$ is also covering. It's easy to see why this works and why $C'$ is unique by the inscribed angle theorem. 768 769 As a result, given any covering triangle, we can recursively triangulate the regions it cuts off by a chord. Thus, inductively, the whole polygon will be triangulated. We are done with the proof. 770 771 Note that this implies our original three towers in the problem must form a covering triangle, since we create a covering triangle after every operation; thus, at the end of these operations, all but possibly one of these triangles is covering (the "possibly one" is the initial triangle). But such a covering triangulation exists and is unique, as shown, so our initial triangle in fact must be covering. 772 773 Now on to the actual operations present in the problem. Using them, we can "construct" the triangulation one step at a time using operations like the one mentioned. Of course, the triangulation is unique, so the only change we can do is the order in which we construct the triangles. 774 775 Consider the dual tree of the triangulation (that is, make a vertex for each triangle and an edge between those vertices corresponding to two triangles that share a diagonal of the convex hull). In an operation, we attach a leaf to any vertex, and in the end we end up with the final dual tree. Note that we can start growing the tree at either triangle adjacent to our original diagonal; that is, if our original points are $A$ and $B$, then we need to consider rooting our tree at either $T_1$ or $T_2$, where those are the two triangles that contain the edge $AB$ (note that $T_2$ may not exist). 776 777 Let's reverse time. Then given the final tree (rooted at either $T_1$ or $T_2$), in an operation we prune a leaf (a leaf here is a vertex with no children). How many ways can we prune all the leaves? 778 779 This is a standard dynamic programming problem, since at each step we need to prune all of our children before we prune ourselves. In particular, if the sizes of our childrens' subtrees are $s_1, \dots, s_k$, then our answer is $\binom{s_1 + \dots + s_k}{s_1, \dots, s_k} \cdot \prod_{i=1}^{k} \mathrm{ans}(\mathrm{child}_i)$. This DP runs in $\mathcal{O}(n)$ time, so it is not a problem to compute. 780 781 We can easily compute the triangulation in $\mathcal{O}(n^2)$ time as follows: given an edge $PQ$, we need to find the point $R$ in a halfplane such that $(PQR)$ covers all points, and as mentioned before, by the inscribed angle theorem this is precisely the point $R$ such that $PQR'$ is minimized. So you can find it with an $\mathcal{O}(n)$ sweep and add the new edges to our triangulation. 782 783 Therefore the solution runs in $\mathcal{O}(n^2)$, but the validator takes $\mathcal{O}(n^3)$ to check. We accepted slower solutions in $\mathcal{O}(n^3)$ as well, and even $\mathcal{O}(n^4)$ with a decent constant factor (which are relatively hard to cut). 784 785 A note about implementation: I'm not very good at it, so my code below is a bit messy. Also, to keep the computations in integers, I needed to use big integers at exactly one point, but it's not so bad: you only need to implement big integer multiplication and comparison, which I shamelessly stole from [jeroenodb](/profile/jeroenodb "International Grandmaster jeroenodb"). You may not need to use it, and can pass using floating-point numbers. 786 787 **Code (C++)** 788 789 ``` 790 #include <bits/stdc++.h> 791 792 using namespace std; 793 794 const int MAX = 200007; 795 const int MOD = 998244353; 796 797 struct bignum { 798 static constexpr long long B = 1LL<<30; 799 static constexpr int N = 6; 800 array<long long, N> b = {}; 801 bignum() {} 802 bignum(long long a) { 803 b[2] = (a / B) / B; 804 b[1] = (a / B) % B; 805 b[0] = a % B; 806 } 807 bignum operator*(const bignum& o) { 808 bignum res; 809 for (int i = 0; i < N; i++) { 810 for (int j = 0; j + i < N; j++) { 811 res.b[i + j] += b[i] * o.b[j]; 812 for (int k = i + j; k + 1 < N; k++) { 813 auto tmp = res.b[k] / B; 814 res.b[k + 1] += tmp; 815 res.b[k] -= tmp * B; 816 } 817 } 818 } 819 return res; 820 } 821 bool operator<=(const bignum& o) const { 822 if (b == o.b) return true; 823 return lexicographical_compare(b.rbegin(),b.rend(),o.b.rbegin(),o.b.rend()); 824 } 825 }; 826 827 template <class T> int sgn(T x) { return (x > 0) - (x < 0); } 828 template<class T> 829 struct Point { 830 typedef Point P; 831 T x, y; 832 explicit Point(T x=0, T y=0) : x(x), y(y) {} 833 bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); } 834 bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); } 835 P operator+(P p) const { return P(x+p.x, y+p.y); } 836 P operator-(P p) const { return P(x-p.x, y-p.y); } 837 P operator*(T d) const { return P(x*d, y*d); } 838 P operator/(T d) const { return P(x/d, y/d); } 839 T dot(P p) const { return x*p.x + y*p.y; } 840 T cross(P p) const { return x*p.y - y*p.x; } 841 T cross(P a, P b) const { return (a-*this).cross(b-*this); } 842 T dist2() const { return x*x + y*y; } 843 double dist() const { return sqrt((double)dist2()); } 844 // angle to x-axis in interval [-pi, pi] 845 double angle() const { return atan2(y, x); } 846 P unit() const { return *this/dist(); } // makes dist()=1 847 P perp() const { return P(-y, x); } // rotates +90 degrees 848 P normal() const { return perp().unit(); } 849 // returns point rotated 'a' radians ccw around the origin 850 P rotate(double a) const { 851 return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); } 852 friend ostream& operator<<(ostream& os, P p) { 853 return os << "(" << p.x << "," << p.y << ")"; } 854 friend istream& operator>>(istream& is, P& p) { 855 return is >> p.x >> p.y; } 856 }; 857 858 typedef Point<long long> P; 859 vector<P> convexHull(vector<P> pts) { 860 if (pts.size() <= 1) return pts; 861 sort(pts.begin(), pts.end()); 862 vector<P> h(pts.size()+1); 863 int s = 0, t = 0; 864 for (int it = 2; it--; s = --t, reverse(pts.begin(), pts.end())) 865 for (P p : pts) { 866 while (t >= s + 2 && h[t-2].cross(h[t-1], p) <= 0) t--; 867 h[t++] = p; 868 } 869 return {h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])}; 870 } 871 872 int n, t; 873 long long inv[MAX], fact[MAX], invfact[MAX]; 874 vector<P> v; 875 876 void orient(P &a, P &b, P &c) { 877 // move points a, b, c to be in counterclockwise order 878 long long val = (b - a).cross(c - a); 879 assert(val != 0); 880 if (val < 0) {swap(a, c);} 881 } 882 883 pair<long long, long long> angleComp(P a, P b, P c) { 884 // get a (scaled) value of f(cos(angle ABC)) 885 P ab = a - b, cb = c - b; 886 long long dt = ab.dot(cb); 887 dt *= dt; 888 int sgn = (ab.dist2() + cb.dist2() >= (a - c).dist2() ? 1 : -1); 889 return make_pair(sgn * dt, ab.dist2() * cb.dist2()); 890 } 891 892 bool inCircle(P a, P b, P c, P d) { 893 // is D in (or on) (ABC)? 894 orient(a, b, c); 895 P ad = a - d, bd = b - d, cd = c - d; 896 return ( 897 ad.dist2() * (bd.x * cd.y - bd.y * cd.x) - 898 bd.dist2() * (ad.x * cd.y - ad.y * cd.x) + 899 cd.dist2() * (ad.x * bd.y - ad.y * bd.x) 900 ) >= 0; 901 } 902 903 pair<bool, int> check(int l, int r) { 904 int start = l, finish = r; 905 if (finish < start) {finish += n;} 906 pair<long long, long long> best = make_pair(-MOD, 1); 907 int w = -1; 908 for (int i = start + 1; i < finish; i++) { 909 pair<long long, long long> val = angleComp(v[l], v[i % n], v[r]); 910 bignum v1 = bignum(val.first) * bignum(best.second); 911 bignum v2 = bignum(val.second) * bignum(best.first); 912 if (!(v1 <= v2)) { 913 best = val; 914 w = i % n; 915 } 916 } 917 if (w == -1) { 918 // cout << v[l] << ' ' << v[r] << " empty?\n"; 919 return make_pair(true, -1); 920 } 921 // cout << v[l] << ' ' << v[r] << " connects to " << v[w] << "?\n"; 922 for (P Q : v) { 923 if (!inCircle(v[l], v[w], v[r], Q)) {return make_pair(false, -1);} 924 } 925 return make_pair(true, w); 926 } 927 928 void reset(int n) { 929 v.clear(); 930 // for (int i = 0; i < n + 5; i++) { 931 // g[i].clear(); 932 // child[i].clear(); 933 // } 934 t = 1; 935 } 936 937 void solve() { 938 cin >> n; 939 reset(n); 940 vector<P> pts(n); 941 for (int i = 0; i < n; i++) { 942 cin >> pts[i]; 943 } 944 vector<P> us{pts[0], pts[1]}; 945 vector<int> us_vals; 946 v = convexHull(pts); 947 n = v.size(); 948 for (auto P : us) { 949 int i = 0; bool hit = false; 950 for (auto Q : v) { 951 if (P == Q) {us_vals.push_back(i); hit = true;} 952 i++; 953 } 954 if (!hit) {cout << 0 << '\n'; return;} 955 } 956 if (v.size() <= 3) {cout << 1 << '\n'; return;} 957 queue<pair<pair<int, int>, int>> q; 958 vector<int> child[MAX]; 959 q.push(make_pair(make_pair(us_vals[0], us_vals[1]), -1)); 960 q.push(make_pair(make_pair(us_vals[1], us_vals[0]), -1)); 961 while (!q.empty()) { 962 auto p = q.front(); 963 q.pop(); 964 pair<bool, int> resp = check(p.first.first, p.first.second); 965 if (!resp.first) {cout << 0 << '\n'; return;} 966 if (resp.second == -1) {continue;} 967 q.push(make_pair(make_pair(p.first.first, resp.second), t)); 968 q.push(make_pair(make_pair(resp.second, p.first.second), t)); 969 if (p.second != -1) { 970 child[p.second].push_back(t); 971 } 972 t++; 973 } 974 // for (int i = 1; i <= n - 2; i++) { 975 // cout << i << ": "; 976 // for (int j : child[i]) {cout << j << ' ';} 977 // cout << '\n'; 978 // } 979 bool edge_case = true; // both 1 and 2 are roots 980 for (int j : child[1]) { 981 if (j == 2) {edge_case = false;} // only 1 is root 982 } 983 984 vector<long long> dp(n + 7); 985 vector<int> sz(n + 7); 986 987 auto cnt = [&](auto self, int v) -> int { 988 if (sz[v] != -1) {return sz[v];} 989 int res = 1; 990 if (!child[v].empty()) { 991 for (int u : child[v]) { 992 res += self(self, u); 993 } 994 } 995 sz[v] = res; 996 return res; 997 }; 998 999 auto f = [&](auto self, int v) -> long long { 1000 if (dp[v] != -1LL) {return dp[v];} 1001 long long res = 1LL; 1002 if (!child[v].empty()) { 1003 res = (res * fact[cnt(cnt, v) - 1]) % MOD; 1004 for (int u : child[v]) { 1005 res = (res * self(self, u)) % MOD; 1006 res = (res * invfact[cnt(cnt, u)]) % MOD; 1007 } 1008 } 1009 dp[v] = res; 1010 return res; 1011 }; 1012 1013 if (edge_case) {child[1].push_back(2);} 1014 1015 fill(dp.begin(), dp.end(), -1LL); 1016 fill(sz.begin(), sz.end(), -1); 1017 long long res = f(f, 1); 1018 1019 if (edge_case) { 1020 child[1].erase(remove(child[1].begin(), child[1].end(), 2), child[1].end()); 1021 child[2].push_back(1); 1022 fill(dp.begin(), dp.end(), -1LL); 1023 fill(sz.begin(), sz.end(), -1); 1024 res = (res + f(f, 2)) % MOD; 1025 } 1026 1027 cout << res << '\n'; 1028 } 1029 1030 int main() { 1031 ios::sync_with_stdio(false); 1032 cin.tie(nullptr); 1033 inv[0] = inv[1] = 1; 1034 for (int i = 2; i < MAX; i++) { 1035 inv[i] = MOD - (long long)(MOD / i) * inv[MOD % i] % MOD; 1036 } 1037 fact[0] = fact[1] = 1; invfact[0] = invfact[1] = 1; 1038 for (int i = 2; i < MAX; i++) { 1039 fact[i] = (fact[i - 1] * (long long)i) % MOD; 1040 invfact[i] = (invfact[i - 1] * inv[i]) % MOD; 1041 } 1042 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 1043 // solve(); 1044 } 1045 ```