We need to solve the same problem $$$t$$$ times. We will make use of loops 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.

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$$$?

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?

Let $$$i$$$ and $$$j$$$ be indices of two arbitrary elements of $$$x$$$. Then for array $$$x$$$ to be beautiful the following needs to hold:

$$$y_i \neq y_j$$$

$$$\frac{C}{x_i} \neq \frac{C}{x_j}$$$, divide both sides by $$$C$$$

$$$\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$$$

$$$x_j \neq x_i$$$

Therefore, all values of $$$x_i$$$ must be distinct. But is it enough just that all values of $$$x$$$ are distinct?

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.

The solution is the number of distinct values in $$$a$$$. How can we count that?

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$$$.

Read the hints.

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.

We will count only the first appearances of every value.

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.

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$$$.

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.

Memory complexity is $$$O(n)$$$. Time complexity is $$$O(n^2)$$$ per testcase giving us a total time complexity of $$$O(tn^2)$$$.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=105;
int n,arr[maxn];
int main(){
   int T;
   cin>>T;
   while(T--){
      cin>>n;
      for(int i=1;i<=n;i++)
         cin>>arr[i];
      int ans=0;
      for(int i=1;i<=n;i++){
         int add=1;
         for(int j=1;j<i;j++)
            if(arr[j]==arr[i])
               add=0;
         ans+=add;
      }
      cout<<ans<<"\n";
   }
   return 0;
}

t = int(input())
for i in range(t):
    n = int(input())
    a = input().split(" ")
    count = 0
    for i in range(0, n):
        add = 1
        for j in range(0, i):
            if a[i]==a[j]:
                add = 0
        count += add
    print(count)

Come up with more ways to count the number of different elements in the array.

Given the string $$$s$$$, how do we calculate the answer?

We know that we need to type a character (apply operation $$$1$$$ exactly $$$n$$$ times). How many switches do we do?

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.

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?

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}$$$.

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:

• if $$$s_{l-1} = s_l$$$, the number of changes increases by $$$1$$$, otherwise it decreases by $$$1$$$.
• if $$$s_{r} = s_{r+1}$$$, the number of changes increases by $$$1$$$, otherwise it decreases by $$$1$$$.

Those 2 changes stack.

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}$$$.

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$$$.

If we cannot do either of the previous two, the number of changes cannot be decreased.

Read the hints.

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.

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.

#include<bits/stdc++.h>
using namespace std;
void testCase() {
    string s;
    int n;
    cin >> n;
    cin >> s;
    s="0"+s;
    int ans = 0, cur = s[0];
    for (int i = 1; i <= n; i++) {
        int dig = s[i];
        if (cur != dig) 
           ans++;
        cur = dig;
    }
   if(ans>=3)
     cout<< ans-2 + n<<"\n";
   else if(ans==2)
     cout<< ans-1 + n<<"\n";
   else 
     cout<<ans+n<<"\n";
}
int main(){
    int t;
    cin>>t;
    while(t--)
        testCase();
    return 0;
}

for _ in range(int(input())):
    n = int(input())
    a = input().strip()
    cnt = 0
    for i in range(n-1):
        if a[i] != a[i+1]: cnt += 1
    if cnt == 0:
        print(n + int(a[0] == "1"))
    elif cnt == 1:
        print(n + 1)
    else:
        print(n+cnt-1 - int(a[0] == "0" and cnt > 2))

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?

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$$$.

For a given array $$$x$$$ of length $$$m$$$, what is the condition that $$$\operatorname{med}(x_1, x_2, \ldots, x_m) \le k$$$?

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?

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.

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:

1. The first and second subarrays have non-negative sums.
2. The second and third subarrays have non-negative sums.
3. The first and third subarrays have non-negative sums.

Use prefix/suffix sums and maximums/ minimums to help you compute the answer in linear time.

Read the hints.

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$$$.

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$$$.

As both cases can be checked with a few array passes, the time and memory complexities are $$$O(n)$$$ per testcase.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
int n,k,arr[maxn],suf[maxn],minsuf[maxn];
bool check_prefix_and_middle(){
   suf[n]=minsuf[n]=arr[n];
   for(int i=n-1;i>=1;i--){
      suf[i]=suf[i+1]+arr[i];
      minsuf[i]=min(minsuf[i+1],suf[i]);
   }
   int s=0;
   for(int i=1;i+2<=n;i++){
      s+=arr[i];
      if(s<0)
         continue;
      if(suf[i+1]>=minsuf[i+2])
         return true;
   }
   return false;
}
void solve(){
   cin>>n>>k;
   for(int i=1;i<=n;i++)
      cin>>arr[i];
   for(int i=1;i<=n;i++)
      if(arr[i]<=k)
         arr[i]=1;
      else
         arr[i]=-1;

   int a=n+1,b=-1;
   int s=0;
   for(int i=1;i<=n;i++){
      s+=arr[i];
      if(s>=0){
         a=i;
         break;
      }
   }
   s=0;
   for(int i=n;i>=1;i--){
      s+=arr[i];
      if(s>=0){
         b=i;
         break;
      }
   }
   if(a+1<b){
      cout<<"YES\n";
      return;
   }
   if(check_prefix_and_middle()){
      cout<<"YES\n";
      return;
   }
   for(int i=1;i<n-i+1;i++)
      swap(arr[i],arr[n-i+1]);
   if(check_prefix_and_middle()){
      cout<<"YES\n";
      return;
   }
   cout<<"NO\n";
   return;
}
int main(){
   int t;
   cin>>t;
   while(t--)
      solve();
   return 0;
}

def check_prefix_and_middle(n, arr):
    suf = [0] * (n + 1)
    minsuf = [0] * (n + 1)
    suf[n] = minsuf[n] = arr[n - 1]

    for i in range(n - 2, -1, -1):
        suf[i + 1] = suf[i + 2] + arr[i]
        minsuf[i + 1] = min(minsuf[i + 2], suf[i + 1])

    s = 0
    for i in range(n - 2):
        s += arr[i]
        if s < 0:
            continue
        if suf[i + 2] >= minsuf[i + 3]:
            return True

    return False

def solve():
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))

    # Transform the array based on the value of k
    for i in range(n):
        arr[i] = 1 if arr[i] <= k else -1

    a, b = n + 1, -1
    s = 0

    for i in range(n):
        s += arr[i]
        if s >= 0:
            a = i + 1
            break

    s = 0
    for i in range(n - 1, -1, -1):
        s += arr[i]
        if s >= 0:
            b = i + 1
            break

    if a + 1 < b:
        print("YES")
        return

    if check_prefix_and_middle(n, arr):
        print("YES")
        return

    arr.reverse()

    if check_prefix_and_middle(n, arr):
        print("YES")
        return

    print("NO")

t = int(input())
for _ in range(t):
    solve()

Solve the problem if you need to find the smallest $$$k$$$ for which the answer is YES.

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.

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.

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.

But how can we guarantee elements at some position will not get deleted?

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?

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.

Read the hints.

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.

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.

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)$$$.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
int n,a[maxn],p[maxn];
void construct(vector<int> pos,vector<int> nums,int layer){
   sort(nums.begin(),nums.end());
   if(pos.size()==1){
      p[pos[0]]=nums[0];
      return;
   }
   vector<int> keep,rem;
   vector<bool> spec;
   for(int x:pos)
      if(a[x]>layer){
         keep.push_back(x);
      }
   if(layer%2==1)
      reverse(nums.begin(),nums.end());
   vector<int> newnums;
   for(int it=1;it<=keep.size();it++){
      newnums.push_back(nums.back());
      nums.pop_back();
   }
   construct(keep,newnums,layer+1);
   reverse(nums.begin(),nums.end());
   int last;
   for(int x:pos){
      last=x;
      if(a[x]>layer)
         break;
      p[x]=nums.back();
      nums.pop_back();
   }
   reverse(nums.begin(),nums.end());
   for(int x:pos){
      if(x<last)
         continue;
      if(a[x]>layer)
         continue;
      p[x]=nums.back();
      nums.pop_back();
   }
}
void solve(){
   cin>>n;
   for(int i=1;i<=n;i++)
      cin>>a[i];
   for(int i=1;i<=n;i++)
      if(a[i]<=0)
         a[i]=1e9;
   vector<int> A;
   for(int i=1;i<=n;i++)
      A.push_back(i);
   construct(A,A,1);
   for(int i=1;i<=n;i++)
      cout<<p[i]<<" \n"[i==n];
}
int main(){
   int T;
   cin>>T;
   while(T--)
      solve();
}

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> a(n), p(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        int mx = max(0, *max_element(a.begin(), a.end())) + 1;
        for (int i = 0; i < n; i++) if (a[i] == -1) a[i] = mx;
 
        int l = 1, r = n;
        for (int k = 1; k <= mx; k++)
        {
            int mr = n - 1;
            while (mr >= 0 && a[mr] <= k) mr--;
            for (int i = 0; i < mr; i++)
            {
                if (a[i] == k)
                {
                    p[i] = ((k & 1) ? r-- : l++);
                }
            }
            for (int i = n - 1; i > mr; i--)
            {
                if (a[i] == k)
                {
                    p[i] = ((k & 1) ? r-- : l++);
                }
            }
        }
        for (int i = 0; i < n; i++) cout << p[i] << " \n"[i == n - 1];
    }
    return 0;
}

I came up with this problem while writing the generator for 1900F - Local Deletions.

When is the solution trivially -1?

When it is impossible to do any operation and array is not sorted in the beginning. Is that enough though?

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.

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$$$.

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.

• We do operation on indices $$$a$$$ and $$$b$$$ and we make it so that $$$value[a] := k - value[c]$$$ and $$$value[b] := value[c]$$$.
• We do operation on indices $$$a$$$ and $$$c$$$ and we make it so that $$$value[a] := k - value[d]$$$ and $$$value[c] := value[d]$$$.
• We do operation on indices $$$a$$$ and $$$d$$$ and we make it so that $$$value[a] := k - value[b]$$$ and $$$value[d] := value[b]$$$.

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.

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?

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?

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.

• We do operation on indices $$$a$$$ and $$$b$$$ and we make it so that $$$value[a] := k - value[1]$$$ and $$$value[b] := value[1]$$$.
• We do operation on indices $$$1$$$ and $$$a$$$ and we make it so that $$$value[1] := k - value[n]$$$ and $$$value[a] := value[n]$$$.

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.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
int n,k,arr[maxn],A,B,p[maxn];
map<int,int> pos;
vector<tuple<int,int,int>> V; /// All operations
void dooperation(int a,int b,int x){
   arr[a]-=x;
   arr[b]+=x;
   V.push_back(make_tuple(a,b,x));
}
void setvalue(int pos,int b,int target){ /// Does operation on (pos, b) such that value of pos becomes target
   if(arr[pos]==target)
      return;
   int dif=target-arr[pos];
   dooperation(b,pos,dif);
}
void performswap(int x,int y){
   int vx=arr[x],vy=arr[y];
   setvalue(A,B,k-vx);
   setvalue(x,A,vy);
   setvalue(y,A,vx);
}
bool cmp(int a,int b){
   return arr[a]<arr[b];
}
void solve(){
   pos.clear();
   V.clear();
   A=B=-1;
   cin>>n>>k;
   for(int i=1;i<=n;i++)
      cin>>arr[i];
   bool issorted=true;
   for(int i=2;i<=n;i++)
      if(arr[i]<arr[i-1])
         issorted=false;
   if(issorted){
      cout<<"0\n";
      return;
   }
   for(int i=1;i<=n;i++){
      if(pos.find(k-arr[i])!=pos.end()){
         B=i;
         A=pos[k-arr[i]];
         break;
      }
      pos[arr[i]]=i;
   }
   if(A==-1){
      cout<<"-1\n";
      return;
   }
   if(A!=1){
      setvalue(A,B,k-arr[1]);
      setvalue(1,A,k-arr[B]);
      A=1;
   }
   if(B!=n){
      setvalue(B,A,k-arr[n]);
      setvalue(n,B,k-arr[A]);
      B=n;
   }
   vector<int> invp;
   for(int i=2;i<n;i++)
      invp.push_back(i);
   sort(invp.begin(),invp.end(),cmp);
   for(int i=0;i<invp.size();i++)
      p[invp[i]]=i+2;
   for(int i=2;i<n;i++){
      if(p[i]==i)
         continue;
      performswap(p[i],i);
      swap(p[p[i]],p[i]);
      i--;
   }
   setvalue(B,A,k);
   cout<<V.size()<<"\n";
   for(auto x:V)
      cout<<(get<0>(x))<<" "<<(get<1>(x))<<" "<<(get<2>(x))<<"\n";
   return;
}
int main(){
   int T;
   cin>>T;
   while(T--)
      solve();
   return 0;
}

Solve the problem in $$$\lceil \frac{3n}{2} \rceil$$$ queries.

If problem had queries of form "What is nor of some interval [$l$, $r$]", how would you answer them?

You can look at all the bits separately and answer for each.

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$$$.

If $$$x=l$$$, the bit will be $$$1$$$ if $$$l$$$ and $$$r$$$ are the same parity and otherwise $$$0$$$.

If $$$x \lt l$$$, the bit will be $$$1$$$ if $$$l$$$ and $$$r$$$ are different parity and otherwise $$$0$$$.

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.

That means there will be only $$$O(k)$$$ different values of nor of an interval ending at some $$$r$$$.

Read the hints.

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)$$$.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
int N,M,arr[maxn],pref[maxn][25],logg,st[4*maxn],stk;
int nor(int a,int b){
   return M^(a|b);
}
int getlog(int x){
   int ans=-1;
   while(x){
      ans+=1;
      x/=2;
   }
   return ans;
}
int internor(int l,int r){
   if(l<=0 or l>r)
      return 0;
   if(l==r)
      return arr[r];
   int ans=0;
   for(int j=0;j<=logg;j++){
      int bit=(1<<j);
      if(pref[r][j]<l)
         if((r-l+1)%2==1)
            bit=0;
      if(pref[r][j]==l)
         if((r-l+1)%2==0)
            bit=0;
      if(pref[r][j]>l)
         if((r-pref[r][j]+1)%2==1)
            bit=0;
      ans+=bit;
   }
   return ans;
}
void update(int lb,int rb,int x,int pos=1,int l=1,int r=stk){
   lb=max(1,lb);
   rb=min(N,rb);
   if(rb<lb)
      return;
   if(l==lb and r==rb){
      st[pos]=max(st[pos],x);
      return;
   }
   int mid=(l+r)/2;
   if(rb<=mid)
      return update(lb,rb,x,pos*2,l,mid);
   if(lb>mid)
      return update(lb,rb,x,pos*2+1,mid+1,r);
   update(lb,mid,x,pos*2,l,mid);
   update(mid+1,rb,x,pos*2+1,mid+1,r);
   return;
}
int get(int pos){
   pos+=stk-1;
   int v=0;
   while(pos){
      v=max(v,st[pos]);
      pos/=2;
   }
   return v;
}
void solve(){
   int K;
   cin>>N>>K;
   stk=1;
   while(stk<N)
      stk<<=1;
   M=(1<<K)-1;
   for(int i=1;i<=N;i++)
      cin>>arr[i];

   logg=getlog(M+1)-1;
   for(int i=1;i<=N;i++){
      for(int j=0;j<=logg;j++)
         if(arr[i]&(1<<j))
            pref[i][j]=i;
         else
            pref[i][j]=pref[i-1][j];
   }
   for(int i=1;i<=N;i++){
      for(int j=0;j<=logg;j++){
         int p=pref[i][j];
         for(int add=-2;add<=2;add++)
            update(p+add,i,internor(p+add,i));
      }
      update(1,i,internor(1,i));
   }
   for(int i=1;i<=N;i++)
      cout<<get(i)<<" \n"[i==N];
}
void reset(){
   for(int i=0;i<=N+2;i++){
      arr[i]=0;
      for(int j=0;j<=logg+2;j++)
         pref[i][j]=0;
   }
   logg=0;
   for(int i=0;i<=stk+stk;i++)
      st[i]=0;
}
int main(){
   int T=1;
   cin>>T;
   while(T--){
      solve();
      reset();
   }
   return 0;
}

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.

Assume that cells $$$i-1$$$, $$$i$$$, and $$$i+1$$$ are covered in water. What happens if you remove water from cell $$$i$$$?

The water at position $$$i$$$ is replaced as both cells $$$i-1$$$ and $$$i+1$$$ have water in them.

Read the hints.

If there are 3 consecutive empty cells $$$i-1$$$, $$$i$$$, $$$i+1$$$, we can place water in cells $$$i-1$$$ and $$$i+1$$$ and then move water from cell $$$i$$$ to all other cells. If there are no such cells, we have to place water on every empty cell.

So if we find substring ''...'' in the array, the answer is $$$2$$$, otherwise the answer is the number of empty cells.

Time and memory complexities are $$$O(N)$$$.

Solve the problem if it is required that each cell is filled with water, or next to at least $$$1$$$ cell that is filled with water.

Check if only digits $$$1$$$ can remain. The situation is similar for checking if only digits $$$2$$$ or only digits $$$3$$$ can remain.

Try to find something that stays the same after each operation.

Look at the parity of the numbers.

The parity of each number changes after an operation. That means that if $$$2$$$ numbers have the same parity, they will always have the same parity. If they had different parity, their parities stay different.

Read the hints.

If the parity of $$$b$$$ and $$$c$$$ is not the same, then it is impossible for only digits $$$1$$$ to remain on the board, as it would require $$$b = c = 0$$$. Otherwise, the following construction will leave only digits $$$1$$$ on the board.

First remove digits $$$2$$$ and $$$3$$$ and write digit $$$1$$$ while $$$b \gt 0$$$ and $$$c \gt 0$$$. If $$$b=c$$$, then we are done. Otherwise, without loss of generality assume $$$b \gt c$$$. That means that after the operations $$$c=0$$$ and $$$b$$$ is even (Because $$$b$$$ and $$$c$$$ are the same parity). Now we perform the following $$$2$$$ operations $$$\frac{b}{2}$$$ times to get only digits $$$1$$$ left. Remove digits $$$1$$$ and $$$2$$$ and add digit $$$3$$$. After that remove digits $$$2$$$ and $$$3$$$ and add digit $$$1$$$. An effective change of these $$$2$$$ operations is the reduction of $$$b$$$ by $$$2$$$.

Time and memory complexities are $$$O(1)$$$.

Come up with a problem that uses a similar idea and try to solve it. A lot of beginner problems use a similar idea.

Solve the problem if all of the characters on vertices are 'U'.

We can run DFS from the root. Using it we can calculate the number of edges that we have to traverse to get to every edge. Just output the smallest value among all the leaves.

Modify the DFS such that it takes into account that traversing some edges does not require an operation.

Add weights to the edges.

Read the hints.

We will make edges from a vertex to its children. The weight of that edge will be $$$1$$$ unless one of the following holds:

• The weight of an edge between a vertex and its left child will be $$$0$$$ if the letter written on that vertex is 'L'.

• The weight of an edge between a vertex and its right child will be $$$0$$$ if the letter written on that vertex is 'R'.

Now we run a modified DFS to find the distance of each vertex from the root, but with weighted edges. We output the minimal value among all the leaves.

Time and memory complexities are $$$O(N)$$$.

Solve the problem if after reaching a leaf, Keksic can teleport to any other leaf that he chooses and then needs to get back to the root, or report that it is impossible for him to complete such a travel.

Let $$$m$$$ be the biggest value in the array. Calculate array $$$x$$$ such that $$$x_i$$$ ($$$1 \le i \le m$$$) is the number of triples which have $$$\gcd$$$ of $$$i$$$. Then the answer is the sum of $$$i \cdot x_i$$$ over all $$$i$$$ ($$$1 \le i \le m$$$).

Value of $$$\lfloor \frac{m}{1} \rfloor + \lfloor \frac{m}{2} \rfloor + \lfloor \frac{m}{3} \rfloor + \ldots + \lfloor \frac{m}{m} \rfloor$$$ is around $$$m log m$$$.

We calculate $$$x_i$$$ from $$$x_m$$$ to $$$x_1$$$. For some $$$i$$$, we can first calculate the number of triples that have a value of function $$$f$$$ that is an integer multiple of $$$i$$$, and then from it subtract $$$x_{2i}, x_{3i}, x_{4i} \ldots$$$. Because of the previous hint, the subtractions will be quite fast.

Now the question is how to calculate the number of triples that have a value of function $$$f$$$ that is an integer multiple of $$$i$$$.

Numbers up to $$$100\,000$$$ can have at most $$$128$$$ divisors.

As the order in which numbers are given does not matter, we can sort the array. Now for each number $$$d$$$ ($$$1 \le d \le M$$$) store indices of all numbers that are divisible by $$$d$$$ in an array of vectors. Now we will for each number $$$d$$$ ($$$1 \le d \le m$$$) count the number of triples.

To find the number of triples that have a gcd value that is an integer multiple of $$$d$$$, we can do the following. We go over the index of the number that will be value $$$b$$$ in the function. We can utilize the vectors we calculated in the previous step for that. Say that the current index is $$$i$$$. Then for value $$$c$$$ we can pick any number with an index larger than $$$i$$$ as the array is sorted. For value $$$a$$$, we can pick any of the numbers divisible by $$$d$$$ with an index less than $$$i$$$, the number of which we can get from the vector. By multiplying those $$$2$$$ numbers we get the number of triples that have $$$a_i$$$ as their middle value.

As numbers can have up to $$$128$$$ divisors, the step above is quite fast.

Total time complexity is $$$O(m log m + n log n + 128 \cdot n)$$$. Total memory complexity is $$$O(m + 128 \cdot n)$$$.

Solve the problem if $$$f(a,b,c) = \gcd (a,c)$$$.

Try to simplify graph $$$H$$$.

Look at strongly connected components of $$$G$$$, and what happens with them.

Use dp to find the answer.

The main observation is what $$$H$$$ looks like. All the strongly connected components (SCC) in $$$G$$$ will become fully connected subgraphs in $$$H$$$. Secondly, take any two vertices $$$a$$$ and $$$b$$$ such that $$$a$$$ and $$$b$$$ are not in the same SCC. We can let $$$S_a$$$ be a set of vertices that are in the same SCC as $$$a$$$ ($$$a$$$ included). Similarly, $$$S_b$$$ is a set of vertices that are in the same SCC as $$$b$$$. If there is an edge going from $$$a$$$ to $$$b$$$, then for any two vertices $$$x$$$ and $$$y$$$ such that $$$x$$$ belongs to $$$S_a$$$ and $$$y$$$ belongs to $$$S_b$$$, there is an edge going from $$$x$$$ to $$$y$$$. Both of the previously stated facts about the graph can be proven by induction.

Now, let's say that there is the longest path that goes through at least one vertex of an SCC. Then that path goes through all the vertices in the SCC, due to all vertices in SCC being connected to the same vertices outside the SCC and due to the fact that SCC is a complete subgraph.

Now we can construct the graph $$$H'$$$. Each of the SCCs from $$$H$$$ will be a vertex in $$$H'$$$. The number on the vertex will be equal to the sum of all numbers on the vertices of the SCC that it was constructed from. Edges between two new vertexes will be added if there is an edge between their original SCCs. The edge will have a weight equal to the size of the SCC that it is going into. An additional vertex will be added at index $$$0$$$ and an edge will be made between it and all other vertices with $$$0$$$ ingoing edges. Weight will be determined based on the size of the SCC of the vertex that the edge is going into.

Due to the previous observations, the answer for the $$$H'$$$ will be the same as the answer for the $$$H$$$. However, notice that $$$H'$$$ is a DAG. That means that the answer for it can be computed using DP after topological ordering.

Total time and memory complexity is $$$O(n)$$$.

We will define the value of the path as the biggest value of a vertex on the path. Among the values of all the longest paths, find the median one. It is guaranteed that there are at most $$$10^{18}$$$ longest paths starting from each node. (So basically, you can ignore overflow in the number of paths) The rest of the constraints are the same.

Solve the problem for $$$q=1$$$.

We can just simulate the process. Each operation removes at least half of the elements, meaning that we will perform at most $$$log n$$$ operations.

Solve the problem if each $$$l_i = 1$$$. So basically, solve the problem for each prefix.

Keep values that are in the array after $$$1$$$, $$$2$$$, $$$3$$$, $$$\cdots$$$, $$$log n$$$ operations. Let's call those array's layers. Layer $$$0$$$ is an array after $$$0$$$ operations, layer $$$1$$$ after $$$1$$$ operation, and so on. When we add a value to the end of the layer, only $$$1$$$ number that was previously local extreme (local minimum or maximum, depending on layer) might unbecome local extreme if the new value becomes local extreme. So we can just propagate this update to all layers.

Try to simulate the process of updating described in hint $$$4$$$. Also, notice that if the array is longer than $$$3$$$, we can handle prefix and suffix updates separately.

Read the hints.

Now we will precompute and store the array after each operation on the entire permutation. We will call those array layers.

We can now solve queries in $$$O(log n)$$$.

If a query involves a small number of elements, we can just brute force it. Otherwise, we do the following:

Now let's define our queries a bit differently. We are given some array $$$x$$$, which will be a subarray of some layer, and $$$2$$$ values, $$$a$$$ and $$$b$$$. We will get array $$$y$$$ by appending $$$a$$$ to the start of $$$x$$$ and appending $$$b$$$ to the end of $$$x$$$. We are interested in the value of $$$f$$$($$$y$$$). It is easy to see that all queries involving $$$3$$$ or more elements can be converted into the modified query.

If $$$|y|$$$ is small, we can just brute force it. Otherwise, we can transform it into a query on the next layer in constant time, or in $$$O(log n)$$$.

Now, the first thing to notice is that all elements in $$$x$$$ that are neither first nor last will be deleted only if they were deleted when we performed operations on the whole permutation. That means that they will represent some interval on the next layer, let's call it $$$z$$$. (That interval can be found either with binary search or in $$$O(1)$$$ with precomputation) It holds that $$$ |z| $$$ is around half of $$$|x|$$$. Now, notice that among $$$a$$$ and the first element of $$$x$$$, there has to be at least one deletion. The same goes for the last element of $$$x$$$ and $$$b$$$.

So now we have transformed the query onto the next level in $$$O(1)$$$, or $$$O(log n)$$$. As we will do at most $$$O(log n)$$$ such transformations, the complexity of a single query is either $$$O(log n)$$$ or $$$O(log^2 n)$$$ depending on the way we find the next interval, both of which should be fast enough to pass.

Total time complexity: $$$O(n + q log n)$$$ or $$$O(n + q log^2 n)$$$. Total memory complexity: $$$O(n+q)$$$

2103D - Local Construction