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  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 ```