codeforces-scrape

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

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.