2191.md (64838B)
1 Source: https://codeforces.com/blog/entry/150256 2 3 Special thanks to [reirugan](/profile/reirugan "Master reirugan"), [weirdflexbutok](/profile/weirdflexbutok "Master weirdflexbutok") and [Intellegent](/profile/Intellegent "Grandmaster Intellegent") for helping with editorials. 4 5 [2191A - Array Coloring](/contest/2191/problem/A "Codeforces Round 1073 (Div. 2)") 6 7 * Idea: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 8 * Solution: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 9 * Editorial: [reirugan](/profile/reirugan "Master reirugan") 10 11 **Hints** 12 13 **Hint 1** 14 15 Without the "after sorting condition", there are only two ways to color the cards. 16 17 **Solution** 18 19 Without the "after sorting condition", there are only two ways to color the cards. We must have that $a$ is alternating in color. 20 21 Without loss of generality, color the odd indices red and the even indices blue. This uniquely colors every card. Now, let's sort the array $a$, while also keeping track of the colors; one way to do this is by sorting it as a vector of pairs. Then we simply have to verify that no two adjacent cards are the same color. 22 23 Alternatively, you can use the fact that $a$ is a permutation, so all differences of $a_i - i$ have to either be odd or even. 24 25 **Code** 26 27 ``` 28 #include <bits/stdc++.h> 29 30 using namespace std; 31 32 void solve() { 33 int n; 34 cin >> n; 35 vector<int> a(n); 36 for(auto &i : a) { 37 cin >> i; 38 } 39 40 int cnt = 0; 41 for(int i = 0; i < n; i++) { 42 cnt += (a[i] % 2 != (i + 1) % 2); 43 } 44 45 cout << (cnt == 0 || cnt == n? "YES" : "NO") << '\n'; 46 } 47 48 signed main() { 49 ios_base::sync_with_stdio(0); cin.tie(0); 50 int ttt = 1; 51 cin >> ttt; 52 while(ttt--) { 53 solve(); 54 } 55 } 56 ``` 57 58 **Rate The Problem!** 59 60 * Good Problem 61 * Okay Problem 62 * Bad Problem 63 * Didn't Solve 64 65 [2191B - MEX Reordering](/contest/2191/problem/B "Codeforces Round 1073 (Div. 2)") 66 67 * Idea: [satyam343](/profile/satyam343 "Expert satyam343") 68 * Solution: [satyam343](/profile/satyam343 "Expert satyam343") 69 * Editorial: [reirugan](/profile/reirugan "Master reirugan") 70 71 **Hints** 72 73 **Hint 1** 74 75 If there are no zeros in $a$, it's impossible. If there's exactly one zero, it's always possible. 76 77 **Hint 2** 78 79 If there are at least $2$ zeros and no ones, there's a split point between the two zeros. 80 81 **Hint 3** 82 83 If there are at least $2$ zeros and a one, you can put all zeros at the end. 84 85 **Solution** 86 87 Notice that $f(l, r) \gt 0$ if and only if $a[l, r]$ contains a zero. Therefore, if $a$ does not contain any zeros, the answer is $\texttt{NO}$, because all values of $f(l, r)$ are zero, so they are all equal. 88 89 Conversely, consider the case where there is exactly one zero. Then we can simply place this zero at the very end. Now, for any $1 \leq i \leq n-1$, we have that $f(1, i) = 0$, but $f(i+1, n) \neq 0$, so the answer is $\texttt{YES}$. 90 91 Finally, consider the case where there are at least two zeros. If $a$ does not contain any ones, then the answer is $\texttt{NO}$. This is because we can always choose an $i$ that splits the zeros — that is, $a[1, i]$ and $a[i+1, n]$ both contain a zero — then we will have that $f(1, i) = f(i+1, n) = 1$. 92 93 Otherwise, if $a$ does contain a one, then we can place all of the zeros at the very end. Now, consider any $1 \leq i \leq n-1$. If $a[1, i]$ does not contain a zero, then $f(1, i) = 0$, but $f(i+1, n) \neq 0$. If $a[1, i]$ does contain a zero, then it also contains a one (because all ones are before all zeros), so $f(1, i) \geq 2$. But $a[i+1, n]$ consists of only zeros, so $f(i+1, n) = 1$. Therefore, the answer is $\texttt{YES}$. 94 95 **Code** 96 97 ``` 98 #include <bits/stdc++.h> 99 100 using namespace std; 101 102 void solve() { 103 int n; 104 cin >> n; 105 vector<int> a(n); 106 for(auto &i : a) { 107 cin >> i; 108 } 109 110 vector<int> cnt(n + 1); 111 for(auto i : a) cnt[i]++; 112 113 if(cnt[0] == 0) cout << "NO\n"; 114 else if(cnt[1] > 0) cout << "YES\n"; 115 else cout << (cnt[0] == 1? "YES" : "NO") << '\n'; 116 } 117 118 signed main() { 119 ios_base::sync_with_stdio(0); cin.tie(0); 120 int ttt = 1; 121 cin >> ttt; 122 while(ttt--) { 123 solve(); 124 } 125 } 126 ``` 127 128 **Rate The Problem!** 129 130 * Good Problem 131 * Okay Problem 132 * Bad Problem 133 * Didn't Solve 134 135 [2190A - Sorting Game](/contest/2190/problem/A "Codeforces Round 1073 (Div. 1)") 136 137 * Idea: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 138 * Solution: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 139 * Editorial: [reirugan](/profile/reirugan "Master reirugan") 140 141 **Hints** 142 143 **Hint 1** 144 145 Let $t$ be the sorted version of $s$. Then if $s = t$ at any point, the player to move loses, because there is no legal move remaining. 146 147 **Hint 2** 148 149 It's possible to sort in one move. 150 151 **Solution** 152 153 Let $t$ be the sorted version of $s$. Then if $s = t$ at any point, the player to move loses, because there is no legal move remaining. 154 155 If $s = t$ at the start of the game, the answer is $\texttt{Bob}$. Otherwise, we claim the answer is $\texttt{Alice}$, and she can win on the first turn by choosing all of the indices at which $s$ and $t$ differ. 156 157 First, we claim this is non-increasing. Let $i$ be the number of zeros in $s$, so $t[1, i]$ consists of only zeros, and $t[i+1, n]$ consists of only ones. Then for any $j$ between $1$ and $i$, if $s_j$ and $t_j$ differ then $s_j = 1$. Similarly, for any $j$ between $i+1$ and $n$, if $s_j$ and $t_j$ differ then $s_j = 0$. So out of the chosen indices, the indices between $1$ and $i$ satisfy $s_j = 1$, and the indices between $i+1$ and $n$ satisfy $s_j = 0$, so the sequence is non-increasing. 158 159 Next, we claim that this sorts the array; in particular, this implies that it changes the array, so it is legal. Furthermore, this wins immediately since Bob has no subsequent move. Indeed, we see that the number of chosen indices between $1$ and $i$ is equal to the number of chosen indices between $i+1$ and $n$, because we must have that the number of zeros and ones in $s$ and $t$ are equal. So the operation simply exchanges all of the ones in $s[1, i]$ with all of the zeros in $s[i+1, n]$, thus making $s = t$ as desired. 160 161 **Code** 162 163 ``` 164 #include <bits/stdc++.h> 165 166 using namespace std; 167 168 void solve() { 169 int n; 170 cin >> n; 171 string s; 172 cin >> s; 173 174 string sorted = s; 175 sort(sorted.begin(), sorted.end()); 176 177 if (s == sorted) { 178 cout << "Bob\n"; 179 return; 180 } 181 182 vector<int> idx; 183 for(int i = 0; i < n; ++i) { 184 if(s[i] != sorted[i]) { 185 idx.push_back(i + 1); 186 } 187 } 188 189 cout << "Alice\n"; 190 cout << idx.size() << '\n'; 191 for(auto i : idx) cout << i << " "; 192 cout << '\n'; 193 } 194 195 signed main() { 196 ios_base::sync_with_stdio(0); cin.tie(0); 197 int ttt = 1; 198 cin >> ttt; 199 while(ttt--) { 200 solve(); 201 } 202 } 203 ``` 204 205 **Rate The Problem!** 206 207 * Good Problem 208 * Okay Problem 209 * Bad Problem 210 * Didn't Solve 211 212 [2190B1 - Sub-RBS (Easy Version)](/contest/2190/problem/B1 "Codeforces Round 1073 (Div. 1)") 213 214 * Idea: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 215 * Solution: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 216 * Editorial: [weirdflexbutok](/profile/weirdflexbutok "Master weirdflexbutok") 217 218 **Hints** 219 220 **Hint 1** 221 222 Try to fix the first position where the better sequence and string differ in characters. 223 224 **Hint 2** 225 226 Greedily delete characters. You will always end up with an RBS if possible it's possible to make the total balance zero. 227 228 **Solution** 229 230 For a string $t$ to be **better** than $s$, note that some prefix of $t$ will be identical to prefix of $s$, then at the position $i$ where $t_i \neq s_i$, $s_i =$ $)$ and $t_i =$ $($. 231 232 Consider the following greedy algorithm. We try to fix the first position where $t_i \neq s_i$ and $s_i =$ $)$, therefore we have $t[1 : i-1]$ = $s[1 : i - 1]$. Now $s_i$ must be $)$. To make $t$ bigger, we look for the first index $j \gt i$ such that $s_j$ = $($. Since this is the next character we add to the subsequence, we must skip the last $j - i$ characters, which will all be $)$. For a sequence to be an RBS, it is necessary for it to have equal number of $($ and $)$. Therefore, we must atleast skip $j - i$ more ( after position $j$ in $t$. 233 234 We can show that if we can have $j - i$ $($ brackets after position $j$ and we delete them, we will always end up with RBS of size $n - 2 \times (j - i)$. 235 236 **Proof** 237 238 Define a balance of a prefix of a bracket string as the number of opening brackets minus the number of closing brackets. 239 240 For a string $t$ to be an RBS, all of its prefix balances must be non-negative. $s$ is an RBS. We can show that for any index in $t$, $bal_t[i] \geq bal_s[j]$, where the $j$-th character in $s$ is at the $i$-th index in $t$. This is because deleting an $)$ in $s$ will increase the balance of every index after the position. Since we only delete $($ after $)$, all the indices' balances must be greater or equal to what it was before. 241 242 Therefore, we can simple precompute the next position of $($ for each index, and find the max over $n - 2 \times (j - i)$ as long as there are sufficient $)$ to delete after $j$. 243 244 Time complexity : $O(n)$ 245 246 **Code** 247 248 ``` 249 #include <bits/stdc++.h> 250 using namespace std; 251 252 int main(){ 253 std::ios_base::sync_with_stdio(0); 254 std::cin.tie(0); 255 256 int T; 257 cin >> T; 258 while(T--){ 259 int n; 260 string s; 261 cin >> n >> s; 262 vector<int> nx(n + 1, n + 1); 263 vector<int> suf(n + 1, 0); 264 for(int i = n - 1; i >= 0; i--){ 265 if(s[i] == '(') nx[i] = i; 266 else nx[i] = nx[i + 1]; 267 if(s[i] == '(') suf[i] += 1; 268 suf[i] += suf[i + 1]; 269 } 270 271 int ans = -1; 272 for(int i = 0; i < n; i++){ 273 if(s[i] == ')' and nx[i] <= n){ 274 int ig = nx[i] - i; 275 if(suf[nx[i] + 1] >= ig){ 276 ans = max(ans, n - 2 * ig); 277 } 278 } 279 } 280 281 cout << ans << '\n'; 282 } 283 } 284 ``` 285 286 **Rate The Problem!** 287 288 * Good Problem 289 * Okay Problem 290 * Bad Problem 291 * Didn't Solve 292 293 [2190B2 - Sub-RBS (Hard Version)](/contest/2190/problem/B2 "Codeforces Round 1073 (Div. 1)") 294 295 * Idea: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 296 * Solution: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 297 * Editorial: [weirdflexbutok](/profile/weirdflexbutok "Master weirdflexbutok") 298 299 **Hints** 300 301 **Hint 1** 302 303 What values can $f(t)$ take if length of $t$ is fixed? 304 305 **Answer** 306 307 $0$ or $|t| - 2$ 308 309 **Hint 2** 310 311 What is a simple condition the string must satisfy for $f(t)$ to be $|t| - 2$? 312 313 **Answer** 314 315 $t$ must be an RBS, and $)(($ must be a subsequence of $t$. 316 317 **Hint 3** 318 319 Use dynamic programming. 320 321 **Solution** 322 323 First, read the solution to D1. 324 325 We can further observe that if our answer is $n - 2 \times k$, we must have had $((($ $\cdots$ $()$ followed by $k$ $)$ s. If we instead follow the same greedy algorithm at the index of the final $($, we end up getting $k = 1$. Therefore, if a good subsequence exists, we can always get a subsequence of length $n - 2$. 326 327 Therefore, a string has a **better** subsequence of length $n - 2$ iff it has a "$)($" followed by "$($". We can further relax this condition to $s$ is good if $s$ is a RBS and it has "$)(($" as a subsequence. 328 329 **Proof** 330 331 Suppose $s$ has $)(($ at position $i \lt j \lt k$. If $s[i + 1] =$ $($, we can choose $(i,i+1,k)$ and we are done. Else, $(i+1,j,k)$ is the same subsequence. Repeating this, we will always end up with $(l, l + 1, k)$ eventually for some $l$. 332 333 Now, we can simply count the number of subsequences of different lengths that are an RBS and have a subsequence "$)(($". This can be done by dynamic programming similar to counting number of subsequences that are RBS. 334 335 We define the following DP state: 336 337 $dp[i][b][l][k]$ = number of bracket sequences using first $i$ characters, with balance $b$, having length $l$ and $k$ indicates how many characters of "$)(($" occur as a subsequence in the strings. 338 339 We obtain the following cases: 340 341 * If $s[i] =$ $($ and $k =$ {$1, 2$}, $dp[i][b + 1][l + 1][k + 1]$ $+= dp[i - 1][b][l][k]$ 342 * If $s[i] =$ $($ and $k =$ {$0, 3$}, $dp[i][b + 1][l + 1][k]$ $+= dp[i - 1][b][l][k]$ 343 * If $s[i] =$ $)$ and $k =$ {$0$} and $b \geq 1$, $dp[i][b - 1][l + 1][k + 1]$ $+= dp[i - 1][b][l][k]$ 344 * If $s[i] =$ $)$ and $k =$ {$1, 2, 3$} and $b \geq 1$, $dp[i][b - 1][l + 1][k]$ $+= dp[i - 1][b][l][k]$ 345 346 We finally output answer as the sum over $dp[n][0][l][3] \times (l - 2)$ over all $l$. 347 348 Time Complexity: $O(n^3)$. This can also be implemented in $O(n^2)$ by not storing the length but the sum of lengths and the count separately. 349 350 **Code** 351 352 ``` 353 #include <bits/stdc++.h> 354 using namespace std; 355 356 // Mint template omitted for readability 357 358 constexpr int md = 998244353; 359 using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>; 360 361 vector<Mint> fact(1, 1); 362 vector<Mint> inv_fact(1, 1); 363 364 Mint C(int n, int k) { 365 if (k < 0 || k > n) { 366 return 0; 367 } 368 while ((int) fact.size() < n + 1) { 369 fact.push_back(fact.back() * (int) fact.size()); 370 inv_fact.push_back(1 / fact.back()); 371 } 372 return fact[n] * inv_fact[k] * inv_fact[n - k]; 373 } 374 375 int main(){ 376 std::ios_base::sync_with_stdio(0); 377 std::cin.tie(0); 378 int T; 379 cin >> T; 380 while(T--){ 381 int n; 382 cin >> n; 383 string s; 384 cin >> s; 385 string t = ")(("; 386 vector<vector<vector<Mint>>> dp(4, vector(n + 1, vector(n + 1, Mint(0)))); // balance, length 387 dp[0][0][0] = 1; 388 for(int i = 0; i < n; i++){ 389 auto ndp = dp; 390 int add = s[i] == '(' ? 1 : -1; 391 for(int bal = 0; bal < n; bal++){ 392 for(int len = 0; len < n; len++){ 393 if(bal + add < 0) continue; 394 for(int ii = 0; ii < 4; ii++){ 395 int ni = ii; 396 if(ii == 0 and s[i] == ')') ni++; 397 if((ii == 1 or ii == 2) and s[i] == '(') ni++; 398 ndp[ni][bal + add][len + 1] += dp[ii][bal][len]; 399 } 400 } 401 } 402 swap(dp, ndp); 403 } 404 405 Mint ans = 0; 406 for(int i = 0; i <= n; i++){ 407 ans += dp[3][0][i] * (i - 2); 408 } 409 410 cout << ans << '\n'; 411 } 412 } 413 ``` 414 415 **Rate The Problem!** 416 417 * Good Problem 418 * Okay Problem 419 * Bad Problem 420 * Didn't Solve 421 422 [2190C - Comparable Permutations](/contest/2190/problem/C "Codeforces Round 1073 (Div. 1)") 423 424 * Idea: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 425 * Solution: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 426 * Editorial: [reirugan](/profile/reirugan "Master reirugan") 427 428 **Hints** 429 430 **Hint 1** 431 432 $q \gt p$ and $\mathbb{rev}(q) \gt \mathbb{rev}(p)$ is equivalent to the following condition: let $i$ be the first index at which $p$ and $q$ differ, and let $j$ be the last index at which $p$ and $q$ differ. Then we must have $q_i \gt p_i$ and $q_j \gt p_j$. 433 434 **Hint 2** 435 436 Fix some $i \lt j$, and consider the subarray $p[i, j]$. We can rearrange these elements however we want, as long as we increase both endpoints. It is easy to see that this is impossible if $p_i$ or $p_j$ is the maximum of the subarray. Otherwise, we want to choose the lexicographically smallest such option. Set $q_i$ to be the smallest element in $p[i, j]$ that is larger than $p_i$. Then, we place the rest of the elements in ascending order to fill $q[i+1, j]$. 437 438 **Hint 3** 439 440 Optimal $i = k - 1$, where $k$ is the largest index where $p_k \gt p_{k - 1}$ and $p_k \gt p_{k + 1}$. 441 442 **Hint 4** 443 444 $[k, n]$ is first decreasing, then increasing. 445 446 **Solution** 447 448 We require that $q \gt p$ and $\mathbb{rev}(q) \gt \mathbb{rev}(p)$. By definition, this is equivalent to the following condition: let $i$ be the first index at which $p$ and $q$ differ, and let $j$ be the last index at which $p$ and $q$ differ. Then we must have that $q_i \gt p_i$ and $q_j \gt p_j$. 449 450 Now, fix some $i \lt j$, and consider the subarray $p[i, j]$. We can rearrange these elements however we want, as long as we increase both endpoints. It is easy to see that this is impossible if $p_i$ or $p_j$ is the maximum of the subarray. Otherwise, we want to choose the lexicographically smallest such option. To do so, we set $q_i$ to be the smallest element in $p[i, j]$ that is larger than $p_i$. Then, we place the rest of the elements in ascending order to fill $q[i+1, j]$. 451 452 Let's verify that this is valid. Clearly, $q_i \gt p_i$ by construction. Now, $q_j$ is the maximum of $q[i+1, j]$, so either $q_j$ or $q_i$ is the maximum of $p[i, j]$. If $q_j$ is the maximum, then it must be larger than $p_j$ because $p_j$ is not the maximum. Otherwise, if $q_i$ is the maximum, then $p_i$ is the second maximum by construction, so $q_j = p_i$. Thus, $q_j$ is larger than $p_j$ because $p_j$ is not the maximum or the second maximum. 453 454 We conclude that any choice of $i \lt j$ such that $p_i$ and $p_j$ are not the maximum of $p[i, j]$ yields a valid choice of $q$, and the optimal one is the one produced by the above construction. 455 456 Now, we want to find the choice of $i$ and $j$ that yield the lexicographically smallest option. It is easy to see that we want to use the largest possible value of $i$, because we are going to keep everything before index $i$ the same, and increase the value at index $i$. Let $1 \lt k \lt n$ denote the index of the last local maximum; that is, $k$ is the largest integer satisfying $p_k \gt p_{k-1}, p_{k+1}$. Then we claim that $i=k-1$ is optimal. 457 458 First, we show that it is valid. Indeed, the subarray $p[i, i+2] = p[k-1, k+1]$ is clearly valid. Next, we show that there is no larger valid choice of $i$. Notice that $p[k, n]$ is first decreasing, then increasing (possibly over an empty subarray). If we choose $i \lt j$ contained in the decreasing portion, then $p_i$ will be the maximum of $p[i, j]$. If we choose $i \lt j$ in the increasing portion, then $p_j$ will be the maximum of $p[i, j]$. Finally, if we choose $i \lt j$ that crosses from the decreasing to the increasing portion, then $\max(p_i, p_j)$ is the maximum of $p[i, j]$. Therefore, no subarray that uses $i \geq k$ can possibly be valid. 459 460 We conclude that we must choose $i = k-1$. Notice that identical reasoning to the above proof shows that if there is no local maximum, then no valid $q$ exists, so we may output $-1$. We further observe that the value of $k$, if it exists, can be determined in $n-1$ queries of adjacent values. 461 462 Now, we want to choose the value of $j$. It is easy to see that we want to choose the largest possible value of $j$, because it gives us strictly more options of how to rearrange the subarray. Since $p[k, n]$ is decreasing then (possibly) increasing, it suffices to find the first value larger than $p_k$, then we will choose the subarray to end right before that value. If no such value exists, we can choose $j = n$. 463 464 However, we do not have to explicitly find the value of $j$. In fact, it suffices to pretend that $j = n$, and then using the construction from earlier, it will naturally follow that everything larger than the actual value of $j$ will remain untouched, since that portion of $p$ is already increasing. So now, we simply have to sort the values in $p[i, n]$, then move the one that comes directly after $p_i$ to the front. 465 466 Notice that we can split this subarray into three monotonic sections; furthermore, we know where the cutoffs for these sections are, since we have queried all adjacent values before. We can sort by finding the next minimum of the subarray one by one. We know that the next minimum must be the next minimum of one of the three sections, and since they are monotonic, we can track these with three pointers. We can find which of these three values is the smallest using two queries. In total, we sort the subarray using at most $2(n-1)$ queries. We can then move the value directly after $p_i$ to the spot $q_i$ without any additional queries. 467 468 This solves the problem using at most $3n$ queries, as desired. 469 470 **Code** 471 472 ``` 473 #include <bits/stdc++.h> 474 475 using namespace std; 476 477 void solve() { 478 int n; 479 cin >> n; 480 481 auto ask = [&](int i, int j) { 482 cout << "? " << i << " " << j << endl; 483 484 int ans; 485 cin >> ans; 486 return ans; 487 }; 488 489 int j = -1; 490 vector<int> val(n + 2); val[n] = 1; 491 for(int i = n - 1; i; i--) { 492 val[i] = ask(i, i + 1); 493 if(val[i] && !val[i + 1]) { 494 j = i; 495 break; 496 } 497 } 498 if(j == -1) { 499 cout << "! " << -1 << endl; 500 return; 501 } 502 503 // Need to sort [j + 1, n] 504 int k = j + 1; 505 while(!val[k + 1]) k++; 506 507 // [j + 1, k] - decreasing 508 // [k + 1, n] - increasing 509 vector<int> order; 510 int l = k, r = k + 1; 511 while(l > j && r <= n) { 512 if(ask(l, r)) order.push_back(l--); 513 else order.push_back(r++); 514 } 515 while(l > j) order.push_back(l--); 516 while(r <= n) order.push_back(r++); 517 518 l = 0, r = order.size() - 1; 519 while(l <= r) { 520 int m = l + r >> 1; 521 if(ask(j, order[m])) r = m - 1; 522 else l = m + 1; 523 } 524 assert(l < order.size()); 525 526 vector<int> res(n + 1); 527 iota(res.begin(), res.end(), 0); 528 res[j] = order[l]; 529 order[l] = j; 530 for(int i = j + 1; i <= n; i++) { 531 res[i] = order[i - j - 1]; 532 } 533 534 res.erase(res.begin()); 535 cout << "! "; for(auto i : res) cout << i << " "; cout << endl; 536 } 537 538 signed main() { 539 int ttt = 1; 540 cin >> ttt; 541 while(ttt--) { 542 solve(); 543 } 544 } 545 ``` 546 547 **Rate The Problem!** 548 549 * Good Problem 550 * Okay Problem 551 * Bad Problem 552 * Didn't Solve 553 554 [2190D - Prufer Vertex](/contest/2190/problem/D "Codeforces Round 1073 (Div. 1)") 555 556 * Idea: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 557 * Solution: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 558 * Editorial: [Intellegent](/profile/Intellegent "Grandmaster Intellegent"), [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 559 560 **Hints** 561 562 **Hint 1** 563 564 Why isn't $P(v)$ always $n - 1$? Specifically, when can we delete vertex $n - 1$? 565 566 **Hint 2** 567 568 Since each tree (with $n \ge 2$) has at least two leaves, $n - 1$ can be deleted only if $n - 1$ and $n$ are the only leaves. How to find $P(v)$ using this fact? 569 570 **Hint 3** 571 572 This means that there's just a single path from $n$ to $n - 1$. In this case it's obvious that the second vertex on the path will be left at the end. Therefore, $P(v)$ is always the second vertex on the path from $n$ to $n - 1$. 573 574 **Hint 4** 575 576 To count this you really only need to consider the case when $v$ and $n$ are adjacent. 577 578 **Hint 5** 579 580 All vertices in a component are indistinguishable. 581 582 **Solution** 583 584 Why isn't $P(v)$ always $n - 1$? Specifically, when can we delete vertex $n - 1$? 585 586 Since each tree (with $n \ge 2$) has at least two leaves, $n - 1$ can be deleted only if $n - 1$ and $n$ are the only leaves. This means that there's just a single path from $n$ to $n - 1$. In this case it's obvious that the second vertex on the path will be left at the end. Therefore, $P(v)$ is always the second vertex on the path from $n$ to $n - 1$. 587 588 So now we just have to count the number of ways to connect the tree satisfying these conditions. The easiest case is when $n$ and $n - 1$ are in the same component, then the Prufer vertex is fixed, so making the forest a tree doesn't change it. 589 590 Let's assume that $n$ and $v$ are already connected, because if not, we have to connect them with an edge, and we can update all the needed values dynamically. 591 592 We have to connect the tree so that $n - 1$ is in the subtree of $v$ (when rooted at $n$). 593 594 Let $C$ be the set of vertices in the component of $n$. Notice that since all vertices in $C$ are indistinguishable, the component with $n - 1$ will be attached to the component of $n$ to each vertex in $C$ in the same number of final trees. 595 596 Let $k$ be the size of the subtree of $v$. Then in $\dfrac{k}{|C|}$ of all trees $n - 1$ will be connected to $n$ through a subtree of $v$. 597 598 Therefore, we just need to maintain the total number of ways to complete the tree and after adding edges from $n$ to $v$, and multiply that value by $\dfrac{k}{|C|}$ to solve the problem. 599 600 Time complexity: $O(n)$ or $O(n \log n)$. 601 602 **Code** 603 604 ``` 605 #include <bits/stdc++.h> 606 607 using namespace std; 608 609 const int mod = 998244353; 610 611 // Removed Mint template for better readability 612 613 vector<Mint> get(vector<vector<int>> g) { 614 int n = g.size() - 1; 615 616 vector<int> comp(n + 1, -1), dp(n + 1, 1), parent(n + 1), sizes(n); 617 int k = 0; 618 function<void(int, int)> dfs = [&](int v, int p) { 619 comp[v] = k; sizes[k]++; 620 621 for(auto to : g[v]) { 622 if(to == p) continue; 623 624 parent[to] = v; 625 dfs(to, v); 626 dp[v] += dp[to]; 627 } 628 }; 629 for(int v = n; v; v--) { 630 if(comp[v] == -1) { 631 dfs(v, 0); 632 k++; 633 } 634 } 635 636 vector<int> sz(n + 1); 637 for(int v = 1; v <= n; v++) sz[v] = sizes[comp[v]]; 638 639 vector<Mint> inv(n + 1); inv[1] = 1; 640 for(int i = 2; i <= n; i++) { 641 inv[i] = mod - inv[mod % i] * (mod / i); 642 } 643 644 vector<Mint> ans(n); 645 Mint p = 1; 646 for(int i = 0; i < k; i++) p *= sizes[i]; 647 648 vector<Mint> n_power(n + 1); 649 n_power[0] = 1; for(int i = 1; i <= n; i++) n_power[i] = n_power[i - 1] * n; 650 651 auto n_pow = [&](int k) { 652 if(k >= 0) return n_power[k]; 653 else if(k == -1) return inv[n]; 654 else assert(0); 655 }; 656 657 if(comp[n] == comp[n - 1]) { 658 // If n and n - 1 are already in one component P(T) is determined 659 int v = n - 1; 660 while(parent[v] != n) v = parent[v]; 661 662 ans[v] = p * n_pow(k - 2); 663 } 664 else { 665 for(int v = 1; v <= n - 1; v++) { 666 if(comp[v] == comp[n]) { 667 // v and n have to be connected 668 if(parent[v] != n) continue; 669 670 ans[v] = dp[v] * p * inv[sz[n]] * n_pow(k - 2); 671 } 672 else if(comp[v] == comp[n - 1]) { 673 // Just connect v and n 674 ans[v] = p * inv[sz[n]] * inv[sz[n - 1]] * (sz[n] + sz[n - 1]) * n_pow(k - 3); 675 } 676 else { 677 // Connect v and n and same as first case 678 ans[v] = sz[v] * p * inv[sz[n]] * inv[sz[v]] * n_pow(k - 3); 679 } 680 } 681 } 682 683 return ans; 684 } 685 686 void solve() { 687 int n, m; 688 cin >> n >> m; 689 690 vector<vector<int>> g(n + 1); 691 for(int i = 0; i < m; i++) { 692 int u, v; 693 cin >> u >> v; 694 695 g[u].push_back(v); g[v].push_back(u); 696 } 697 698 vector<Mint> ans = get(g); 699 for(int v = 1; v < n; v++) cout << ans[v] << ' '; cout << endl; 700 } 701 702 signed main() { 703 ios_base::sync_with_stdio(0); cin.tie(0); 704 int ttt = 1; 705 cin >> ttt; 706 while(ttt--) { 707 solve(); 708 } 709 } 710 ``` 711 712 **Rate The Problem!** 713 714 * Good Problem 715 * Okay Problem 716 * Bad Problem 717 * Didn't Solve 718 719 [2190E - Median Permutation](/contest/2190/problem/E "Codeforces Round 1073 (Div. 1)") 720 721 * Idea: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 722 * Solution: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 723 * Editorial: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 724 725 Special thanks to [Sana](/profile/Sana "International Grandmaster Sana") for showing me how to go from $O(n^2)$ to $O(n)$. 726 727 **Hints** 728 729 **Hint 1** 730 731 If you bruteforce and oeis, you'll find out that the total number of valid permutations is $n \cdot 2^{n - 2}$. You should forget about this, trying to prove this directly is not gonna work. 732 733 **Hint 2** 734 735 Consider the case where $p_1 = 1$ and $p_n = n$. 736 737 **Hint 3** 738 739 Look at even and odd indices separately. 740 741 **Hint 4** 742 743 When $p_1 = 1$ and $p_n = n$, the condition is that $p_{i - 2} \lt p_i$ must hold for all $i$. Try to generalize this condition for other cases. 744 745 **Hint 5** 746 747 If $p_{i - 2} \lt p_i \gt p_{i + 2}$, we must have $p_i = n$, so even and odd indices are almost monotonic. 748 749 **Hint 6** 750 751 Consider a case where $p_1 \lt p_3$ and $p_2 \gt p_4$ and the restrictions this puts on the problem. 752 753 **Hint 7** 754 755 The two cases above are sufficient, try to make them easier two count. 756 757 **Hint 8** 758 759 There are $2$ chains of increasing values. 760 761 **Solution** 762 763 Notice that $1$ and $n$ can never be medians, so $f(p)$ has to be a permutation of ${ 2, \ldots, n }$. 764 765 Suppose that we have 5 consecutive elements $[p_1, p_2, p_3, p_4, p_5]$, and $p_1 \lt p_3 \gt p_5$. WLOG, assume that $p_2 \lt p_4$. It turns out there's a very tight condition for this case to not have duplicates. Mainly, $p_3$ has to be the largest element. 766 767 **Proof** 768 769 Suppose $p_4$ is the largest element instead. Median of $[3, 5]$ is $p_3$. For $[2, 4]$ to not have $p_3$ as the median, we must have $p_3 \lt p_2 \lt p_4$, and the median of $[2, 4]$ is $p_2$. But then in $[1, 3]$ we have $p_1 \lt p_3 \lt p_2$, so $p_3$ is the median again, which is a contradiction. 770 771 Notice that since $p_3$ is the largest element among all $3$ subarrays in which it takes part in, $p_3$ **cannot** appear in $f(p)$. Therefore, an important observation is: if $p_{i - 2} \lt p_i \gt p_{i + 2}$, then $p_i = n$. Similarly, if $p_{i - 2} \gt p_i \lt p_{i + 2}$, then $p_i = 1$. 772 773 From this we can see that all indices with the same parity are almost monotonic. But how do even and odd indices interact with each other? 774 775 Let's consider another case: $[p_1, p_2, p_3, p_4]$, $p_1 \lt p_3$ and $p_2 \gt p_4$ (odd is increasing, even is decreasing). We can see that this case also has a simple structure. Mainly, if we bruteforce (to not consider a lot of cases) all valid permutations of size $4$ that satisfy the two inequalities above, we'll get only two solutions: $[1, 4, 2, 3]$ and $[3, 2, 4, 1]$. This means that either all even indices have values greater than all odd indices, or vice versa. 776 777 The two conditions we found are actually already sufficient, and it's very easy to prove this. 778 779 Suppose $f(p)_i = f(p)_j$ with $i \lt j$, so $p$ is invalid. Notice that for this to happen $[i, i + 2]$ and $[j, j + 2]$ have to both include the same value in $p$, so $[i, i + 2]$ and $[j, j + 2]$ have to intersect, so $i + 2 \ge j$, or $j - i \le 2$. Therefore, it is sufficient to check that there are no "bad" subarrays $[i, i + 4]$, and if all subarrays of size $5$ are valid in $p$, $p$ is valid as well. 780 781 Using this and our two conditions above we can just check all permutations of size $5$ and verify that they are sufficient. 782 783 So now we only have to understand how to count. The conditions we have are actually pretty restrictive. 784 785 WLOG, assume that $1$ is located earlier than $n$. 786 787 First consider the case where $pos_1$ and $pos_n$ have the different parity. 788 789 Consider the picture below. Each arrow denotes that the element should be smaller than the element arrow points to. Let's see how even and odd indices compare to each other. 790 791 **Spoiler** 792 793  794 795 Look at $i = 2$. We have $p_2 \gt p_4$ and $p_3 \lt p_5$, which is the second condition we had. Since $p_4 = 1$, we must have $p_4 \lt p_2 \lt p_3 \lt p_5$. For $i = 1$ the same thing holds, and since we already know that $p_3 \gt p_2$ (and all odd indices in this case must have a larger element than even indices), we must have $p_4 \lt p_2 \lt p_1 \lt p_3 \lt p_5$. 796 797 The same thing happens after $n$ on the right side, we must have: $p_{10} \lt p_{12} \lt p_{13} \lt p_{11} \lt p_9$, so essentially can add two new (purple) arrows to the picture: 798 799 **Spoiler** 800 801  802 803 And after some recoloring, we can see that the when $1$ and $n$ are located on different parities, there must be two chains of values: 804 805 **Spoiler** 806 807  808 809 After applying the same logic, we get a similar situation when $1$ and $n$ are located on the same parity: 810 811 **Spoiler** 812 813  814 815 From this we can see that in all cases there are at most two increasing chains (dark-red and orange on the two pictures above). 816 817 Since we know the positions of $1$ and $n$, the problem now transformed into: given two chains of increasing values, we have to count the number of ways to put all values $1, 2, \ldots, n$ into the chains with some values already being placed. 818 819 Suppose we have two chains $a$ and $b$ with sizes $k$ and $l$, and we know that some $a_i = x$. Notice that this means that $i - 1$ of the $x - 1$ elements before $x$ have to be in $a$, and all the others must be in $b$. This means that we can go through all placed elements and count the number of ways to position the unplaced ones using binomial coefficients. You can read the code for better understanding. 820 821 Time complexity: $O(n)$. 822 823 **Code** 824 825 ``` 826 #include <bits/stdc++.h> 827 828 using namespace std; 829 830 const long long mod = 998244353; 831 const int MAX = 2e5 + 42; 832 833 // Mint template omitted for readability 834 835 Mint fact[MAX], inv[MAX]; 836 837 Mint C(int n, int k) { 838 if(n < k || k < 0) return 0; 839 return fact[n] * inv[k] * inv[n - k]; 840 } 841 842 Mint get(vector<int> p) { 843 int n = p.size(); 844 845 int pos_1 = -1, pos_n = -1; 846 for(int i = 0; i < n; i++) { 847 if(p[i] == 1) pos_1 = i; 848 if(p[i] == n) pos_n = i; 849 } 850 assert(pos_1 != -1); 851 assert(pos_n != -1); 852 853 if(pos_1 > pos_n) { 854 reverse(p.begin(), p.end()); 855 pos_1 = n - 1 - pos_1; 856 pos_n = n - 1 - pos_n; 857 } 858 859 vector<vector<int>> g(n + 1); 860 if(pos_1 % 2 == pos_n % 2) { 861 for(int i = (pos_1 & 1 ^ 1); i < n; i += 2) { 862 if(i >= 2) g[i - 2].push_back(i); 863 } 864 for(int i = pos_1 - 2; i >= 0; i -= 2) { 865 g[i + 2].push_back(i); 866 } 867 for(int i = pos_1 + 2; i <= pos_n; i += 2) { 868 g[i - 2].push_back(i); 869 } 870 for(int i = pos_n + 2; i < n; i += 2) { 871 g[i].push_back(i - 2); 872 } 873 } 874 else { 875 for(int i = pos_1 - 2; i >= 0; i -= 2) { 876 g[i + 2].push_back(i); 877 } 878 for(int i = pos_1 + 2; i < n; i += 2) { 879 g[i - 2].push_back(i); 880 } 881 882 for(int i = pos_n - 2; i >= 0; i -= 2) { 883 g[i].push_back(i + 2); 884 } 885 for(int i = pos_n + 2; i < n; i += 2) { 886 g[i].push_back(i - 2); 887 } 888 } 889 890 if(pos_1 != 0) { 891 if(pos_1 % 2 == 0) g[0].push_back(1); 892 if(pos_1 % 2 == 1) g[1].push_back(0); 893 } 894 if(pos_n != 0) { 895 if(pos_n % 2 == (n - 1) % 2) g[n - 2].push_back(n - 1); 896 if(pos_n % 2 != (n - 1) % 2) g[n - 1].push_back(n - 2); 897 } 898 899 g[pos_1].clear(); 900 for(int i = 0; i < n; i++) { 901 if(i == pos_1 || i == pos_n) continue; 902 assert(g[i].size() == 1); 903 if(g[i][0] == pos_n) g[i].clear(); 904 } 905 906 vector<int> in_degree(n); 907 for(int v = 0; v < n; v++) { 908 for(auto to : g[v]) in_degree[to]++; 909 } 910 911 vector<pair<int, int>> pos(n + 1); 912 int t = 0, cnt = 0; 913 for(int i = 0; i < n; i++) { 914 if(i == pos_1 || i == pos_n || in_degree[i] > 0) continue; 915 916 t++; 917 cnt = 0; 918 if(t == 1) pos[1] = {t, cnt++}; 919 int j = i; 920 while(1) { 921 pos[p[j]] = {t, cnt++}; 922 923 if(g[j].empty()) break; 924 j = g[j][0]; 925 } 926 } 927 pos[n] = {t, cnt}; 928 929 Mint ans = 1; 930 for(int i = 1; i < n; i++) { 931 int j = i + 1; 932 while(pos[j].first == 0) j++; 933 934 auto [ti, ci] = pos[i]; ci++; 935 auto [tj, cj] = pos[j]; 936 if(ti == 2) ci = i - ci; 937 if(tj == 2) cj = j - 1 - cj; 938 939 // At i we have ci in first, at j - 1 we have cj 940 // Choose cj - ci from j - i - 1 941 ans *= C(j - i - 1, cj - ci); 942 i = j - 1; 943 } 944 945 return ans; 946 } 947 948 void solve() { 949 int n; 950 cin >> n; 951 vector<int> p(n); 952 for(auto &i : p) { 953 cin >> i; 954 } 955 956 Mint ans = get(p); 957 cout << ans << '\n'; 958 } 959 960 signed main() { 961 fact[0] = 1; for(int i = 1; i < MAX; i++) fact[i] = fact[i - 1] * i; 962 inv[MAX - 1] = 1 / fact[MAX - 1]; 963 for(int i = MAX - 1; i; i--) inv[i - 1] = inv[i] * i; assert(inv[0] == 1); 964 ios_base::sync_with_stdio(0); cin.tie(0); 965 int ttt = 1; 966 cin >> ttt; 967 while(ttt--) { 968 solve(); 969 } 970 } 971 ``` 972 973 **Rate The Problem!** 974 975 * Good Problem 976 * Okay Problem 977 * Bad Problem 978 * Didn't Solve 979 980 [2190F - Xor Product](/contest/2190/problem/F "Codeforces Round 1073 (Div. 1)") 981 982 * Idea: [nika-skybytska](/profile/nika-skybytska "Grandmaster nika-skybytska") 983 * Solution: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 984 * Editorial: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 985 986 **Hints** 987 988 **Hint 1** 989 990 Find a formula for $S(0, 0, k)$ 991 992 **Hint 2** 993 994 Find a formula for $S(x, x, k)$ 995 996 **Hint 3** 997 998 You can assume that $x$ and $x + k - 1$ have no non-zero common prefix. Let $p$ be the most significant bit $2$ of $x + k - 1$, $a = P - 1 - x$ and $b = x + k - 1 - P$. Then $S(x, x, k) = S(0, 0, \max(a + 1,\ b + 1)) \ \cup\ [2^{p + 1} - 1 - f(a, b),\ 2^{p + 1} - 1]$. 999 1000 **Hint 4** 1001 1002 Find a formula for $S(x, y, k)$ 1003 1004 **Hint 5** 1005 1006 You can't assume that $x$ and $x + k - 1$ have no common prefix, but try to solve when they don't for now 1007 1008 **Hint 6** 1009 1010 Denote $P_x$, $a$ and $b$ as in Hint 3, and similarly $P_y$, $c$ and $d$ for $y$. When $P_x = P_y = P$, the formula is $S(x, y, k) = [0, \max(f(b, d), f(a, c)] \cup [2P - 1 - \max(f(a, d), f(b, c), 2P - 1]$. Solve when $P_x \neq P_y$. 1011 1012 **Hint 7** 1013 1014 Assume $P_x \lt P_y$. $S(x, y, k) = [Py - Px - 1 - \min(f(b, c), Px - 1), Py - Px + \min(f(a, c), Px - 1)] \cup $ $[Py + Px - 1 - \min(f(a, d), Px - 1), Py + Px + \min(f(b, d), Px - 1)]$. 1015 1016 **Hint 8** 1017 1018 Common non-zero prefix doesn't change the size of $S$, so in general the formula for size is $|S(x, y, k)| = \min\left(f(a, c) + f(b, c) + 2,\ 2P_x\right)\ +\ \min\left(f(a, d) + f(b, d) + 2,\ 2P_x\right)$. Use digit dp to solve the problem. 1019 1020 **Solution** 1021 1022 A few notations: 1023 1024 * $S(x, y, k) = {(x + i) \oplus (y + j) \mid 0 \le i \lt k,\ 0 \le j \lt k}$. 1025 * $S(x, y, k, l) = {(x + i) \oplus (y + j) \mid 0 \le i \lt k,\ 0 \le j \lt l}$. 1026 * $[l, r] \oplus x = {i \oplus x \mid l \le i \le r}$. 1027 * $[l_1, r_1] * [l_2, r_2] = {i \oplus j \mid l_1 \le i \le r_1,\ l_2 \le j \le r_2}$ (We'll call this the XOR Cartesian product). 1028 1029 Let's try to find a formula for a general $S(x, y, k)$. Consider the simplified case $x = y$. 1030 1031 If $x = y = 0$, we can achieve every XOR value up to the maximum possible XOR. Let $p$ be the smallest integer such that $2^p \ge k$. Then $S(0, 0, k) = [0,\ 2^p - 1]$. 1032 1033 When $x \neq y$, notice that $x$ and $x + k - 1$ share some common prefix of bits. Let its length be $L$. That prefix is present in all $x + i$ and $x + j$, so it cancels out in XOR. Therefore, we can zero out the top $L$ bits and assume $\lfloor \log_2 x \rfloor \neq \lfloor \log_2 (x + k - 1) \rfloor$. 1034 1035 Let $p = \lfloor \log_2 (x + k - 1)\rfloor$ and $P = 2^p$. Then $x$ does **not** have the bit $P$ set, and we can split: - $[x,\ P - 1]$ - $[P,\ x + k - 1]$ 1036 1037 Now write $S(x, x, k)$ as the union of XOR-products of these two ranges (there are 3 distinct ones, since cross terms are symmetric). 1038 1039 Define $a = (P - 1) - x, \quad b = (x + k - 1) - P$. 1040 1041 Product A: $[P,\ x + k - 1] * [P,\ x + k - 1]$. All numbers in $[P,\ x + k - 1]$ have the bit $P$ set, so it cancels in XOR. After removing that bit: $ [P,\ x + k - 1] * [P,\ x + k - 1] = S(0, 0, b + 1)$. (Here $b + 1 = (x + k - 1) - P + 1 = x + k - P$.) 1042 1043 Product B: $[x,\ P - 1] * [x,\ P - 1]$. This is similar to the $S(0, 0, \cdot)$ case but taken from the other side. Replace each $t \in [x,\ P - 1]$ with $t \oplus (P - 1)$, which equals to $(P - 1) - t$. Since we XOR both sides, the set of XORs does not change, and we get: $[x,\ P - 1] * [x,\ P - 1] = S(0, 0, a + 1)$ (here $a + 1 = (P - 1 - x) + 1 = P - x$). 1044 1045 Product C, the hardest case: $[x,\ P - 1] * [P,\ x + k - 1]$ Apply the same transforms: 1046 1047 * $[x,\ P - 1] \to [0,\ a]$ 1048 * $[P,\ x + k - 1] \to [0,\ b]$ 1049 1050 But now the “removed masks” do not cancel out, so at the end we must XOR by $(P - 1) \oplus P = 2^{p + 1} - 1$. 1051 1052 So: $[x,\ P - 1] * [P,\ x + k - 1] = S(0, 0, a + 1, b + 1)\ \oplus\ (2^{p + 1} - 1)$. 1053 1054 Let's understand how to find $S(0, 0, k, l)$. Claim: $S(0, 0, k, l)$ is a single interval, or $S(0, 0, k, l) = [0, f(k - 1, l - 1)]$, where $f(n, m)$ is the largest XOR of $0 \le i \le n$ and $0 \le j \le m$. 1055 1056 **Proof** 1057 1058 The claim is that the interval is $[0, M]$, where $M = f(k - 1,\ l - 1) = \max_{0 \le i \lt k,\ 0 \le j \lt l} (i \oplus j)$. 1059 1060 This is true because if we can obtain XOR value $C$, we can also obtain $C - 1$. Take the most significant bit where $C$ and $C - 1$ differ and flip that bit by adjusting either $i$ or $j$ (whichever has that bit set), then adjust lower bits as needed. This does not increase $i$ or $j$, so it stays within bounds. 1061 1062 It's not hard to compute $f(n, m)$ in general. 1063 1064 **How to compute** 1065 1066 Let $p$ be the index of the most significant set bit in $(n & m)$. Then $f(n, m) = n\ \vert\ m\ \vert\ (2^p - 1)$. 1067 1068 Using this, Product C becomes an interval: $S(0,0,a + 1,b + 1)\oplus (2^{p + 1} - 1) = [0,\ f(a, b)]\ \oplus\ (2^{p + 1} - 1) = [2^{p + 1} - 1 - f(a, b),\ 2^{p + 1} - 1]$. 1069 1070 So, combine the three parts: $S(x, x, k) = S(0, 0, a + 1)\ \cup\ S(0, 0, b + 1)\ \cup\ [2^{p + 1} - 1 - f(a, b),\ 2^{p + 1} - 1]$. 1071 1072 This can be simplified to: $S(x, x, k) = S(0, 0, \max(a + 1,\ b + 1)) \ \cup\ [2^{p + 1} - 1 - f(a, b),\ 2^{p + 1} - 1]$. 1073 1074 Now handle $x \ne y$ similarly. First assume that: $x$ and $x + k - 1$ have no common non-zero prefix bits (after stripping common prefix as before, though in this case it's not obvious that this will not change the set, but we'll handle this later), and similarly for $y$. 1075 1076 Let: $p_x = \lfloor \log_2(x + k - 1)\rfloor,\quad P_x = 2^{p_x}$, $p_y = \lfloor \log_2(y + k - 1)\rfloor,\quad P_y = 2^{p_y}$. 1077 1078 Split into four intervals: - $[x,\ P_x - 1]$, $[P_x,\ x + k - 1]$ - $[y,\ P_y - 1]$, $[P_y,\ y + k - 1]$ 1079 1080 Define $a = (P_x - 1) - x,\quad b=(x + k - 1) - P_x$, $c = (P_y - 1) - y,\quad d=(y + k - 1) - P_y$. 1081 1082 Now consider the four products: 1083 1084 1. $I_1 = [x, P_x - 1] * [y, P_y - 1] = [0, f(a, c)] \oplus (P_x - 1) \oplus (P_y - 1)$ 1085 2. $I_2 = [P_x, x + k - 1] * [P_y, y + k - 1] = [0, f(b, d)] \oplus P_x \oplus P_y$ 1086 3. $I_3 = [x, P_x - 1] * [P_y, y + k - 1] = [0, f(a, d)] \oplus (P_x - 1) \oplus P_y$ 1087 4. $I_4 = [P_x, x + k - 1] * [y, P_y - 1] = [0, f(b, c)] \oplus P_x \oplus (P_y - 1)$ 1088 1089 Notice that the $P_x = P_y = P$ case is trivial, we already almost solved it, and by the same reasoning $S(x, y, k) = [0, \max(f(b, d), f(a, c)] \cup [2P - 1 - max(f(a, d), f(b, c), 2P - 1]$ in this case. 1090 1091 Now WLOG assume $P_x \lt P_y$. We have $a + b = c + d = k - 2$. Notice that $a, b \lt P_x$ (since $a = P_x - 1 - x$ and $P_x + b \lt 2P_x$). Also notice that $c, d \lt 2P_x$, since $\max(a, b) \le \dfrac{k}{2} \lt P_x$, so $k \lt 2P_x$ and $c + d = k - 2$. 1092 1093 Consider $I_2 = [0, f(b, d)] \oplus P_x \oplus P_y$. Since $P_x \lt P_y$, write $P_x \oplus P_y = P_x + P_y$. Also $f(b, d) \lt 2P_x$. 1094 1095 * If $f(b, d) \lt P_x$, then $I_2 = [P_x + P_y,\ P_x + P_y + f(b, d)]$ 1096 * If $f(b, d) \ge P_x$, then $[0, f(b, d)]$ contains $P_x$, and we get: $I_2 = [P_y,\ P_y + (f(b, d) - P_x)]\ \cup\ [P_x + P_y,\ P_y + 2P_x - 1]$. 1097 1098 Now consider $I_3 = [0, f(a, d)] \oplus (P_x - 1) \oplus P_y$. XORing by $(P_x - 1)$ is just a reversal inside $[0, P_x - 1]$ and separately inside $[P_x, 2P_x - 1]$. 1099 1100 * If $f(a, d) \lt P_x$, then $I_3 = [P_y + (P_x - 1 - f(a, d)),\ P_y + (P_x - 1)]$ 1101 * If $f(a, d) \ge P_x$, then $I_3 = [P_y,\ P_y + (P_x - 1)]\ \cup\ [P_y + (2P_x - 1 - f(a, d)),\ P_y + (2P_x - 1)]$ 1102 1103 An important observation is that if $d \ge P_x$, then $f(a, d), f(b, d) \ge P_x$, and $f(a, d), f(b, d) \lt P_x$ otherwise, since $a, b \lt P_x$. So: 1104 1105 * If $d \ge P_x$, then $I_2 \cup I_3 = [P_y,\ P_y + 2P_x - 1]$ 1106 * If $d \lt P_x$, then $I_2 \cup I_3 = [P_y + P_x - 1 - f(a, d),\ P_y + P_x + f(b, d)]$ 1107 1108 So in all cases, $I_2 \cup I_3$ is exactly one interval, and its length is: $|I_2 \cup I_3| = \min\left( f(a, d) + f(b, d) + 2,\ 2P_x \right)$. 1109 1110 The other two intervals are similar, except now we XOR by $(P_y - 1)$ instead of $P_y$. We can rewrite this as $(P_x - 1) \oplus (P_y - 1) = (P_x \oplus P_y) \oplus (P_x - 1) \oplus (P_y - 1) = (P_y - 2P_x) \oplus P_x$. 1111 1112 From this we can get a similar result: 1113 1114 * If $c \ge P_x$, $I_1 \cup I_4 = [P_y - 2P_x,\ P_y - 1]$ 1115 * If $c \lt P_x$, $I_1 \cup I_4 = [P_y - P_x - 1 - f(b, c),\ P_y - P_x + f(a, c)]$ 1116 1117 So again we get exactly one interval, and $|I_1 \cup I_4| = \min\left( f(a, c) + f(b, c) + 2,\ 2P_x \right)$. 1118 1119 Notice that the two cases never intersect: 1120 1121 * $I_1 \cup I_4$ is inside $[P_y - 2P_x,\ P_y - 1]$. 1122 * $I_2 \cup I_3$ is inside $[P_y,\ P_y + 2P_x - 1]$. 1123 1124 Therefore $|S(x, y, k)| = |I_1 \cup I_4| + |I_2 \cup I_3| = \min\left(f(a, c) + f(b, c) + 2,\ 2P_x\right)\ +\ \min\left(f(a, d) + f(b, d) + 2,\ 2P_x\right)$ 1125 1126 Remember that we had assumed that $x$ and $x + k - 1$ had no common non-zero prefix bits (and same for $y$). If they do, let $X$ be that common prefix value for $x$ and $Y$ for $y$. Then every element of $S(x, y, k)$ is XORed by $X \oplus Y$. 1127 1128 However, notice that $X, Y \ge 2P_x$, since $P_x$ is the first bit that differs in $x$ and $x + k - 1$, and if we XOR by a bit after $P_x$ the values will just shift, but the size won't change. So when $x$ and $x + k - 1$ have a common prefix, we can just get rid of it without changing the size of $S$. 1129 1130 Now we can solve the original problem, where $x$ is fixed. If $P_x = P_y$ the size of always smaller than when not, so we only have to consider the case when $P_x \neq P_y$. In fact, it is always optimal to have $P_y \gt P_x$, because having a smaller $P_y$ will trigger the $2P_x$ part of the formula. 1131 1132 We have $a$ and $b$ fixed from $x$, so the formula we need to optimize is: $\min\left(f(a, c) + f(b, c) + 2,\ 2P_x\right)\ +\ \min\left(f(a, k - 2 - c) + f(b, k - 2 - c) + 2,\ 2P_x\right)$ over all $0 \le c \le k - 2$. We can easily do that with digit dp in $O(\log k)$ with a constant factor of around $100$, which solves the problem. 1133 1134 **Code** 1135 1136 ``` 1137 #include <bits/stdc++.h> 1138 1139 using namespace std; 1140 1141 template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; } 1142 1143 const long long inf = 4.1e18; 1144 const int LG = 61; 1145 1146 long long get_different(long long power, long long k, long long A) { 1147 long long B = k - A; 1148 vector<vector<long long>> dp(2, vector<long long>(16, -inf)); 1149 dp[0][0] = 0; 1150 1151 int cnt_states = 0; 1152 for(int L = LG - 1; ~L; L--) { 1153 vector<vector<long long>> ndp(2, vector<long long>(16, -inf)); 1154 1155 for(int C = 0; C < 2; C++) { 1156 for(int cd = 0; cd < 4; cd++) { 1157 int a = A >> L & 1; 1158 int b = B >> L & 1; 1159 int c = cd >> 1; 1160 int d = cd & 1; 1161 1162 int new_C = (k >> L & 1) ^ c ^ d; 1163 if((new_C + c + d >= 2) != C) continue; 1164 1165 for(int mask = 0; mask < 16; mask++) { 1166 if(dp[C][mask] < 0) continue; 1167 1168 // ac - 0, ad - 1, bc - 2, bd - 3 1169 int new_mask = mask; 1170 long long add = 0; 1171 1172 if((1ll << L) >= power && c) add += (2ll << L) - 2, new_mask |= (1 << 0) | (1 << 2); 1173 if((1ll << L) >= power && d) add += (2ll << L) - 2, new_mask |= (1 << 1) | (1 << 3); 1174 1175 if((new_mask >> 0 & 1 ^ 1) && (a & c)) add += (1ll << L + 1) - 1, new_mask |= 1 << 0; 1176 if((new_mask >> 1 & 1 ^ 1) && (a & d)) add += (1ll << L + 1) - 1, new_mask |= 1 << 1; 1177 if((new_mask >> 2 & 1 ^ 1) && (b & c)) add += (1ll << L + 1) - 1, new_mask |= 1 << 2; 1178 if((new_mask >> 3 & 1 ^ 1) && (b & d)) add += (1ll << L + 1) - 1, new_mask |= 1 << 3; 1179 1180 if(new_mask >> 0 & 1 ^ 1) add += ((long long) (a | c)) << L; 1181 if(new_mask >> 1 & 1 ^ 1) add += ((long long) (a | d)) << L; 1182 if(new_mask >> 2 & 1 ^ 1) add += ((long long) (b | c)) << L; 1183 if(new_mask >> 3 & 1 ^ 1) add += ((long long) (b | d)) << L; 1184 1185 cnt_states++; 1186 long long cand = dp[C][mask] + add; 1187 umax(ndp[new_C][new_mask], cand); 1188 } 1189 } 1190 } 1191 1192 dp = ndp; 1193 } 1194 1195 long long best = -inf; 1196 for(int mask = 0; mask < 16; mask++) { 1197 umax(best, dp[0][mask]); 1198 } 1199 return best + 4; 1200 } 1201 1202 long long get(long long x, long long k) { 1203 if(k == 1) return 1; 1204 1205 int px = __lg(x ^ x + k - 1); 1206 long long Px = 1ll << px; 1207 x &= Px * 2 - 1; 1208 1209 long long a = Px - 1 - x; 1210 return get_different(Px, k - 2, a); 1211 } 1212 1213 void solve() { 1214 long long k, x; 1215 cin >> x >> k; 1216 1217 cout << get(x, k) << '\n'; 1218 } 1219 1220 signed main() { 1221 ios_base::sync_with_stdio(0); cin.tie(0); 1222 int ttt = 1; 1223 cin >> ttt; 1224 while(ttt--) { 1225 solve(); 1226 } 1227 } 1228 ``` 1229 1230 **Rate The Problem!** 1231 1232 * Good Problem 1233 * Okay Problem 1234 * Bad Problem 1235 * Didn't Solve 1236 1237 [2190G - Maximize Determinant](/contest/2190/problem/G "Codeforces Round 1073 (Div. 1)") 1238 1239 * Idea: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 1240 * Solution: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 1241 * Editorial: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 1242 1243 **Hints** 1244 1245 **Hint 1** 1246 1247 $|\operatorname{det}(A)| \le 1$ for all $A$ and $X = 1$ for all $n$. Find an easy way to calculate the determinant. 1248 1249 **Hint 2** 1250 1251 Try to determine when the determinant is $0$. Try to calculate it $\operatorname{mod} 2$. 1252 1253 **Hint 3** 1254 1255 Add an extra column to the matrix and look at the difference array for each row. 1256 1257 **Hint 4** 1258 1259 Since each row has exactly $2$ ones now, the determinant is $0$ iff there's a cycle in a graph with $n + 1$ vertices and edges $(l_i, r_i + 1)$. In other words, the determinant is non-zero when the graph is a tree. 1260 1261 **Hint 5** 1262 1263 Determine if the determinant is $-1$ or $1$. When $l_i = r_i$ for all $i$, the determinant is a parity of a permutation, so try to transform it into that form. 1264 1265 **Hint 6** 1266 1267 Root the tree at $n + 1$, let $p_v$ be the parent of vertex $v$, and $f(v)$ be the index of the edge $(v, p_v)$. 1268 1269 Let $k$ be the number of $v$ that $p_v \lt v$, and let $q$ be the permutation with $q_{f(v)} = v$. Then $\operatorname{det}(A) = (-1)^k \cdot \operatorname{sgn}(q)$. 1270 1271 **Hint 7** 1272 1273 For the original problem, first solve when $\operatorname{det}(A) = -1$. If you change two edges, you can always swap them to negate the sign of the determinant, so it's sufficient to determine for each edge if we can negate the sign by editing it. 1274 1275 **Hint 8** 1276 1277 Try to change edge $v \rightarrow p_v$ to $u \rightarrow p_v$, where $u$ is a direct child of $v$. 1278 1279 **Hint 9** 1280 1281 If we replace $v \rightarrow p_v$ with $x \rightarrow y$, where $x$ is in the subtree of $v$ and $y$ is outside of subtree of $v$, the determinant is simply multiplied by $-1^{[v \gt p_v] + [x \gt y]}$. It is sufficient to check two extreme cases there. 1282 1283 **Hint 10** 1284 1285 If $\operatorname{det}(A) = 0$ and there are at least $3$ components, the answer is the weight of a transformed MST. 1286 1287 **Hint 11** 1288 1289 If there are exactly $2$ components, apply the same logic as in the solution for $-1$. In particular, there's a cycle and we have to change an edge in it to connect two components. 1290 1291 **Solution** 1292 1293 First let's find an easy way to calculate the determinant of a fixed $A$. We can easily see that $\operatorname{det}(A) \in [-1, 0, 1]$ for any $A$. 1294 1295 **Proof** 1296 1297 If there's no ones in the first column, the determinant is $0$. Otherwise, let $i$ be the row with $l_i = 1$ and $r_i$ being as small as possible. We can subtract this row from all others, and then expand on that row using the Cramer's rule. This multiplies the determinant by $-1$ or $1$ and get rids of one row and one column, so we can apply induction. 1298 1299 Let's first of all understand when it is $0$, so in other words we need to find if the determinant is even. 1300 1301 Notice that replacing each row with its difference array is a linear transformation, because we can set $a_{i, j} = a_{i, j} - a_{i, j - 1}$ for all $j$ simultaneously, and do that for all $i$ from the end. 1302 1303 Therefore, let's add an extra column so that the matrix is $n$ by $n + 1$ now, and replace each row with its difference array. Now every row has exactly one $1$ and exactly one $-1$, or exactly two $1$'s when looked at $\operatorname{mod} 2$. 1304 1305 So we have $n$ binary strings of size $n + 1$ with two $1$'s in each string and we want to determine if they are linearly independent. 1306 1307 The solution to this is known, and the strings are linearly independent iff there are no cycles in a graph with $n + 1$ vertices and $n$ edges $(x_i, y_i)$. 1308 1309 Therefore, the determinant is $0$ iff there is a cycle in a graph with $n + 1$ vertices and $n$ edges $(l_i, r_i + 1$) (since each row got replaced with a difference array, so the last $1$ shifted to a $-1$ in the next index). 1310 1311 If the graph is a tree, the determinant is $1$ or $-1$. Let's learn to determine which one it is. 1312 1313 Notice that if $l_i = r_i$ for all $i$, the determinant is the parity of a permutation, so it clearly can't be simplified beyond that, so let's try to get it down to that. 1314 1315 Let's try to transform the matrix into a permutation. Consider the following matrix: 1316 1317 $ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & -1 \\ 1 & 0 & -1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & -1 & 0 \\ 0 & 0 & 1 & -1 & 0 & 0 \\ 1 & -1 & 0 & 0 & 0 & 0 \\ \end{bmatrix} $ 1318 1319 The tree of this matrix looks like this: 1320 1321 **Picture** 1322 1323  1324 1325 Denote $p_v$ as the parent of vertex $v$, $f(v)$ as the index of a row with $v$ and $p_v$. If $p_v = n + 1$ holds for all $v$, $p_v$ has a $-1$ and $v$ has $1$ at $f(v)$-th row, we are simply in a case of a permutation that was discussed earlier, so let's transform the matrix into that. 1326 1327 Let's make it so $p_v$ has a $-1$ and $v$ has $1$, so multiply $f(v)$-th row by $-1$ if $p_v \lt v$: 1328 1329 **Picture** 1330 1331  1332 1333 Now we can iteratively move $p_v \neq n + 1$ to $p_{p_v}$ by adding $f(p_v)$ to $f(v)$. For example, in the picture above for $v = 4$ we add $i = 1$ to $i = 4$ and get a new tree: 1334 1335 **Picture** 1336 1337  1338 1339 This way we can transform the matrix to have $p_v = n + 1$: 1340 1341 **Operations** 1342 1343 $ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & -1 \\ 1 & 0 & -1 & 0 & 0 & 0 \\ -1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & -1 & 1 & 0 & 0 \\ -1 & 1 & 0 & 0 & 0 & 0 \\ \end{bmatrix} 1344 1345 \xrightarrow{v = 4,\ r_4 \leftarrow r_4 + r_1} $ $ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & -1 \\ 1 & 0 & -1 & 0 & 0 & 0 \\ -1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & -1 \\ -1 & 1 & 0 & 0 & 0 & 0 \\ \end{bmatrix} 1346 1347 \xrightarrow{v = 2,\ r_5 \leftarrow r_5 + r_2} $ $ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & -1 \\ 1 & 0 & -1 & 0 & 0 & 0 \\ -1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & -1 \\ 0 & 1 & -1 & 0 & 0 & 0 \\ \end{bmatrix} 1348 1349 \xrightarrow{v = 5,\ r_3 \leftarrow r_3 + r_2} $ $ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & -1 \\ 1 & 0 & -1 & 0 & 0 & 0 \\ 0 & 0 & -1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & -1 \\ 0 & 1 & -1 & 0 & 0 & 0 \\ \end{bmatrix} 1350 1351 \xrightarrow{v = 1,\ r_2 \leftarrow r_2 + r_1} $ $ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & -1 \\ 1 & 0 & 0 & 0 & 0 & -1 \\ 0 & 0 & -1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & -1 \\ 0 & 1 & -1 & 0 & 0 & 0 \\ \end{bmatrix} 1352 1353 \xrightarrow{v = 3,\ r_3 \leftarrow r_3 + r_1} $ $ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & -1 \\ 1 & 0 & 0 & 0 & 0 & -1 \\ 0 & 0 & 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 1 & 0 & -1 \\ 0 & 1 & -1 & 0 & 0 & 0 \\ \end{bmatrix} 1354 1355 \xrightarrow{v = 5,\ r_5 \leftarrow r_5 + r_1} $ $ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & -1 \\ 1 & 0 & 0 & 0 & 0 & -1 \\ 0 & 0 & 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 1 & 0 & -1 \\ 0 & 1 & 0 & 0 & 0 & -1 \\ \end{bmatrix} $ 1356 1357 At the end we end up with a $p_v = n + 1$ for all $v$, and since the last column doesn't actually exist in the matrix, the matrix is just a permutation, and we can find its sign. 1358 1359 Notice an imporant fact: during our operations $f(v)$ didn't change, only $p_v$ did, so at the end we will always end up with the permutation $q$ of size $n$ with $q_{f(v)} = v$. 1360 1361 To sum it up, to find the sign of $A$: 1362 1363 Let $k$ be the number of $v$ that $p_v \lt v$, and let $q$ be the permutation with $q_{f(v)} = v$. Then $\operatorname{det}(A) = (-1)^k \cdot \operatorname{sgn}(q)$. 1364 1365 Now let's use this formula to solve the original problem. We have to make $A$ has a determinant of $1$. Obviously, if it's already $1$, the answer is $0$. 1366 1367 Let's first solve the case when it's $-1$. Notice an important fact: if we modify two rows, we can simply swap them, and that negates the determinant. 1368 1369 So the upperbound on the answer is the sum of two smallest values of $a_i$. We now simply have to determine the smallest cost of an edge that can negate the determinant on it's own. 1370 1371 Root the tree at $n + 1$ again, we delete the $i$-th edge $v \rightarrow p_v$, and replace it with an edge $x \rightarrow y$, where $x$ is a **direct** child of $v$. Assume that $f(x) = j$. How does the determinant change? 1372 1373 Notice that besides $i$, only the direction of edge $j$ changes. In particular, the edge $x \rightarrow v$ changes to $v \rightarrow x$, and $i$-th edge is now $x \rightarrow y$. 1374 1375 How does $q$ change? Before the operation, $q_i = v$ and $q_j = x$, now $q_i = x$ and $q_j = v$, so it swaps $q_i$ and $q_j$, which negates the sign. Additionally, since $j$-th edge was reversed, the value of $-1^{[x \gt v]}$ changed to $-1^{[v \gt x]}$, so this part was negated as well. 1376 1377 Therefore, the only change in determinant is: $-1^{[v \gt p_v] + [x \gt y]}$. We can iteratively apply this to get the same result for when $x$ is not a child of $v$. 1378 1379  1380 1381 Therefore, if we replace $v \rightarrow p_v$ with $x \rightarrow y$, where $x$ is in the subtree of $v$ and $y$ is outside of subtree of $v$, the determinant is multiplied by $-1^{[v \gt p_v] + [x \gt y]}$. 1382 1383 This means that we can change the sign of determinant if the values of $[v \gt p_v]$ and $[x \gt y]$ are different. 1384 1385 Let $\max_v$ be the largest value in the subtree of $v$, and $\min_v$ the smallest value **outside** of the subtree of $v$. Then we can use the edge $v \rightarrow p_v$ to change the sign iff $\max_v \gt \min_v$, because if we choose $x = v$, $y = n + 1$, the sign is going to be different compared to when we choose $x = \max_v$, $y = \min_v$. 1386 1387 We can use this to determine if we can change the sign with an edge $i$ and find the smallest cost of one which we can use. This solves the case when the determinant is $-1$. 1388 1389 Now the only thing left is to solve when the determinant is $0$. Our graph is not a tree now. 1390 1391 Notice that if there are at least $3$ components, we have to change at at least $2$ edges, so we don't have to worry about the sign, since we can swap two edges if needed like we did in the previous case. 1392 1393 So we simply have to make the graph a tree while changing a subset of edges with the smallest total cost, which is precisly the MST problem (slightly modified). 1394 1395 The only case left is when the graph consists of two components. We can actually use the exact same observations as in the $\operatorname{det}(A) = -1$. There's a cycle, we have to remove one edge from it and connect the components. We can also change two edges, but at least one of them has to be in the cycle. 1396 1397 In the first case we have to check if the smallest value in the component with $n + 1$ is smaller than the largest value in the other component, and if so, we can choose any edge on the cycle. Otherwise, we have to apply the same logic as we did earlier. 1398 1399 Final time complexity: $O(n \log n)$ due to sorting for finding MST. 1400 1401 **Code** 1402 1403 ``` 1404 #include <bits/stdc++.h> 1405 1406 using namespace std; 1407 1408 const long long inf = 1e18; 1409 1410 struct DSU { 1411 int n; 1412 vector<int> p, siz; 1413 int comp; 1414 1415 DSU(int N) { 1416 n = N - 1; 1417 comp = 0; 1418 p = vector<int>(n + 1); 1419 siz = vector<int>(n + 1); 1420 }; 1421 1422 void create(int x) { 1423 p[x] = x; 1424 siz[x] = 1; 1425 comp++; 1426 } 1427 1428 void init() { 1429 comp = 0; 1430 for(int v = 1; v <= n; v++) create(v); 1431 } 1432 1433 int get(int x) { 1434 return p[x] = (p[x] == x? x : get(p[x])); 1435 } 1436 1437 bool unite(int x, int y) { 1438 x = get(x), y = get(y); 1439 if(x == y) return 0; 1440 if(siz[x] < siz[y]) swap(x, y); 1441 comp--; 1442 siz[x] += siz[y]; 1443 p[y] = x; 1444 return 1; 1445 } 1446 }; 1447 1448 int get_cycles(vector<int> p) { 1449 int n = p.size(); 1450 1451 vector<int> used(n); 1452 int cnt = 0; 1453 for(int i = 0; i < n; i++) { 1454 if(used[i]) continue; 1455 1456 int j = i; 1457 while(!used[j]) { 1458 used[j] = 1; 1459 j = p[j]; 1460 } 1461 1462 cnt++; 1463 } 1464 1465 return cnt; 1466 } 1467 1468 long long solve_zero(vector<array<int, 3>> a) { 1469 int n = (int) a.size(); 1470 int N = n + 1; 1471 vector<vector<array<int, 3>>> g(N + 1); 1472 for(int i = 0; i < n; i++) { 1473 auto [u, v, w] = a[i]; 1474 g[u].push_back({v, w, i}); 1475 g[v].push_back({u, w, i}); 1476 } 1477 vector<pair<int, int>> parent(N + 1); 1478 vector<int> used(N + 1), d(N + 1); 1479 1480 int extra_edge = -1; 1481 function<void(int, int)> dfs = [&](int v, int p) { 1482 used[v] = 1; 1483 for(auto [to, w, idx] : g[v]) { 1484 if(to == p) continue; 1485 if(used[to]) { 1486 extra_edge = idx; 1487 continue; 1488 } 1489 1490 parent[to] = {v, idx}; 1491 d[to] = d[v] + 1; 1492 dfs(to, v); 1493 } 1494 }; 1495 dfs(N, 0); dfs(1, 0); 1496 1497 assert(extra_edge != -1); 1498 parent[1] = {N, extra_edge}; 1499 1500 int sign = 1; 1501 vector<int> p(n); 1502 for(int v = 1; v <= n; v++) { 1503 auto [u, idx] = parent[v]; 1504 p[idx] = v - 1; 1505 if(v > u) sign *= -1; 1506 } 1507 int cnt_cycles = get_cycles(p); 1508 if((n - cnt_cycles) & 1) sign = -sign; 1509 1510 long long ans = inf; 1511 int best_idx = extra_edge; 1512 if(sign == 1) ans = min(ans, (long long) a[extra_edge][2]); 1513 1514 int v = a[extra_edge][0]; 1515 int u = a[extra_edge][1]; 1516 if(d[v] < d[u]) swap(u, v); 1517 1518 int prev = u; 1519 while(v != u) { 1520 auto [par, idx] = parent[v]; 1521 1522 // Delete (v, p) 1523 // Add (v, prev) 1524 sign *= -1; 1525 if(v > par) sign *= -1; 1526 if(v > prev) sign *= -1; 1527 if(sign == 1) ans = min(ans, (long long) a[idx][2]); 1528 1529 if(a[idx][2] < a[best_idx][2]) best_idx = idx; 1530 1531 prev = v; 1532 v = par; 1533 } 1534 1535 long long two_operations = inf; 1536 for(int i = 0; i < n; i++) { 1537 if(i != best_idx) two_operations = min(two_operations, (long long) a[i][2]); 1538 } 1539 two_operations += a[best_idx][2]; 1540 ans = min(ans, two_operations); 1541 1542 return ans; 1543 } 1544 1545 long long get(vector<array<int, 3>> a) { 1546 int n = (int) a.size(); 1547 1548 int N = n + 1; 1549 for(auto &[l, r, w] : a) r++; 1550 1551 auto edges = a; 1552 for(auto &[u, v, w] : edges) { 1553 swap(u, w); 1554 } 1555 sort(edges.rbegin(), edges.rend()); 1556 1557 DSU dsu(N + 1); 1558 dsu.init(); 1559 long long ans = 0; 1560 for(auto [w, u, v] : edges) { 1561 if(!dsu.unite(u, v)) ans += w; 1562 } 1563 1564 if(dsu.comp > 1) { 1565 if(dsu.comp > 2) return ans; 1566 else { 1567 int cnt_other = 0, max_other = 0; 1568 for(int v = 1; v <= N; v++) { 1569 if(dsu.get(N) != dsu.get(v)) { 1570 cnt_other++; 1571 max_other = max(max_other, v); 1572 } 1573 } 1574 1575 if(cnt_other < max_other) return ans; 1576 return solve_zero(a); 1577 } 1578 } 1579 1580 vector<vector<array<int, 3>>> g(N + 1); 1581 for(int i = 0; i < n; i++) { 1582 auto [u, v, w] = a[i]; 1583 g[u].push_back({v, w, i}); 1584 g[v].push_back({u, w, i}); 1585 } 1586 vector<pair<int, int>> parent(N + 1); 1587 vector<int> sz(N + 1, 1), max_dp(N + 1), weight(N + 1); 1588 1589 function<void(int, int)> dfs = [&](int v, int p) { 1590 max_dp[v] = v; 1591 1592 for(auto [to, w, idx] : g[v]) { 1593 if(to == p) continue; 1594 1595 parent[to] = {v, idx}; 1596 weight[to] = w; 1597 dfs(to, v); 1598 sz[v] += sz[to]; 1599 max_dp[v] = max(max_dp[v], max_dp[to]); 1600 } 1601 }; 1602 dfs(N, 0); 1603 1604 int sign = 1; 1605 vector<int> p(n); 1606 for(int v = 1; v <= n; v++) { 1607 auto [u, idx] = parent[v]; 1608 p[idx] = v - 1; 1609 if(v > u) sign *= -1; 1610 } 1611 int cnt_cycles = get_cycles(p); 1612 if((n - cnt_cycles) & 1) sign = -sign; 1613 1614 ans = inf; 1615 if(sign == 1) ans = 0; 1616 else { 1617 reverse(edges.begin(), edges.end()); 1618 ans = edges[0][0] + edges[1][0]; 1619 1620 for(int v = 1; v < N; v++) { 1621 if(sz[v] < max_dp[v]) ans = min(ans, (long long) weight[v]); 1622 } 1623 } 1624 1625 return ans; 1626 } 1627 1628 void solve() { 1629 int n; 1630 cin >> n; 1631 vector<array<int, 3>> a(n); 1632 for(auto &[l, r, w] : a) { 1633 cin >> l >> r >> w; 1634 } 1635 1636 long long ans = get(a); 1637 cout << ans << '\n'; 1638 } 1639 1640 signed main() { 1641 ios_base::sync_with_stdio(0); cin.tie(0); 1642 int ttt = 1; 1643 cin >> ttt; 1644 while(ttt--) { 1645 solve(); 1646 } 1647 } 1648 ``` 1649 1650 **Rate The Problem!** 1651 1652 * Good Problem 1653 * Okay Problem 1654 * Bad Problem 1655 * Didn't Solve