2103.md (27279B)
1 Source: https://codeforces.com/blog/entry/142149 2 3 [2103A - Common Multiple](/contest/2103/problem/A "Codeforces Round 1019 (Div. 2)") 4 5 Author: [NemanjaSo2005](/profile/NemanjaSo2005 "Grandmaster NemanjaSo2005") 6 7 **Hint 0** 8 9 We need to solve the same problem $t$ times. We will make use of [loops](https://www.geeksforgeeks.org/loops-programming/) to do so. From now we will focus on solving a problem for one test case, but remember that all of the following will be in a loop. 10 11 **Hint 1** 12 13 So the array $x$ is beautiful if there exists an array of distinct elements $y$ such that $x_i \cdot y_i$ is the same for all $1 \le i \le n$. We will try to make the condition into something more understandable. Suppose that the common product is some constant $C$. How can you express each $y_i$ in terms of $C$ and $x_i$? 14 15 **Hint 2** 16 17 It can be expressed as $y_i = \frac{C}{x_i}$. If all $y_i = \frac{C}{x_i}$ must be all different, what does that force upon the array $x$ for it to be beautiful? 18 19 **Hint 3** 20 21 Let $i$ and $j$ be indices of two arbitrary elements of $x$. Then for array $x$ to be beautiful the following needs to hold: 22 23 $y_i \neq y_j$ 24 25 $\frac{C}{x_i} \neq \frac{C}{x_j}$, divide both sides by $C$ 26 27 $\frac{1}{x_i} \neq \frac{1}{x_j}$, as neither $x_i$ nor $x_j$ are $0$, multiply by $x_i \cdot x_j$ 28 29 $x_j \neq x_i$ 30 31 Therefore, all values of $x_i$ must be distinct. But is it enough just that all values of $x$ are distinct? 32 33 It is, and here is how to easily construct the integer array $y$ that satisfies the constraints. Let $P$ be the product of all elements of $x$. Then make $y_i = \frac{P}{x_i}$ for all $1 \le i \le n$. As all values of $x$ are distinct and nonzero, it is guaranteed that all values of $y$ will also be distinct. 34 35 **Hint 4** 36 37 The solution is the number of distinct values in $a$. How can we count that? 38 39 **Hint 5** 40 41 We can only count the first appearance of each value. So the problem is now how to check if the appearance of value at some position $i$ is indeed the first appearance of $a_i$. 42 43 **Solution** 44 45 Read the hints. 46 47 The answer to the problem is the number of distinct elements in the array. There are many ways to find it; we will present one of the easiest. 48 49 We will count only the first appearances of every value. 50 51 That means that if array is for example [ $1$, $3$, $1$, $5$, $3$, $1$], we will only count $1$ at position $1$, $3$ at position $2$ and $5$ at position $4$. We will not count values $1$ at positions $3$ and $6$, nor the value $3$ at position $5$, as they are not the first appearance of those values. 52 53 We will iterate through every element in $x$ and for an element $x_i$, check if there exists some $x_j$ $(j \lt i)$ such that $x_i = x_j$. If we can't find such $j$, then that means it's the first appearance of $x_i$. 54 55 We can do it by having one loop iterate over $i$, and it will have a variable that says whether it is the first appearance, originally set to true. Then we will iterate in another loop over all indices $1 \le j \lt i$ and if at any point $a_i = a_j$, we will set the value of the variable to false. Then we increase the count of different values if the variable is still true. 56 57 Memory complexity is $O(n)$. Time complexity is $O(n^2)$ per testcase giving us a total time complexity of $O(tn^2)$. 58 59 **Implementation (c++)** 60 61 ``` 62 #include<bits/stdc++.h> 63 #define ll long long 64 using namespace std; 65 const int maxn=105; 66 int n,arr[maxn]; 67 int main(){ 68 int T; 69 cin>>T; 70 while(T--){ 71 cin>>n; 72 for(int i=1;i<=n;i++) 73 cin>>arr[i]; 74 int ans=0; 75 for(int i=1;i<=n;i++){ 76 int add=1; 77 for(int j=1;j<i;j++) 78 if(arr[j]==arr[i]) 79 add=0; 80 ans+=add; 81 } 82 cout<<ans<<"\n"; 83 } 84 return 0; 85 } 86 ``` 87 88 **Implementation (python)** 89 90 ``` 91 t = int(input()) 92 for i in range(t): 93 n = int(input()) 94 a = input().split(" ") 95 count = 0 96 for i in range(0, n): 97 add = 1 98 for j in range(0, i): 99 if a[i]==a[j]: 100 add = 0 101 count += add 102 print(count) 103 ``` 104 105 **Bonus** 106 107 Come up with more ways to count the number of different elements in the array. 108 109 [2103B - Binary Typewriter](/contest/2103/problem/B "Codeforces Round 1019 (Div. 2)") 110 111 Author: [Blagoj](/profile/Blagoj "Expert Blagoj") 112 113 **Hint 1** 114 115 Given the string $s$, how do we calculate the answer? 116 117 **Hint 2** 118 119 We know that we need to type a character (apply operation $1$ exactly $n$ times). How many switches do we do? 120 121 **Hint 3** 122 123 If the string $s$ starts with a 1, we need to do a switch immediately. From that point on, we only switch if the current number in the string changes. We can assume that we start with a 0, as the other case can be handled by appending 0 to the start and subtracting $1$ from the final answer. 124 125 **Hint 4** 126 127 We will assume that we only want to make the answer smaller, as for keeping the answer, we can pick any interval of size $1$. How does reversing some interval [ $l$, $r$ ] change the answer? 128 129 **Hint 5** 130 131 Notice that all switches before $l-1$, after $r+1$ and inbetween $l$ and $r$ will stay. So we only care about the values of $s_{l-1}$, $s_l$, $s_r$ and $s_{r+1}$. 132 133 **Hint 6** 134 135 Notice that if $s_l = s_r$, then the swap does not change the number of changes. So we can assume that $s_l \neq s_r$ in the optimal swap. Now, to evaluate how good the swap is, we can observe the following: 136 137 * if $s_{l-1} = s_l$, the number of changes increases by $1$, otherwise it decreases by $1$. 138 * if $s_{r} = s_{r+1}$, the number of changes increases by $1$, otherwise it decreases by $1$. 139 140 Those 2 changes stack. 141 142 **Hint 7** 143 144 From the previous hint, we can conclude that we can decrease the number of changes by at most $2$. For us to be able to decrease the number of changes by $2$, it shall hold that $s_{l-1} \neq s_l$ and $s_r \neq s_{r+1}$. 145 146 If we want to decrease the number of changes by $1$, it is enough to make $s_{l-1} \neq s_l$ and to make $r=n$. 147 148 If we cannot do either of the previous two, the number of changes cannot be decreased. 149 150 **Solution** 151 152 Read the hints. 153 154 As said in the hints, we will assume that string $s$ starts with a 0. Now we need to check if it is possible to pick indices $l$ and $r$ such that the number of changes after the swap decreases by $2$. With some casework, we can see that it is always possible if the original number of changes is at least $3$. If the original number of changes is $2$, we cannot decrease it by $2$, but we can decrease it by $1$. If the original number of changes is $0$ or $1$, we cannot decrease it. 155 156 Counting the number of changes can be done in a single pass of a loop. The time and memory complexities are $O(n)$ per testcase. 157 158 **Implementation (c++)** 159 160 ``` 161 #include<bits/stdc++.h> 162 using namespace std; 163 void testCase() { 164 string s; 165 int n; 166 cin >> n; 167 cin >> s; 168 s="0"+s; 169 int ans = 0, cur = s[0]; 170 for (int i = 1; i <= n; i++) { 171 int dig = s[i]; 172 if (cur != dig) 173 ans++; 174 cur = dig; 175 } 176 if(ans>=3) 177 cout<< ans-2 + n<<"\n"; 178 else if(ans==2) 179 cout<< ans-1 + n<<"\n"; 180 else 181 cout<<ans+n<<"\n"; 182 } 183 int main(){ 184 int t; 185 cin>>t; 186 while(t--) 187 testCase(); 188 return 0; 189 } 190 ``` 191 192 **Implementation (python)** 193 194 ``` 195 for _ in range(int(input())): 196 n = int(input()) 197 a = input().strip() 198 cnt = 0 199 for i in range(n-1): 200 if a[i] != a[i+1]: cnt += 1 201 if cnt == 0: 202 print(n + int(a[0] == "1")) 203 elif cnt == 1: 204 print(n + 1) 205 else: 206 print(n+cnt-1 - int(a[0] == "0" and cnt > 2)) 207 ``` 208 209 **Bonus** 210 211 Solve the problem if you were given $n$ strings. You will swap their order however you want and then concatenate them all into one string $s$. What is the minimal number of operations needed to write $s$ obtained in that way? 212 213 [2103C - Median Splits](/contest/2103/problem/C "Codeforces Round 1019 (Div. 2)") 214 215 Author: [NemanjaSo2005](/profile/NemanjaSo2005 "Grandmaster NemanjaSo2005") 216 217 **Hint 1** 218 219 We split our array into $3$ subarrays, take their medians, and the final median needs to be $\le k$. That means that the median of at least $2$ of those subarrays needs to be $\le k$. 220 221 **Hint 2** 222 223 For a given array $x$ of length $m$, what is the condition that $\operatorname{med}(x_1, x_2, \ldots, x_m) \le k$? 224 225 **Hint 3** 226 227 There need to be at least as many elements in $x$ that are $\le k$ as those that are $ \gt k$. How can we simplify this? 228 229 **Hint 4** 230 231 We can replace all elements that are $\le k$ with $1$ and all elementsthat are $ \gt k$ with $-1$. Now the median of $x$ is $\le k$ if and only if the sum of elements in $x$ is non-negative. 232 233 **Hint 5** 234 235 Now that we replaced the elements of $a$, the question is if it is possible to split it into $3$ subarrays, of which at least $2$ have a non-negative sum. There are $3$ cases: 236 237 1. The first and second subarrays have non-negative sums. 238 2. The second and third subarrays have non-negative sums. 239 3. The first and third subarrays have non-negative sums. 240 241 **Hint 6** 242 243 Use prefix/suffix sums and maximums/ minimums to help you compute the answer in linear time. 244 245 **Solution** 246 247 Read the hints. 248 249 Cases $1$ and $2$ from hint 5 are symmetric, so we will only explain how to do case $1$. Compute the prefix sum of the array, let it be array $p$. The subarray [$l$, $r$] has non-negative sum if $p_{l-1} \le p_{r}$. For each index $2 \le i \lt n$ compute value $msp$ (max suffix prefix), such that $msp_i = max(p_i, p_{i+1},\ldots, p_{n-1})$. Then iterate over index $1 \le i \le n-2$ that will be the end of the first subarray. If $p_i \ge 0$ and $msp_{i+1} \ge p_i$, then it will be possible to split the array such that the medians of the first and second subarrays are $\le k$. 250 251 Case $3$ is even easier. Find positions $x$ and $y$ such that [ $1$ , $x$ ] is the shortest prefix with median $ \le k$ and [ $y$, $n$ ] is the shortest suffix with median $\le k$. Then the split into three subarrays such that the first and third have median $\le k$ is possible if and only if [ $x+1$ , $y-1$ ] is a valid subarray, in other words, if $x + 2 \le y$. 252 253 As both cases can be checked with a few array passes, the time and memory complexities are $O(n)$ per testcase. 254 255 **Implementation (c++)** 256 257 ``` 258 #include<bits/stdc++.h> 259 #define ll long long 260 using namespace std; 261 const int maxn=2e5+5; 262 int n,k,arr[maxn],suf[maxn],minsuf[maxn]; 263 bool check_prefix_and_middle(){ 264 suf[n]=minsuf[n]=arr[n]; 265 for(int i=n-1;i>=1;i--){ 266 suf[i]=suf[i+1]+arr[i]; 267 minsuf[i]=min(minsuf[i+1],suf[i]); 268 } 269 int s=0; 270 for(int i=1;i+2<=n;i++){ 271 s+=arr[i]; 272 if(s<0) 273 continue; 274 if(suf[i+1]>=minsuf[i+2]) 275 return true; 276 } 277 return false; 278 } 279 void solve(){ 280 cin>>n>>k; 281 for(int i=1;i<=n;i++) 282 cin>>arr[i]; 283 for(int i=1;i<=n;i++) 284 if(arr[i]<=k) 285 arr[i]=1; 286 else 287 arr[i]=-1; 288 289 int a=n+1,b=-1; 290 int s=0; 291 for(int i=1;i<=n;i++){ 292 s+=arr[i]; 293 if(s>=0){ 294 a=i; 295 break; 296 } 297 } 298 s=0; 299 for(int i=n;i>=1;i--){ 300 s+=arr[i]; 301 if(s>=0){ 302 b=i; 303 break; 304 } 305 } 306 if(a+1<b){ 307 cout<<"YES\n"; 308 return; 309 } 310 if(check_prefix_and_middle()){ 311 cout<<"YES\n"; 312 return; 313 } 314 for(int i=1;i<n-i+1;i++) 315 swap(arr[i],arr[n-i+1]); 316 if(check_prefix_and_middle()){ 317 cout<<"YES\n"; 318 return; 319 } 320 cout<<"NO\n"; 321 return; 322 } 323 int main(){ 324 int t; 325 cin>>t; 326 while(t--) 327 solve(); 328 return 0; 329 } 330 ``` 331 332 **Implementation (python)** 333 334 ``` 335 def check_prefix_and_middle(n, arr): 336 suf = [0] * (n + 1) 337 minsuf = [0] * (n + 1) 338 suf[n] = minsuf[n] = arr[n - 1] 339 340 for i in range(n - 2, -1, -1): 341 suf[i + 1] = suf[i + 2] + arr[i] 342 minsuf[i + 1] = min(minsuf[i + 2], suf[i + 1]) 343 344 s = 0 345 for i in range(n - 2): 346 s += arr[i] 347 if s < 0: 348 continue 349 if suf[i + 2] >= minsuf[i + 3]: 350 return True 351 352 return False 353 354 def solve(): 355 n, k = map(int, input().split()) 356 arr = list(map(int, input().split())) 357 358 # Transform the array based on the value of k 359 for i in range(n): 360 arr[i] = 1 if arr[i] <= k else -1 361 362 a, b = n + 1, -1 363 s = 0 364 365 for i in range(n): 366 s += arr[i] 367 if s >= 0: 368 a = i + 1 369 break 370 371 s = 0 372 for i in range(n - 1, -1, -1): 373 s += arr[i] 374 if s >= 0: 375 b = i + 1 376 break 377 378 if a + 1 < b: 379 print("YES") 380 return 381 382 if check_prefix_and_middle(n, arr): 383 print("YES") 384 return 385 386 arr.reverse() 387 388 if check_prefix_and_middle(n, arr): 389 print("YES") 390 return 391 392 print("NO") 393 394 t = int(input()) 395 for _ in range(t): 396 solve() 397 ``` 398 399 **Bonus** 400 401 Solve the problem if you need to find the smallest $k$ for which the answer is YES. 402 403 [2103D - Local Construction](/contest/2103/problem/D "Codeforces Round 1019 (Div. 2)") 404 405 Author:[NemanjaSo2005](/profile/NemanjaSo2005 "Grandmaster NemanjaSo2005") 406 407 **Hint 1** 408 409 Try to prove the claim that $a_i \le \lceil \log_2 n\rceil$. It also shall help you understand when the construction is possible, which is often a good way to think about constructive problems. 410 411 **Hint 2** 412 413 We can notice that among any two consecutive elements $p_i$ and $p_{i+1}$, one of them has to be deleted. That means that after each operation, around half of the elements are deleted, therefore giving us the bound $a_i \le \lceil \log_2 n\rceil$. It also means that for array $a$ to describe a possible permutation, it must not contain two consecutive elements on any layer that do not get deleted in next iteration. 414 415 **Hint 3** 416 417 The whole function on going to next layer is defined in recursive way. Also, WLOG we can assume that local maximums stay, as it is symmetrical for local minimums. It makes sense to think about how to arrange elements on current layer and select those that do and those that do not get deleted. Then we will apply recursive step on next layer to arrange those that do not get deleted. 418 419 But how can we guarantee elements at some position will not get deleted? 420 421 **Hint 4** 422 423 If there are $k$ positions at which elements that should not be deleted go, then we can just select the $k$ biggest elements to go there and the rest of the array we fill in with smaller ones. But how do we guarantee that one of the smaller ones does not become a local maximum? 424 425 **Hint 5** 426 427 We can sort the smaller elements in increasing/ decreasing order, so none of them will be local maximum. However, there is an edge case of the smallest elements that form a prefix/ suffix. The part of smallest elements that form a prefix must be sorted in increasing order and the part of smallest elements that form a suffix must be sorted in decreasing order. Otherwise we might get that elements at first or last positions are local maximum when we do not want them to be. 428 429 **Solution** 430 431 Read the hints. 432 433 We process each layer separately and WLOG assume that we delete those that are not local maximums. We will have some elements that go onto next layer, and we will get their order when we process the next layer, for now we just know their positions. Say exactly $k$ elements are going to next layer, then we can select them to be the largest $k$ elements, which guarantees they will be local maximums. 434 435 Now the question is how to place smaller elements. We can imagine that bigger elements divide the layer into subarrays of indices that will be deleted. It does not matter how we fill in those subarrays with smaller elements, as long as they are in sorted order. If the subarray is the prefix of a layer, it must be sorted increasingly, and if it is the suffix of the layer, it must be sorted decreasingly. 436 437 Depending on implementation time complexity is either $O(n)$ or $O(n log n)$, both of which are fast enough to pass. Memory complexity is $O(n)$. 438 439 **Implementation O(N)** 440 441 ``` 442 #include<bits/stdc++.h> 443 #define ll long long 444 using namespace std; 445 const int maxn=2e5+5; 446 int n,a[maxn],p[maxn]; 447 void construct(vector<int> pos,vector<int> nums,int layer){ 448 sort(nums.begin(),nums.end()); 449 if(pos.size()==1){ 450 p[pos[0]]=nums[0]; 451 return; 452 } 453 vector<int> keep,rem; 454 vector<bool> spec; 455 for(int x:pos) 456 if(a[x]>layer){ 457 keep.push_back(x); 458 } 459 if(layer%2==1) 460 reverse(nums.begin(),nums.end()); 461 vector<int> newnums; 462 for(int it=1;it<=keep.size();it++){ 463 newnums.push_back(nums.back()); 464 nums.pop_back(); 465 } 466 construct(keep,newnums,layer+1); 467 reverse(nums.begin(),nums.end()); 468 int last; 469 for(int x:pos){ 470 last=x; 471 if(a[x]>layer) 472 break; 473 p[x]=nums.back(); 474 nums.pop_back(); 475 } 476 reverse(nums.begin(),nums.end()); 477 for(int x:pos){ 478 if(x<last) 479 continue; 480 if(a[x]>layer) 481 continue; 482 p[x]=nums.back(); 483 nums.pop_back(); 484 } 485 } 486 void solve(){ 487 cin>>n; 488 for(int i=1;i<=n;i++) 489 cin>>a[i]; 490 for(int i=1;i<=n;i++) 491 if(a[i]<=0) 492 a[i]=1e9; 493 vector<int> A; 494 for(int i=1;i<=n;i++) 495 A.push_back(i); 496 construct(A,A,1); 497 for(int i=1;i<=n;i++) 498 cout<<p[i]<<" \n"[i==n]; 499 } 500 int main(){ 501 int T; 502 cin>>T; 503 while(T--) 504 solve(); 505 } 506 ``` 507 508 **Implementation O(n log n) (prvocislo)** 509 510 ``` 511 #include <algorithm> 512 #include <bitset> 513 #include <cassert> 514 #include <chrono> 515 #include <cmath> 516 #include <deque> 517 #include <iomanip> 518 #include <iostream> 519 #include <map> 520 #include <queue> 521 #include <random> 522 #include <set> 523 #include <string> 524 #include <vector> 525 typedef long long ll; 526 typedef long double ld; 527 using namespace std; 528 529 int main() 530 { 531 ios::sync_with_stdio(false); 532 cin.tie(0); 533 int t; 534 cin >> t; 535 while (t--) 536 { 537 int n; 538 cin >> n; 539 vector<int> a(n), p(n); 540 for (int i = 0; i < n; i++) cin >> a[i]; 541 int mx = max(0, *max_element(a.begin(), a.end())) + 1; 542 for (int i = 0; i < n; i++) if (a[i] == -1) a[i] = mx; 543 544 int l = 1, r = n; 545 for (int k = 1; k <= mx; k++) 546 { 547 int mr = n - 1; 548 while (mr >= 0 && a[mr] <= k) mr--; 549 for (int i = 0; i < mr; i++) 550 { 551 if (a[i] == k) 552 { 553 p[i] = ((k & 1) ? r-- : l++); 554 } 555 } 556 for (int i = n - 1; i > mr; i--) 557 { 558 if (a[i] == k) 559 { 560 p[i] = ((k & 1) ? r-- : l++); 561 } 562 } 563 } 564 for (int i = 0; i < n; i++) cout << p[i] << " \n"[i == n - 1]; 565 } 566 return 0; 567 } 568 ``` 569 570 **Bonus** 571 572 I came up with this problem while writing the generator for [1900F - Local Deletions](/contest/1900/problem/F "Codeforces Round 911 (Div. 2)"). 573 574 [2103E - Keep the Sum](/contest/2103/problem/E "Codeforces Round 1019 (Div. 2)") 575 576 Author:[NemanjaSo2005](/profile/NemanjaSo2005 "Grandmaster NemanjaSo2005") 577 578 **Hint 1** 579 580 When is the solution trivially -1? 581 582 **Hint 2** 583 584 When it is impossible to do any operation and array is not sorted in the beginning. Is that enough though? 585 586 **Hint 3** 587 588 It is enough. If we have even a single pair of values that sums up to $k$, we can make the array non-decreasing. From now assume there is only one such pair as we can ignore other pairs. 589 590 **Hint 4** 591 592 The constraint of $3n$ hints that a solution is linear. Maybe we are actually supposed to sort the array? Let's assume indices of values that sum up to $k$ are $a$ and $b$. How do we swap values at some other two indices $c$ and $d$. 593 594 **Solution part 1** 595 596 We can do the following sequence of operations. It could change values of elements at positions $a$ and $b$, but their sum will remain $k$ and values at indices $c$ and $d$ will be swapped. 597 598 * We do operation on indices $a$ and $b$ and we make it so that $value[a] := k - value[c]$ and $value[b] := value[c]$. 599 * We do operation on indices $a$ and $c$ and we make it so that $value[a] := k - value[d]$ and $value[c] := value[d]$. 600 * We do operation on indices $a$ and $d$ and we make it so that $value[a] := k - value[b]$ and $value[d] := value[b]$. 601 602 Notice that after this sequence of operations we swapped values at positions $c$ and $d$ and $value[a] + value[b]$ is still $k$. We can now sort the rest of the array (without $a$ and $b$) and then adjust values of $a$ and $b$ at the end. However, there is still a problem. 603 604 **Hint 5** 605 606 It might be impossible to adjust values of $a$ and $b$. Take $k=5$ and array [$1$, $3$, $2$, $3$, $5$] for example, with $a = 3$ and $b = 4$. How do we avoid such problems? 607 608 **Hint 6** 609 610 If $a = 1$ and $b = n$ we can just make $value[a]=0$ and $value[b] = k$ and as all other elements are between $0$ and $k$, it is guaranteed that array is sorted. How do we do it? 611 612 **Solution part 2** 613 614 We will assume that both $a$ and $b$ are neither $1$ nor $n$. If they are, then we will skip some steps. The following sequence of operations makes $a=1$ and $b=n$ a valid choice. Note that $a$ and $b$ are referring to their original indices. 615 616 * We do operation on indices $a$ and $b$ and we make it so that $value[a] := k - value[1]$ and $value[b] := value[1]$. 617 * We do operation on indices $1$ and $a$ and we make it so that $value[1] := k - value[n]$ and $value[a] := value[n]$. 618 619 After those two operations we can just sort the rest of the array with sequence of $3$ operations previously described. Then at the end, we do operation to make $value[1] = 0$ and $value[n] = k$. Due to $n \gt 4$ in total we use a bit less than $3n$ operations in the worst case. 620 621 **Implementation** 622 623 ``` 624 #include<bits/stdc++.h> 625 #define ll long long 626 using namespace std; 627 const int maxn=2e5+5; 628 int n,k,arr[maxn],A,B,p[maxn]; 629 map<int,int> pos; 630 vector<tuple<int,int,int>> V; /// All operations 631 void dooperation(int a,int b,int x){ 632 arr[a]-=x; 633 arr[b]+=x; 634 V.push_back(make_tuple(a,b,x)); 635 } 636 void setvalue(int pos,int b,int target){ /// Does operation on (pos, b) such that value of pos becomes target 637 if(arr[pos]==target) 638 return; 639 int dif=target-arr[pos]; 640 dooperation(b,pos,dif); 641 } 642 void performswap(int x,int y){ 643 int vx=arr[x],vy=arr[y]; 644 setvalue(A,B,k-vx); 645 setvalue(x,A,vy); 646 setvalue(y,A,vx); 647 } 648 bool cmp(int a,int b){ 649 return arr[a]<arr[b]; 650 } 651 void solve(){ 652 pos.clear(); 653 V.clear(); 654 A=B=-1; 655 cin>>n>>k; 656 for(int i=1;i<=n;i++) 657 cin>>arr[i]; 658 bool issorted=true; 659 for(int i=2;i<=n;i++) 660 if(arr[i]<arr[i-1]) 661 issorted=false; 662 if(issorted){ 663 cout<<"0\n"; 664 return; 665 } 666 for(int i=1;i<=n;i++){ 667 if(pos.find(k-arr[i])!=pos.end()){ 668 B=i; 669 A=pos[k-arr[i]]; 670 break; 671 } 672 pos[arr[i]]=i; 673 } 674 if(A==-1){ 675 cout<<"-1\n"; 676 return; 677 } 678 if(A!=1){ 679 setvalue(A,B,k-arr[1]); 680 setvalue(1,A,k-arr[B]); 681 A=1; 682 } 683 if(B!=n){ 684 setvalue(B,A,k-arr[n]); 685 setvalue(n,B,k-arr[A]); 686 B=n; 687 } 688 vector<int> invp; 689 for(int i=2;i<n;i++) 690 invp.push_back(i); 691 sort(invp.begin(),invp.end(),cmp); 692 for(int i=0;i<invp.size();i++) 693 p[invp[i]]=i+2; 694 for(int i=2;i<n;i++){ 695 if(p[i]==i) 696 continue; 697 performswap(p[i],i); 698 swap(p[p[i]],p[i]); 699 i--; 700 } 701 setvalue(B,A,k); 702 cout<<V.size()<<"\n"; 703 for(auto x:V) 704 cout<<(get<0>(x))<<" "<<(get<1>(x))<<" "<<(get<2>(x))<<"\n"; 705 return; 706 } 707 int main(){ 708 int T; 709 cin>>T; 710 while(T--) 711 solve(); 712 return 0; 713 } 714 ``` 715 716 **Bonus** 717 718 Solve the problem in $\lceil \frac{3n}{2} \rceil$ queries. 719 720 [2103F - Maximize Nor](/contest/2103/problem/F "Codeforces Round 1019 (Div. 2)") 721 722 Author: [NemanjaSo2005](/profile/NemanjaSo2005 "Grandmaster NemanjaSo2005") 723 724 **Hint 1** 725 726 If problem had queries of form "What is nor of some interval [$l$, $r$]", how would you answer them? 727 728 **Hint 2** 729 730 You can look at all the bits separately and answer for each. 731 732 **Hint 3** 733 734 For each bit, we only care about the position of the last $1$ on it before $r$. Let that position be $x$. If $x \gt l$, then if $x$ and $r$ are of the same parity, the bit will be $0$; otherwise, it will be $1$. 735 736 If $x=l$, the bit will be $1$ if $l$ and $r$ are the same parity and otherwise $0$. 737 738 If $x \lt l$, the bit will be $1$ if $l$ and $r$ are different parity and otherwise $0$. 739 740 **Hint 4** 741 742 From the previous hint we conclude that for a fixed $r$, the values of interval [$l$, $r$] repeat when you increase $l$ by $2$, except at positions near where last $1$ is for some bit. 743 744 **Hint 5** 745 746 That means there will be only $O(k)$ different values of nor of an interval ending at some $r$. 747 748 **Solution** 749 750 Read the hints. 751 752 We can go from beginning to the end of the array and keep all the possible nor values of intervals ending at $r$ in some vector. For each value we will also remember the highest position $l$ for which we can obtain such value. When we find all those intervals for some $r$, we use segment tree to set answer to all positions in this interval to max of current answer and nor of our interval. Time complexity is $O(nk^2 + nk log n)$ and memory complexity is $O(n)$. 753 754 **Implementation** 755 756 ``` 757 #include<bits/stdc++.h> 758 #define ll long long 759 using namespace std; 760 const int maxn=2e5+5; 761 int N,M,arr[maxn],pref[maxn][25],logg,st[4*maxn],stk; 762 int nor(int a,int b){ 763 return M^(a|b); 764 } 765 int getlog(int x){ 766 int ans=-1; 767 while(x){ 768 ans+=1; 769 x/=2; 770 } 771 return ans; 772 } 773 int internor(int l,int r){ 774 if(l<=0 or l>r) 775 return 0; 776 if(l==r) 777 return arr[r]; 778 int ans=0; 779 for(int j=0;j<=logg;j++){ 780 int bit=(1<<j); 781 if(pref[r][j]<l) 782 if((r-l+1)%2==1) 783 bit=0; 784 if(pref[r][j]==l) 785 if((r-l+1)%2==0) 786 bit=0; 787 if(pref[r][j]>l) 788 if((r-pref[r][j]+1)%2==1) 789 bit=0; 790 ans+=bit; 791 } 792 return ans; 793 } 794 void update(int lb,int rb,int x,int pos=1,int l=1,int r=stk){ 795 lb=max(1,lb); 796 rb=min(N,rb); 797 if(rb<lb) 798 return; 799 if(l==lb and r==rb){ 800 st[pos]=max(st[pos],x); 801 return; 802 } 803 int mid=(l+r)/2; 804 if(rb<=mid) 805 return update(lb,rb,x,pos*2,l,mid); 806 if(lb>mid) 807 return update(lb,rb,x,pos*2+1,mid+1,r); 808 update(lb,mid,x,pos*2,l,mid); 809 update(mid+1,rb,x,pos*2+1,mid+1,r); 810 return; 811 } 812 int get(int pos){ 813 pos+=stk-1; 814 int v=0; 815 while(pos){ 816 v=max(v,st[pos]); 817 pos/=2; 818 } 819 return v; 820 } 821 void solve(){ 822 int K; 823 cin>>N>>K; 824 stk=1; 825 while(stk<N) 826 stk<<=1; 827 M=(1<<K)-1; 828 for(int i=1;i<=N;i++) 829 cin>>arr[i]; 830 831 logg=getlog(M+1)-1; 832 for(int i=1;i<=N;i++){ 833 for(int j=0;j<=logg;j++) 834 if(arr[i]&(1<<j)) 835 pref[i][j]=i; 836 else 837 pref[i][j]=pref[i-1][j]; 838 } 839 for(int i=1;i<=N;i++){ 840 for(int j=0;j<=logg;j++){ 841 int p=pref[i][j]; 842 for(int add=-2;add<=2;add++) 843 update(p+add,i,internor(p+add,i)); 844 } 845 update(1,i,internor(1,i)); 846 } 847 for(int i=1;i<=N;i++) 848 cout<<get(i)<<" \n"[i==N]; 849 } 850 void reset(){ 851 for(int i=0;i<=N+2;i++){ 852 arr[i]=0; 853 for(int j=0;j<=logg+2;j++) 854 pref[i][j]=0; 855 } 856 logg=0; 857 for(int i=0;i<=stk+stk;i++) 858 st[i]=0; 859 } 860 int main(){ 861 int T=1; 862 cin>>T; 863 while(T--){ 864 solve(); 865 reset(); 866 } 867 return 0; 868 } 869 ``` 870 871 **Bonus** 872 873 Nor and Nand are well known for being able to mimic any bitwise operation if applied enough times. Make a circuit to add three $1$-bit numbers (those are zero and one) using $9$ NAND gates.