codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![ ](/predownloaded/11/99/119980c34c8a2c4ab1fadc4b9d017bad9d3fbc6c.png)
    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 ![ ](/predownloaded/9b/a6/9ba61c80911c1b754f802109487b5fcc5e27a263.png)
    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 ![ ](/predownloaded/4f/3a/4f3a0669cc8919b662573dba320c4667be3d424f.png)
    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 ![ ](/predownloaded/5d/a9/5da994c0a48dd74e122dd6f49f3f0bb05f2e3bcf.png)
    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 ![ ](/predownloaded/9a/1a/9a1aaa2c4b6c8609396d779633e83c4c45a5310b.png)
   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 ![ ](/predownloaded/c3/be/c3be67217ab3c171787048af8afa7845f67fa30f.png)
   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 ![ ](/predownloaded/f9/ae/f9aef4015162b7321fd3ef5c7ce2427e81c985dd.png)
   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 ![ ](/predownloaded/24/61/2461d7d3e8149f7fea4d490af6cc74da1bb03aa8.png)
   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