codeforces-scrape

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

2210.md (37221B)


      1 Source: https://codeforces.com/blog/entry/152413
      2 
      3 Thank you for participating in our round. We apologise for C2 being too hard compared to C1.
      4 
      5 UPD : Added an alternative solution to B, which contains the original solution with a diagram for better understanding.
      6 
      7 [2210A - A Simple Sequence](/contest/2210/problem/A "Codeforces Round 1089 (Div. 2)")
      8 
      9 Idea: [ritam1234](/profile/ritam1234 "Expert ritam1234"), Preparation: [ritam1234](/profile/ritam1234 "Expert ritam1234")
     10 
     11 **Solution**
     12 
     13 We observe that
     14 
     15 $x \bmod (x-1) = \begin{cases} 1 & \text{if } x \gt 2 \\ 0 & \text{if } x = 2 \end{cases}$
     16 
     17 Now observe that the sequence $n, n-1, \dots, 1$ satisfies the problem's condition (since $1 \ge 1 \ge \dots \ge 0$).
     18 
     19 Hence, the sequence $n, n-1, \dots, 1$ works.
     20 
     21 [2210B - Simply Sitting on Chairs](/contest/2210/problem/B "Codeforces Round 1089 (Div. 2)")
     22 
     23 Idea: [ritam1234](/profile/ritam1234 "Expert ritam1234"), Preparation: [ritam1234](/profile/ritam1234 "Expert ritam1234"), [Argentum47](/profile/Argentum47 "Expert Argentum47")
     24 
     25 **Hint 1**
     26 
     27 Suppose the game ends at chair $k$ (or chair $n+1$ if the game ends after successfully visiting the $n-th$ chair) , try to find the maximum number of chairs you can visit as a function of $k$.
     28 
     29 **Solution**
     30 
     31 We hope you have read the hint because the solution continues from that.
     32 
     33 The maximum number of chairs which you can visit if your game ends at chair $k$ is given by $\left| { i : 1 \le i \lt k, p_i \le i \ or \ p_i \ge k } \right|$. We can obviously visit all chairs such that $p_i\le i$ and we can also visit all chairs with $p_i\ge k$ because since our game ends at chair $k$, marking any chair from $k,k+1,k+2,\ldots n$ would not matter.
     34 
     35 Let's call this function $f(k)$. So our answer is given by  
     36 $max\left(f(k)\right)\forall k \; , \; 1 \le k \le n+1$.
     37 
     38 For now consider $k \lt n+1$.
     39 
     40 Let $ct$ denote the count of chairs such that $p_i\ge k,i \lt k$.
     41 
     42 Now according to exchange argument, there should be atleast $ct$ chairs to right of k such that $p_i\le i$, i.e., $count\left(p_i\le i,k\le i\le n\right)\ge ct$
     43 
     44 Therefore it is always optimal to choose $k=n+1$ for sitting on the maximum number of chairs possible.
     45 
     46 Thus the answer is count of indices such that $p_i\le i$.
     47 
     48 You can refer to the following for a better idea of the exchange argument, credits [dipamsen](/profile/dipamsen "Specialist dipamsen")
     49 
     50 **Solution-2**
     51 
     52 ![image](/predownloaded/5d/cd/5dcd815956459c00b52766212937932bb030856b.png)
     53 
     54 [2210C1 - A Simple GCD Problem (Easy Version)](/contest/2210/problem/C1 "Codeforces Round 1089 (Div. 2)")
     55 
     56 Idea: [simplelife](/profile/simplelife "Expert simplelife"), Preparation: [Argentum47](/profile/Argentum47 "Expert Argentum47")
     57 
     58 **Hint 1**
     59 
     60 Do we really need to consider all subarrays?
     61 
     62 **Hint 2**
     63 
     64 We only need to consider adjacent elements of the array.
     65 
     66 **Hint 3**
     67 
     68 Let's say we have gcd($a_{i-1}, a_{i}$) and gcd($a_{i}, a_{i+1}$), What is the minimum possible value of $a_i$ satisfying this.
     69 
     70 **Solution**
     71 
     72 Since $b_i \le a_i$, the problem essentially asks for the number of indices $i$ where $a_i$ can be strictly decreased ($b_i \lt a_i$) without changing the GCD of any subarray.
     73 
     74 **Claim**: To preserve the GCD of all subarrays, it is sufficient to preserve the GCD of all adjacent elements (subarrays of length 2).
     75 
     76 **Proof**: Assume we modify the array such that the GCD of adjacent elements remains unchanged for all $i$. We can show this preserves the GCD of any subarray of length $k \ge 3$. For a subarray of length 3, using the properties of the GCD operator, we know that,
     77 
     78 $ \gcd(a_i, a_{i+1}, a_{i+2}) = \gcd(\gcd(a_i, a_{i+1}), \gcd(a_{i+1}, a_{i+2})) $
     79 
     80 Since the GCD of adjacent elements is preserved by our assumption, the GCD of the triplet is also preserved. By induction, we can show that this holds for all subarrays of length $\ge 2$.
     81 
     82 Now for each element $a_i$ ($1 \lt i \lt n$) let,
     83 
     84 $A = \gcd(a_{i-1}, a_i) \quad \text{and} \quad B = \gcd(a_i, a_{i+1})$
     85 
     86 For $a_i$ to maintain these GCDs, it must be a multiple of both $A$ and $B$. The smallest such value is $\text{lcm}(A, B)$. $a_i$ can only be reduced iff $\text{lcm}(A, B) \lt a_i$. For the endpoins, we need to consider only one adjacent pair. For $a_1$, it can be reduced iff $\gcd(a_1, a_2) \lt a_1$ and for $a_n$, it can be reduced iff $\gcd(a_{n-1}, a_n) \lt a_n$.
     87 
     88 The answer is just the number of indices that can be reduced. The time complexity is $O(n \log(\max a_i))$.
     89 
     90 [2210C2 - A Simple GCD Problem (Hard Version)](/contest/2210/problem/C2 "Codeforces Round 1089 (Div. 2)")
     91 
     92 Idea: [simplelife](/profile/simplelife "Expert simplelife"), Preparation: [Argentum47](/profile/Argentum47 "Expert Argentum47")
     93 
     94 Thanks to [Intellegent](/profile/Intellegent "Grandmaster Intellegent") for misreading $C1$ and [Argentum47](/profile/Argentum47 "Expert Argentum47") for fully solving it.
     95 
     96 **Hint 1**
     97 
     98 If you are able to set the value at a particular index < $a_i$, do it.
     99 
    100 **Hint 2**
    101 
    102 What can you say about remaining indices whose value is unchanged?
    103 
    104 **Hint 3**
    105 
    106 We can only increase the value of the indices with unchanged values, and while increasing, we can only change them to their multiples
    107 
    108 **Hint 4**
    109 
    110 Do we need to consider all multiples? No!
    111 
    112 **Hint 5**
    113 
    114 We only need to consider prime multiples. Do we need to consider all prime multiples? No!
    115 
    116 **Hint 6**
    117 
    118 We only need to consider first few prime multiples, 20 should suffice, but why?
    119 
    120 **Hint 7**
    121 
    122 Note that as discussed in previous part, we only need to consider adjacent elements. How can we use this to implement our logic?
    123 
    124 **Hint 8**
    125 
    126 Use $dp$!. Let $dp[i][j]$ denotes max changes till index $i$, if we multiply index $i$ by $j^{th}$ prime.
    127 
    128 **Solution**
    129 
    130 Refer to the editorial of C1 first. We consider only indices $i$ ($1 \lt i \lt n$). For the endpoints, we can do a similar analysis as well. Let $A = \gcd(a_i, a_{i-1})$ and $B = \gcd(a_i, a_{i+1})$.
    131 
    132 First of all, it is trivial to observe that if $b_i \lt \text{lcm}(A, B)$, or if $ a_i = lcm(A,B)$. It is impossible to "reduce" the value of $a_i$, we can only increase it. Furthermore, if we can reduce the value of $a_i$, it is optimal to always reduce it to minimum possible value.
    133 
    134 Now lets consider the unchanged values so far. They fall in either of the $2$ categories: $\text{lcm}(A,B) \gt b_i$ $\text{lcm}(A,B) = a_i$
    135 
    136 If an index falls in category $1$, it is easy to see that it is impossible to change it without altering subarray GCD. However if the index falls in category $2$, then we can multiply it by some number $x$ such that $a_i \cdot x \lt b_i$ and GCD is preserved.
    137 
    138 It is easy to see that it is optimal to choose a prime number as $x$, since any composite number can be written as product of primes, and choosing either of those primes will result in same subarray GCD.
    139 
    140 Now notice that we can only choose prime numbers which are NOT a factor of $a_{i-1}/ \gcd(a_i, a_{i-1})$ and $a_{i+1}/\gcd(a_i, a_{i+1})$, since if the prime number was present in those values, the subarray GCD will increase.
    141 
    142 Also notice that we don't have to consider all the primes, just the first $20$ prime numbers will do, since it can be easily seen that the product of first $20$ primes > $10^{18}$. This is important because the product of adjacent elements can be atmost $10^{18}$, and hence cannot cover all these primes.
    143 
    144 Now we can use dp to solve from here, where $dp[i][j]$ = maximum number of changes in array from index $1$ to $i$, if we multiply $a_i$ with $j$. Also for $j = 0$, define $dp[i][0]$ = maximum number of changes in array from index $1$ to $i$, if we keep a[i] unchanged. Initially assign all values negative infinity.
    145 
    146 Create a new array $c_i$, such that $c_i = \text{lcm}(A,B)$ for all $i$. Furthermore, if ($c_i \gt b_i$), set $c_i = a_i$ only. The reason for this is that if $a_i$ can be successfully reduced, then we just use that value in our analysis. Else we use $a_i$ only.
    147 
    148 Now lets focus on base case. For $i = 0$, if $c_0 \neq a_0$, then $dp[0][0] = 1$, else $dp[0][0] = 0$. Now for $j = 1$ to $j = 20$, let $x = c_i \cdot p_j$. if $x \leq b_0$ and gcd($x, c_1$) = gcd($a_0, a_1$), and $x \neq a_0$ then multiplying is a valid option, and hence set $dp[0][j] = 1$, else it is invalid and let it stay negative infinity. We take gcd($x, c_1$) here and in subsequent test cases as well, since we want to consider the least possible value in next index, to minimize prime collisions.
    149 
    150 Now for remaining indices, let's say we multiplied previous element by $k^{th}$ prime, and are trying to multiply the current element with $j^{th}$ prime, then the following conditions must hold true (let $x = c_i \cdot p_j$ and $y = c_{i-1} \cdot p_k$)
    151 
    152 1. $x \le b_i$
    153 2. gcd($x, c_{i+1}$) = gcd($a_i, a_{i+1}$)
    154 3. gcd($x, y$) = gcd($a_i, a_{i-1}$)
    155 4. $x \neq a_i$
    156 
    157 If these $4$ conditions hold, then multiplying by $j$ is a valid combination, considering we multiplied previous number by $k$. In this case the answer will be $dp[i][j]$ = max($dp[i][j], dp[i-1][k] + 1$).
    158 
    159 Note that we will handle $j = 0$ case explicitly, by setting $dp[i][0] = \text{max}_k(dp[i-1][k]) + 1$ if $c_i \lt a_i$, and $dp[i][0] = \text{max}_k(dp[i-1][k]$, otherwise. This is to ensure we always have a valid transition (number is unchanged) in case of impossibility, (the case where $a_i$ can never be changed) and dp[i] values are not just all negative infinity in that case. (Basically even if we can't change the value, we have to keep the number as $a_i$ only).
    160 
    161 The overall time complexity of this logic is $O(n \cdot L^{2} \cdot log(max(A_i)))$, where $L$ is the number of primes used in our logic. This comfortably passes within the time constraints, in both python and cpp. For larger L, like 25-30, some basic optimizations, like exiting the loop if $c_i \cdot p_j \gt b_i$ might be required depending on the implementation.
    162 
    163 **Additional Challenge**
    164 
    165 What we described was the simplest solution to this problem that passes comfortably within these time constraints. Can you find a more efficient algo, which lets say passes comfortably for $n = 2 \cdot 10^{5}$ and for $n = 10^{6}$.
    166 
    167 **Code(C++)**
    168 
    169 ```
    170 #include <bits/stdc++.h>
    171 using namespace std; 
    172 typedef long long ll;
    173 
    174 void solve()
    175 {
    176     ll n;
    177     cin >> n;
    178     vector<ll> a(n), b(n), c(n);
    179     for(ll i = 0; i < n; i++) cin >> a[i];
    180     for(ll i = 0; i < n; i++) cin >> b[i];
    181     vector<ll> primes = {1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73};
    182     for(ll i = 0; i < n; i++)
    183     {
    184         if (i == 0) c[i] = gcd(a[i], a[i+1]);
    185         else if (i == n-1) c[i] = gcd(a[i-1], a[i]);
    186         else c[i] = lcm(gcd(a[i], a[i-1]), gcd(a[i], a[i+1]));
    187  
    188         if (c[i] > b[i]) c[i] = a[i];
    189     }
    190     ll L = primes.size();
    191     vector<vector<ll>> dp(n, vector<ll>(L, -1e18));
    192  
    193     //set up the base cases
    194     for(ll i = 0; i < L; i++)
    195     {
    196         if (i == 0)
    197         {
    198             if (c[0] == a[0]) dp[0][0] = 0;
    199             else dp[0][0] = 1;
    200             continue;
    201         }
    202         ll val = c[0] * primes[i];
    203         if (val <= b[0] and gcd(val, c[1]) == gcd(a[0], a[1]) and val != a[0]) dp[0][i] = 1; 
    204     }
    205     
    206     //make the transitions
    207     for(ll i = 1; i < n; i++)
    208     {
    209         for(ll j = 0; j < L; j++)
    210         {
    211             for(ll k = 0; k < L; k++)
    212             {
    213                 //j = 0, special case, we are keeping value unchanged, and always want something to be assigned here
    214                 if (j == 0)
    215                 {
    216                     if (c[i] == a[i]) dp[i][j] = max(dp[i][j], dp[i-1][k]);
    217                     else dp[i][j] = max(dp[i][j], dp[i-1][k]+1);
    218                     continue;
    219                 }
    220                 //we check for all conditions, that multiplying this by prime j and prev by prime k keeps everything in check
    221                 ll val1 = c[i] * primes[j];
    222                 ll val2 = c[i-1] * primes[k];
    223                 if (val1 <= b[i] and gcd(val1, val2) == gcd(a[i], a[i-1]) and val1 != a[i])
    224                 {
    225                     if (i < n-1)
    226                     {
    227                         if (gcd(val1, c[i+1]) == gcd(a[i], a[i+1])) dp[i][j] = max(dp[i][j], dp[i-1][k] + 1);
    228                     }
    229                     else dp[n-1][j] = max(dp[n-1][j], dp[n-2][k] + 1);
    230                 }
    231             }
    232         }
    233     }
    234     cout << max(0LL, *max_element(dp[n-1].begin(), dp[n-1].end())) << '\n';
    235 }
    236  
    237 int main()
    238 {
    239     ll n = 1;
    240     cin >> n;
    241     while(n--) solve();
    242     return 0;
    243 }
    244 ```
    245 
    246 [2210D - A Simple RBS Problem](/contest/2210/problem/D "Codeforces Round 1089 (Div. 2)")
    247 
    248 Idea: [simplelife](/profile/simplelife "Expert simplelife"), Preparation: [simplelife](/profile/simplelife "Expert simplelife")
    249 
    250 Thanks to [awesomeguy856](/profile/awesomeguy856 "Grandmaster awesomeguy856") for helping me in writing the editorial for this problem.
    251 
    252 **Hint 1**
    253 
    254 Think of some invariants.
    255 
    256 **Hint 2**
    257 
    258 Notice that the operation performed is reversible, so if you can convert $s$ to $t$ , you can also convert $t$ to $s$.
    259 
    260 **Solution**
    261 
    262 First, consider the tree representations of $"("+s+")"$ and $"("+t+")"$. The tree representation of an $RBS$ can be found with a stack, where each bracket pair is a node, and its parent is the bracket pair at the top of the stack when it is initially added.
    263 
    264 The swapping operation becomes the following on a tree: Either
    265 
    266 1. Take two nodes $u$ and $v$ and swap the subtrees of a contiguous range of children of u with the disjoint subtrees of a contiguous range of children of $v$.
    267 2. Swap the subtrees of two disjoint contiguous ranges of children of $u$ for any $u$.
    268 
    269 We observe two invariants in this process
    270 
    271 1. the number of leafs (since entire subtrees are swapped, no new leafs are generated and no leafs are destroyed)
    272 2. the depth of the highest node u with multiple children (or the lack thereof). This is because for any node v in the fixed chain above u, no swaps can be made as every non-fixed node is in the subtree of the only child of $v$. Furthermore, u will always have multiple children: if at any point $u$ has only 1 child, then reversing the operations would turn a fixed node into a nonfixed node, contradicting the previous sentence.
    273 
    274 If these two invariants differ between $s$ and $t$, we immediately know the answer is NO, and these conditions can be checked easily on a tree.
    275 
    276 We claim that if $s$ and $t$ have the same values for these invariants, then it is sufficient for the answer to be YES.
    277 
    278 **Proof**:
    279 
    280 Let $u$ be the highest node with multiple children (i.e. the lowest fixed node). Consider the process of turning the number of children of $u$ into the number of leafs. If the number of children of $u$ is less than the number of leafs, then there must exist a lower node $v$ that has multiple children. Swap the subtrees of the children of $v$ with the subtree of any child of $u$ that is not the ancestor of $v$. Then, the number of children of $u$ has increased. Continuing this process eventually leads a tree where $u$ is the only node with multiple children (a bunch of chains attached to $u$). Then, we make it so that only the leftmost child $c$ of $u$ is allowed to have a child. If any other child $v$ of $u$ has a child, then swap the subtree of $v$ with the lowest node in the chain attached to $u$. Then, $v$ is replaced with a leaf. Continuing this process turns every child of $u$ besides $c$ into a leaf, as desired.
    281 
    282 This process ends with a unique tree based on the two invariants we found, so both $s$ and $t$ can reach this tree through some swaps. Since operations are reversible, $s$ can be transformed into this tree, then be transformed into $t$. So the answer is YES.
    283 
    284 **Code(C++)**
    285 
    286 ```
    287 #include<bits/stdc++.h>
    288 using namespace std;
    289  
    290 void solve(){
    291     int n;
    292     cin>>n;
    293     string s,t;
    294     cin>>s>>t;
    295     auto count_adjacent_pairs = [](string &s) -> int {
    296         int m=s.size();
    297         int ct=0;
    298         for(int i=0;i<m-1;i++){
    299             if(s[i]=='(' and s[i+1]==')')ct++;
    300         }
    301         return ct;
    302     };
    303     auto count_outer_brackets = [](string &s) -> int {
    304         int m=s.size();
    305         vector<int> match(m,-1);
    306         stack<int> indices;
    307         for(int i=0;i<m;i++){
    308             if(s[i]==')'){
    309                 match[indices.top()]=i;
    310                 indices.pop();
    311             }
    312             else{
    313                 indices.push(i);
    314             }
    315         }
    316         int ct=0;
    317         int l=0,r=m-1;
    318         while(match[l]==r){
    319             l++;
    320             r--;
    321             ct++;
    322         }
    323         return ct;
    324     };
    325     if(count_adjacent_pairs(s)==count_adjacent_pairs(t) and count_outer_brackets(s)==count_outer_brackets(t)){
    326         cout<<"YES\n";
    327         return;
    328     }
    329     cout<<"NO\n";
    330 }
    331  
    332 int main(){
    333     int t;
    334     cin>>t;
    335     while(t--){
    336         solve();
    337     }
    338     return 0;
    339 }
    340 ```
    341 
    342 [2210E - Binary Strings are Simple?](/contest/2210/problem/E "Codeforces Round 1089 (Div. 2)")
    343 
    344 Idea: [Argentum47](/profile/Argentum47 "Expert Argentum47"), [simplelife](/profile/simplelife "Expert simplelife"), Preparation: [ritam1234](/profile/ritam1234 "Expert ritam1234"), [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__"), [Argentum47](/profile/Argentum47 "Expert Argentum47")
    345 
    346 Thanks to [wuhudsm](/profile/wuhudsm "Expert wuhudsm") for buffing this problem.
    347 
    348 **Part 1 Hint**
    349 
    350 Consider a binary string of length $n$. Cyclically rotating the string to the left removes the character from front and places it on the back. Analyse the change in inversions modulo n if the front character is '$0$' and do the same for '$1$'.
    351 
    352 **Part 1 Solution**
    353 
    354 Let $c_1 =$ number of $1$'s in the binary string and $c_0 =$ count of $0$'s in the binary string.
    355 
    356 Lets consider the inversions due to each individual $0$ and $1$ in the string. Lets say at index $i$, we have a $1$. Then the number of inversions caused by it = number of $0$s in the binary string from index $i+1$ to $n$. If we have a $1$ at that index, it contributes $0$ inversions.
    357 
    358 What happens if we cyclically rotate a string? If the first character in the string was a $1$, it essentially created $c_0$ inversions, which will no longer be there, and hence number of inversions decrease by $c_0$. If the first character in the string was a $0$, then what we are essentially doing is placing a $0$ at the front, increasing inversions by $c_1$ ($1$ inversion will increase for each index $i$ having a $1$.
    359 
    360 Now lets say the initial inversions are $x$. After $1$ cyclic rotation, it will become either $x + c_1$, or $x - c_0$, and we will add this value to the set. Now observe that $x - c_0$ (mod $n$) $=$ $x + n - c_0$ (mod $n$) $=$ $x + c_0 + c_1 - c_0$ (mod $n$) = $x + c_1$ (mod $n$).
    361 
    362 It essentially means that no matter what we doing, number of inversions increase by $c_1$ modulo $n$. Therefore the array contains $x$, $x + c_1$, $x + 2 \cdot c_1$.... $x + (n-1) \cdot c_1$ (mod $n$). It can be shown that this sequence contains exactly $n/ \gcd (n, c_1)$ distinct elements. Hence $f(l, r) = n/ \gcd (n, c_1)$
    363 
    364 **Part 2 Hint 1**
    365 
    366 It isn't really useful to directly work with $\operatorname{gcd}$ , Try to find some useful properties of $\operatorname{gcd}$ and work with them.
    367 
    368 **Part 2 Hint 2**
    369 
    370 Let's say you know the $i$-th character of the string. How do you determine the $i+1$-th character while minimising the cost of query ?
    371 
    372 **Part 2 Solution**
    373 
    374 First it's obvious to see that the binary string and its complement form returns the same answer for all queries so we need atleast two guesses. Hence we will first assume the first character of the string , build the string using this first character and then if this string is not correct, its complement form will be definitely correct.
    375 
    376 Then we can see if we query ranges of only **even** lengths , we can determine the **parity** of '$1$'s present in the range.(Given $m$ is even,$\operatorname{gcd}(k,m)$ is odd if $k$ is odd else even if $k$ is even)
    377 
    378 Thus we can first find the string using the following method ---
    379 
    380 1. We can start determining all characters from left to right.
    381 2. At a position $i$, we can query the longest prefix which includes the $i$-th position (basically if $i$ is odd , we query $(2,i)$ else $(1,i)$).
    382 3. Since we can already know the characters upto $i-1$-th position, we can choose whether $i$-th character is '$1$' or '$0$' based on the parity of the query we receive.
    383 
    384 However the cost of the queries is $\sum_{i=1}^{n} \frac{n}{i}$ $\approx$ $n\cdot ln(n)$ which is greater than $3\cdot n$ for sufficiently large $n$.
    385 
    386 To reduce the cost, we will have to query from both ends.
    387 
    388 To determine $i+1$-th character assuming we know $i$-th character , we can treat $(i,i+1)$ as a pair.
    389 
    390 For this pair , we can choose the longest prefix or the longest suffix(similar to what we did earlier) and make two queries which minimise the cost. Since we know the parities of both queries and the $i$-th character , we can determine the $i+1$-th character.
    391 
    392 We can see the cost of the total queries turn out to be approximately
    393 
    394 $2\cdot \sum_{i=\frac{n}{2}}^{n} \frac{n}{i}\approx 2\cdot ln(2) \cdot n\approx 1.38 \cdot n \lt 3\cdot n$
    395 
    396 The bound was set to $3\cdot n$ to allow some other weaker solutions to pass using the same idea.
    397 
    398 There also exists a solution using trees , which basically uses the same query pattern as I mentioned above (We can determine the longest even prefix or longest even suffix for each position and take the longer of these queries) .
    399 
    400 We make a tree out of all these queries , assigning the edges as the parity of the queries. Then assuming the $1$-st character , we find the rest of the characters using a $DFS/BFS$.
    401 
    402 **Code 1(C++)**
    403 
    404 ```
    405 #include <bits/stdc++.h>
    406 using namespace std;
    407 map<pair<int,int>,int> quers;
    408 int ask(int l,int r){
    409     if(l>r)return 0;
    410     if(quers.count({l,r})){
    411         return quers[{l,r}];
    412     }
    413     cout<<"? "<<l<<" "<<r<<endl;
    414     int x;
    415     cin>>x;
    416     return quers[{l,r}]=((r-l+1)/x)%2;
    417 }
    418 
    419 void solve() {
    420     int n;
    421     cin>>n;
    422     string s;
    423     for(int i=0;i<n;i++)s+='0';
    424     quers.clear();
    425     if(n<=6){
    426         int cu;
    427         for(int i=2;i<=n;i++){
    428             cu=ask(i-1,i);
    429             s[i-1]=((s[i-2]-'0')^cu)+'0';
    430         }
    431         cout<<"! "<<s<<endl;
    432         int x;
    433         cin>>x;
    434         if(x==1)return;
    435         for(auto &x:s){
    436             if(x=='0')x='1';
    437             else x='0';
    438         }
    439         cout<<"! "<<s<<endl;
    440         cin>>x;
    441         return;
    442     }
    443     for(int i=2;i<n;i++){
    444         // to guess i
    445         // 1 + (i)%2 i
    446         // 1 + (i)%2 i-2
    447         // i+1 n-(n-i)%2
    448         // i-1 n-(n-i)%2
    449         int quer1=i-(i)%2;
    450         int quer2=n-(n-i)%2-i;
    451         if(quer1>quer2){
    452             int type1=ask(1+(i)%2,i);
    453             int type2=ask(1+(i)%2,i-2);
    454             s[i-1]=((s[i-2]-'0')^type1^type2)+'0';
    455         }
    456         else{
    457             int type1=ask(i+1,n-(n-i)%2);
    458             int type2=ask(i-1,n-(n-i)%2);
    459             s[i-1]=((s[i-2]-'0')^type1^type2)+'0';
    460         }
    461     }
    462     int la=ask(1+(n&1),n);
    463     int ct=0;
    464     for(int i=(n&1);i<n;i++){
    465         ct+=(s[i]=='1');
    466     }
    467     ct&=1;
    468     s[n-1]=(la^ct)+'0';
    469     cout<<"! "<<s<<endl;
    470     int x;
    471     cin>>x;
    472     if(x==1)return;
    473     for(auto &x:s){
    474         if(x=='0')x='1';
    475         else x='0';
    476     }
    477     cout<<"! "<<s<<endl;
    478     cin>>x;
    479 }
    480 signed main() {
    481     ios_base::sync_with_stdio(false);
    482     cin.tie(NULL);
    483     int t; cin >> t;
    484     while (t--)
    485         solve();
    486     return 0;
    487 }
    488 ```
    489 
    490 **Code 2(C++)**
    491 
    492 ```
    493 #include <bits/stdc++.h>
    494 using namespace std;
    495 
    496 void dfs(int u, int p, vector<vector<pair<int,int>>> &g, vector<int> &pref)
    497 {
    498     for(auto [v,parity]:g[u])
    499     {
    500         if(v==p)continue;
    501         pref[v]=pref[u]^parity;
    502         dfs(v,u,g,pref);
    503     }
    504 }
    505 void solve() {
    506     int n;
    507     cin>>n;
    508     vector<vector<pair<int,int>>> g(n+1);
    509     vector<int> p(n+1);
    510     string s;
    511     for(int i=2;i<=n;i++)
    512     {
    513         int f=0;
    514         if(i%2)f=1;
    515         int l=n;
    516         if((i%2)!=(l%2))l--;
    517         if(i-f>l-i)
    518         {
    519             cout<<"? "<<f+1<<" "<<i<<"\n";
    520             cout.flush();
    521             int x;
    522             cin>>x;
    523             int par=((i-f)/x)%2;
    524             g[i].push_back({f,par});
    525             g[f].push_back({i,par});
    526         }
    527         else
    528         {
    529             cout<<"? "<<i+1<<" "<<l<<"\n";
    530             cout.flush();
    531             int x;
    532             cin>>x;
    533             int par=((l-i)/x)%2;
    534             g[i].push_back({l,par});
    535             g[l].push_back({i,par});
    536         }
    537     }
    538     p[1]=0;
    539     dfs(0,-1,g,p);
    540     dfs(1,-1,g,p);
    541 
    542     for(int i=1;i<=n;i++)
    543     {
    544         int r=p[i]^p[i-1];
    545         if(r==0)s+='0';
    546         else s+='1';
    547     }
    548     cout<<"! "<<s<<"\n";
    549     cout.flush();
    550     int w;
    551     cin>>w;
    552     if(w)return;
    553 
    554     for(int i=0;i<n;i++)
    555     {
    556         if(s[i]=='0')s[i]='1';
    557         else s[i]='0';
    558     }
    559     cout<<"! "<<s<<"\n";
    560     cout.flush();
    561     cin>>w;
    562 }
    563 
    564 int main() {
    565     int t=1; cin >> t;
    566     while(t--)
    567         solve();
    568     return 0;
    569 }
    570 ```
    571 
    572 [2210F - A Simple Problem](/contest/2210/problem/F "Codeforces Round 1089 (Div. 2)")
    573 
    574 Idea: [simplelife](/profile/simplelife "Expert simplelife"), Preparation: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    575 
    576 Thanks to [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__") for solving this problem.
    577 
    578 For the simplicity of editorial , denote $\max(b_1,b_2,\ldots,b_i)$ as prefix-max($i$) and $\min(b_1,b_2,\ldots,b_i)$ as prefix-min($i$).
    579 
    580 **Hint 1**
    581 
    582 You may think that first choosing prefix-max and then choosing prefix-min is always optimal , but is it always correct?
    583 
    584 **Hint 2**
    585 
    586 Suppose at an index $i$ , you choose prefix-max($i$) or a prefix-min($i$) , how does it affect the inversions from the left side and from the right side? Analyse all the cases properly.
    587 
    588 **Solution**
    589 
    590 First we will solve this problem for a single query and then build up the optimal solution step by step.
    591 
    592 Suppose we choose a prefix-max($i$) at index $i$.
    593 
    594 Then,
    595 
    596 * It will never create an inversion with the left side of array.($j \lt i$)
    597 * It will always create an inversion with any prefix-min on the right side of array and never creates any inversion with prefix-max.($j \gt i$)
    598 
    599 Now suppose we choose a prefix-min($i$) at index $i$.
    600 
    601 Then,
    602 
    603 * It will always create an inversion with the left side of array except when we choose a prefix-min whose value is equal to this prefix-min.($j \lt i$)
    604 * It will always create an inversion with any prefix-min on the right side of array that is smaller than this prefix-min and never creates any inversion with prefix-max.($j \gt i$)
    605 
    606 Thus we can see our choices at an index $i$(choosing whether we take prefix-max($i$) or prefix-min($i$)) is independent of any index $j$ where the prefix-min($j$)$\neq$prefix-min($i$).
    607 
    608 Thus we can divide this array into blocks having equal prefix-min.
    609 
    610 Since choices in each block is independent of other blocks , we can maximise the number of inversions in each block independently and add the contributions of each block to final answer.
    611 
    612 Now for each block , Let $s$ be the length of the array that comes before this block and $t$ be the length of the current block.
    613 
    614 We can easily prove that in this block , that first choosing prefix-max and then prefix-min is the optimal choice to maximise the number of inversions.
    615 
    616 Let $x(x\leq t)$ be the number of elements we choose to be prefix-max in this block. Then the number of inversions in this block is given by $(s+x)\cdot(t-x)$.
    617 
    618 This is a concave down quadratic function with its value maximised at $x=\frac{t-s}{2}$. Then for this block , we can just choose the closest non-negative integer value of $x$ to be the optimal $x$.
    619 
    620 For the single query version , we can just divide the array into blocks , choose the optimal $x$ for each block independently and sum the contributions over all blocks.
    621 
    622 Now for optimising the solution ,
    623 
    624 We will divide the blocks into two cases.
    625 
    626 * **Case 1**: $t-s \gt 0$
    627 * **Case 2**: $t-s\leq 0$
    628 
    629 For blocks in Case $2$ , we can just choose $x=0$ i.e , all elements in the block are prefix-min.
    630 
    631 Now notice that for Case $1$ , $t$ must be greater than $s$ i.e , the size of current block should be as large as the size of the array that comes before it. This means whenever we encounter a case of type $1$ , the current array length doubles. This means Case $1$ only happens at most **${log_2(n)}$** times , where n is the length of the total array.
    632 
    633 Now for implementation details,
    634 
    635 We can handle all cases of type $1$ in $O(1)$ time.
    636 
    637 Now we need an efficient method to jump over blocks of type $2$.
    638 
    639 An efficient way to do this is by using binary lifting.
    640 
    641 Consider the following subproblem ---
    642 
    643 The current array length is $s$ and you have to jump over $k$ blocks of length $b_1,b_2,\ldots,b_k$, which are of type $2$.
    644 
    645 Let $tot=\sum_{i=1}^{k} b_i$.
    646 
    647 The number of inversions due to these $k$ blocks will be ---
    648 
    649 $s\cdot b_1 + (s+b_1)\cdot b_2\ldots + (s+b_1+b_2\ldots b_{k-1})\cdot b_k$ $=$ $s\cdot tot + \sum_{i=1}^{k}\sum_{j=i+1}^{k} b_i\cdot b_j$ $ = $ $ s\cdot tot + \frac{1}{2}\cdot\left(tot^2-\sum_{i=1}^{k} b_i^2\right)$
    650 
    651 We can precompute the square sum.
    652 
    653 We also need to store the maximum block length we can jump over in case of type $2$. This can also be done using binary lifting.
    654 
    655 The intended time complexity of the solution is $O((n+q)\cdot \log(n))$ but fairly implemented $O(n\cdot \log(n) + q\cdot \log(n)^2)$ also passes.
    656 
    657 The following can also be implemented using a data-structure , like segment tree or fenwick tree , refer to [Dominater069](/profile/Dominater069 "Legendary Grandmaster Dominater069")'s code.
    658 
    659 **Code ( __baozii__,C++)**
    660 
    661 ```
    662 #include <bits/stdc++.h>
    663 
    664 using namespace std;
    665 
    666 using i64 = long long;
    667 
    668 constexpr int B = 21;
    669 
    670 void solve() {
    671     int n, q;
    672     cin >> n >> q;
    673     vector<int> a(n);
    674     for (int i = 0; i < n; i++) cin >> a[i];
    675     vector<i64> next(n, n), st;
    676     for (int i = 0; i < n; i++) {
    677         while (!st.empty() && a[i] < a[st.back()]) {
    678             next[st.back()] = i;
    679             st.pop_back();
    680         }
    681         st.push_back(i);
    682     }
    683     vector<vector<int>> g(n + 1);
    684     for (int i = 0; i < n; i++) g[next[i]].push_back(i);
    685     vector<array<int, B>> up(n + 1), pa(n + 1);
    686     vector<i64> sum1(n + 1), sum2(n + 1);
    687     for (int i = 0; i <= n; i++) up[i].fill(n), pa[i].fill(n);
    688     auto dfs = [&](auto &&self, int u) -> void {
    689         for (auto v : g[u]) {
    690             int d = u - v;
    691             for (int i = 0; i < B; i++) {
    692                 up[v][i] = (d >= 1 << i) ? v : up[u][i];
    693                 if (i == 0) pa[v][i] = u;
    694                 else pa[v][i] = pa[pa[v][i - 1]][i - 1];
    695             }
    696             sum1[v] = sum1[u] + d;
    697             sum2[v] = sum2[u] + 1LL * d * d;
    698             self(self, v);
    699         }
    700     };
    701     dfs(dfs, n);
    702     while (q--) {
    703         i64 l, r;
    704         cin >> l >> r;
    705         l--;
    706         i64 u = min(r, next[l]);
    707         i64 x = (u - l - 1) / 2;
    708         i64 ans = x * (u - l - 1 - x);
    709         i64 t = u - l;
    710         while (u < r) {
    711             int i = (t <= 1) ? 0 : (31 - __builtin_clz(t));
    712             assert(i < B && i >= 0);
    713             i64 v = up[u][i];
    714             if (v > r) {
    715                 v = u;
    716                 for (int j = B - 1; j >= 0; j--) if (pa[v][j] <= r) v = pa[v][j];
    717             }
    718             i64 d1 = sum1[u] - sum1[v], d2 = sum2[u] - sum2[v];
    719             ans += t * d1 + (d1 * d1 - d2) / 2;
    720             t += d1;
    721             u = v;
    722             if (u < r) {
    723                 i64 s = min(r, next[u]) - u;
    724                 i64 x = clamp((s - t) / 2, 0LL, s);
    725                 ans += -x * x + (s - t) * x + s * t;
    726                 t += s;
    727                 u = min(r, next[u]);
    728             }
    729         }
    730         cout << ans << "\n";
    731     }
    732 }
    733 
    734 int main() {
    735     ios::sync_with_stdio(0);
    736     cin.tie(0);
    737 
    738     int t;
    739     cin >> t;
    740     while (t--) solve();
    741 }
    742 ```
    743 
    744 **Code(Dominater069,C++)**
    745 
    746 ```
    747 #include <bits/stdc++.h>
    748 using namespace std;
    749 #define int long long
    750 #define INF (int)1e18
    751 
    752 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
    753 
    754 struct FenwickTree{
    755     int n;
    756     vector <int> f;
    757     vector <int> b;
    758 
    759     inline void add(int i, int x){
    760         b[i] += x;
    761         for (int j = i; j <= n; j += j & (-j)){
    762             f[j] += x;
    763         }
    764     }
    765 
    766     inline void modify(int i, int x){
    767         add(i, x - b[i]);
    768     }
    769 
    770     inline void init(int nn, vector <int> a){
    771         n = nn;
    772         if (a.size() == n){
    773             vector <int> a2;
    774             a2.push_back(0);
    775             for (auto x : a) a2.push_back(x);
    776             a = a2;
    777         }
    778 
    779         f.resize(n + 1);
    780         b.resize(n + 1);
    781 
    782         for (int i = 0; i <= n; i++) f[i] = 0, b[i] = 0;
    783 
    784         for (int i = 1; i <= n; i++){
    785             modify(i, a[i]);
    786         }
    787     }
    788 
    789     inline int query(int x){
    790         int ans = 0;
    791         for (int i = x; i; i -= i & (-i)){
    792             ans += f[i];
    793         }
    794         return ans;
    795     }
    796 
    797     inline int query(int l, int r){
    798         return query(r) - query(l - 1);
    799     }
    800 };
    801 
    802 void Solve() 
    803 {
    804     // make edges l -> nx[l] 
    805     // binary lifting 
    806     // cost(i) needs to be computed 
    807     // sequence length > prefix => balances at (seq + prefix) / 2 
    808     // otherwise balances at seq length * prefix 
    809     // the first can happen only log times 
    810     // for all active i, need to add (i - l) * val[i] 
    811     // fix the sum for i = l and i such that sequence length > prefix 
    812     // find first val[i] > current, is it guaranteed to be active?
    813     
    814     int n, q; cin >> n >> q;
    815     
    816     vector <int> p(n + 1);
    817     for (int i = 1; i <= n; i++){
    818         cin >> p[i];
    819     }
    820     
    821     vector<vector<pair<int, int>>> adj(n + 1);
    822     for (int i = 1; i <= q; i++){
    823         int l, r; cin >> l >> r;
    824         
    825         adj[l].push_back({r, i});
    826     }
    827     
    828     vector <int> nxs(n + 1, n + 1);
    829     {
    830         stack <pair<int, int>> st;
    831         for (int i = 1; i <= n; i++){
    832             while (!st.empty() && st.top().first > p[i]){
    833                 nxs[st.top().second] = i;
    834                 st.pop();
    835             }
    836             
    837             st.push({p[i], i});
    838         }
    839     }
    840     
    841     vector<vector<int>> jump(21, vector<int>(n + 2));
    842     for (int i = 1; i <= n + 1; i++){
    843         jump[0][i] = (i > n) ? i : nxs[i];
    844     }
    845     
    846     for (int i = 1; i <= 20; i++){
    847         for (int j = 1; j <= n + 1; j++){
    848             jump[i][j] = jump[i - 1][jump[i - 1][j]];
    849         }
    850     }
    851     
    852     vector <int> val(n + 1);
    853     for (int i = 1; i <= n; i++){
    854         val[i] = nxs[i] - i;
    855     }
    856     
    857     // fenwick for i * val[i] and val[i]
    858     stack <pair<int, int>> st; // stack for active values 
    859     FenwickTree f1, f2;
    860     vector <int> vv(n);
    861     f1.init(n, vv); f2.init(n, vv);
    862     
    863     for (int i = 1; i <= n; i++){
    864         f1.modify(i, val[i]);
    865         f2.modify(i, val[i] * i);
    866     }
    867     
    868     set <int> ss;
    869     
    870     vector<vector<int>> at(n + 1);
    871     for (int i = 1; i <= n; i++){
    872         int r = i - val[i];
    873         if (r >= 1){
    874             at[r].push_back(i);
    875         }
    876     }
    877     
    878     auto deac = [&](int x){
    879         ss.erase(x);
    880         f1.modify(x, 0);
    881         f2.modify(x, 0);
    882     };
    883     
    884     vector <int> ans(q + 1);
    885     
    886     for (int l = n; l >= 1; l--){
    887         while (!st.empty() && st.top().first > p[l]){
    888             deac(st.top().second);
    889             st.pop();
    890         }
    891         st.push({p[l], l});
    892         ss.insert(l);
    893         for (auto x : at[l]){
    894             ss.erase(x);
    895         }
    896         
    897         for (auto [r, i] : adj[l]){
    898             ans[i] += f2.query(l, r) - l * f1.query(l, r);
    899             
    900             auto calc = [&](int x){
    901             //    cout << "UPD " << x << "\n";
    902                 int vv = min(val[x], r - x + 1);
    903                 if (x == l) vv--;
    904                 if (vv > x - l){
    905                     vv += (x - l);
    906                     ans[i] += (vv / 2) * ((vv + 1) / 2);
    907                 } else {
    908                     ans[i] += vv * (x - l);
    909                 }
    910             };
    911             
    912             int pos = l;
    913             // while (pos <= r){
    914             //     if (nxs[pos] > r && val[pos] <= (pos - l)){
    915             //         ans[i] -= val[pos] * (pos - l);
    916             //         calc(pos);
    917             //     }
    918             //     pos = nxs[pos];
    919             // }
    920             for (int j = 20; j >= 0; j--){
    921                 if (jump[j][pos] <= r){
    922                     pos = jump[j][pos];
    923                 }
    924             }
    925             assert(nxs[pos] > r);
    926             if (!ss.count(pos)){
    927                 ans[i] -= val[pos] * (pos - l);
    928                 calc(pos);
    929             }
    930             
    931             for (auto x : ss){
    932                 if (x <= r){
    933                     ans[i] -= val[x] * (x - l);
    934                     calc(x);
    935                 } else {
    936                     break;
    937                 }
    938             }
    939         }
    940     }
    941     
    942     for (int i = 1; i <= q; i++){
    943         cout << ans[i] << "\n";
    944     }
    945 }
    946 
    947 int32_t main() 
    948 {
    949     auto begin = std::chrono::high_resolution_clock::now();
    950     ios_base::sync_with_stdio(0);
    951     cin.tie(0);
    952     int t = 1;
    953     // freopen("in",  "r", stdin);
    954     // freopen("out", "w", stdout);
    955     
    956     cin >> t;
    957     for(int i = 1; i <= t; i++) 
    958     {
    959         //cout << "Case #" << i << ": ";
    960         Solve();
    961     }
    962     auto end = std::chrono::high_resolution_clock::now();
    963     auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    964     cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    965     return 0;
    966 }
    967 ```