brute force dp math

If Bob is winning for given $$$n$$$ stones then Alice will win for $$$n + 2$$$ stones and $$$n + 3$$$ stones, because in $$$n + 2$$$ case Alice will remove $$$2$$$ stones and in $$$n + 3$$$ case Alice will remove $$$3$$$ stones resulting in $$$n$$$ stones where players switch their turns i.e., now Bob will play like first player for these $$$n$$$ stones, so obviously Alice will win.

From this information we can create $$$dp$$$ table, where $$$dp[x]$$$ refers who will win if pile contains $$$x$$$ stones. The base case is for $$$n = 1$$$ where Bob will win.

So from this $$$dp$$$ table , if Alice is already winning no need to add stones , otherwise we will iterate untill we reach the state where Alice will win.

If we observe the pattern, it will look like LWWWLLWWWLLWWWLLWWWLL... where $$$L$$$ means Alice loosing, $$$W$$$ means Alice winning. we can easily see from the pattern that if $$$n$$$ mod $$$5 \ge 2$$$ no need to add stones, Otherwise answer will be $$$2 - n$$$ mod $$$5$$$.

Time Complexity : $$$O(t)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int r=(n%5);
        if(r==0) cout<<"2\n";
        else if(r==1) cout<<"1\n";
        else cout<<"0\n";
    }
}

Good problem! :
Average problem :
Bad problem... :

constructive algorithm implementation

The Upperbound value of $$$k$$$ for given $$$n$$$ is $$$⌈ \frac{n}{2} ⌉^2$$$, because the top-left square grid containing $$$⌈ \frac{n}{2} ⌉^2$$$ cells can have any characters which will mirror the other cells.

There are many ways to construct the grid, the below implementation is one of them.

Time Complexity : $$$O(n^2)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        int maxi=((n+1)/2)*((n+1)/2);
        if(k>maxi) cout<<"-1\n";
        else{
            vector<vector<int>> v(n,vector<int>(n));
            int val=0;
            for(int i=0;i<(n+1)/2;i++){
                for(int j=0;j<(n+1)/2;j++){
                    v[i][j]=val;
                    v[i][(n-j-1)]=val;
                    val=(val+1)%k;
                }
            }
            int x=1;
            if(n%2) x++;
            for(int i=(n+1)/2;i<n;i++){
                for(int j=0;j<n;j++){
                    v[i][j]=v[i-x][j];
                }
                x+=2;
            }
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    cout<<(char)('a'+v[i][j]);
                }
                cout<<"\n";
            }
        }
    }
}

Good problem! :
Average problem :
Bad problem... :

number theory math

General idea of the solution is to store the count of the factors of all $$$a_i(1 \le i \le n)$$$, in that the answer is the maximum factors whose count is greater than or equal to $$$n-2$$$, because we can change the remaining elements to this factor. But this solution is too slow. Infact we don't need to calculate all elements factors, it is sufficient to calculate any $$$3$$$ elements factors. Because if you are interested in any $$$4$$$-th element factors then if those factor is not included in the previous $$$3$$$ elements choosen then its not useful because we can only change upto maximum $$$2$$$ elements.

Note that we can actually also solve this problem by taking factors of only $$$1$$$ element, below implementation shows this.

Time Complexity : $$$O(nD(x)+t \sqrt{x})$$$, where $$$x$$$ is any element from $$$a$$$, $$$D(x)$$$ means number of factors of $$$x$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
vector<ll> get(ll n){
    vector<ll> v;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            v.push_back(i);
            ll j=(n/i);
            if(j!=i) v.push_back(j);
        }
    }
    return v;
}
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vector<ll> a(n);
        ll ans=0;
        for(ll i=0;i<n;i++){
            cin>>a[i];
            ans=__gcd(ans,a[i]);
        }
        sort(a.begin(),a.end());
        vector<ll> v=get(a[0]);
        for(ll i=0;i<(ll)v.size();i++){
            ll cnt=0;
            for(ll j=0;j<n;j++) if(a[j]%v[i]==0) cnt++;
            if(cnt>=(n-2)) ans=max(ans,v[i]);
        }
        vector<ll> p,s;
        for(ll i=1;i<n;i++) p.push_back(a[i]);
        s=p;
        for(ll i=1;i<(ll)p.size();i++) p[i]=__gcd(p[i],p[i-1]);
        for(ll i=(ll)s.size()-2;i>=0;i--) s[i]=__gcd(s[i],s[i+1]);
        for(ll i=0;i<(ll)p.size();i++){
            ll val=0;
            if(i-1>=0) val=__gcd(val,p[i-1]);
            if(i+1<(ll)s.size()) val=__gcd(val,s[i+1]);
            ans=max(ans,val);
        }
        ll val=0;
        for(ll i=2;i<n;i++) val=__gcd(val,a[i]);
        ans=max(ans,val);
        cout<<ans<<"\n";
    }
}

can you solve the problem for $$$1 \le a_i \le 10^{18}$$$ ?

Good problem! :
Average problem :
Bad problem... :

data structure greedy

Let's first solve the problem for the entire array. Consider the prefix sum array $$$S$$$, where we want all $$$S[i] > 0$$$.

Consider how a swap operation would change the $$$S$$$ array. Clearly, we only pick $$$a[i] = -1$$$ and $$$a[j] = 1$$$. This makes $$$S[i, \dots, j-1]$$$ increase by 2.

Thus, we have a greedy strategy: each time, select the smallest $$$i$$$ and the largest $$$j$$$ such that $$$a[i] = -1$$$ and $$$a[j] = 1$$$. Let $$$\text{minS} = \min(S[1, \dots, n])$$$. With each operation, $$$\text{minS}$$$ increases by 2, so the required number of operations is easy to calculate.

Returning to the original problem, we can use a segment tree to maintain $$$S$$$. For operation 2, this is simply a range addition operation on the segment tree. For operation 1, we can easily find the $$$\text{minS}$$$ for each interval.

Time Complexity : $$$O(nlogn)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

vector<ll> tree,lazy,v1;

void build(ll v, ll tl, ll tr){
    if(tl==tr) tree[v]=v1[tl];
    else{
        ll m=(tl+tr)/2;
        build(2*v+1,tl,m);
        build(2*v+2,m+1,tr);
        tree[v]=min(tree[2*v+1],tree[2*v+2]);
    }
}

void push(ll v){
    tree[2*v+1]+=lazy[v];
    tree[2*v+2]+=lazy[v];
    lazy[2*v+1]+=lazy[v];
    lazy[2*v+2]+=lazy[v];
    lazy[v]=0;
}

ll get(ll v, ll tl, ll tr, ll l, ll r){
    if(l>r) return 1e18;
    if(l==tl && r==tr) return tree[v];
    push(v);
    ll m=(tl+tr)/2;
    ll val1=get(2*v+1,tl,m,l,min(r,m));
    ll val2=get(2*v+2,m+1,tr,max(l,m+1),r);
    return min(val1,val2);
}

void update(ll v, ll tl, ll tr, ll l, ll r, ll x){
    if(l>r) return;
    if(l==tl && r==tr){
        tree[v]+=x;
        lazy[v]+=x;
    }
    else{
        push(v);
        ll m=(tl+tr)/2;
        update(2*v+1,tl,m,l,min(r,m),x);
        update(2*v+2,m+1,tr,max(l,m+1),r,x);
        tree[v]=min(tree[2*v+1],tree[2*v+2]);
    }
}
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n,q;
        cin>>n>>q;
        vector<ll> a(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        v1.clear();
        v1=a;
        for(ll i=1;i<n;i++) v1[i]+=v1[i-1];
        tree.clear();
        tree.resize(4*n);
        lazy.clear();
        lazy.resize(4*n);
        build(0,0,n-1);
        while(q--){
            ll type;
            cin>>type;
            if(type==1){
                ll l,r;
                cin>>l>>r;
                l--;
                r--;
                ll sum=get(0,0,n-1,r,r);
                if(l-1>=0) sum-=get(0,0,n-1,l-1,l-1);
                if(sum<=0) cout<<"-1\n";
                else{
                    ll val=get(0,0,n-1,l,r);
                    if(l-1>=0) val-=get(0,0,n-1,l-1,l-1);
                    if(val>0) cout<<"0\n";
                    else{
                        val=-val;
                        cout<<(val+2)/2<<"\n";
                    }
                }
            }
            else{
                ll pos;
                cin>>pos;
                pos--;
                if(a[pos]==1) update(0,0,n-1,pos,n-1,-2);
                else update(0,0,n-1,pos,n-1,2);
                a[pos]*=-1;
            }
        }
    }
}

can you solve the problem for range update instead of point update ?

Good problem! :
Average problem :
Bad problem... :

constructive algorithm tree

There will be no tree if the grid $$$a$$$ doesn't satisfy atleast one of the following condition :

1. $$$a_{ij} = a_{ji}$$$
2. $$$a_{ii}=i$$$
3. $$$a_{ij} \le a_{(a_{ij})j}$$$

Otherwise we can construct the tree in many ways, one of the possible way is:

1. Lets create a parent array $$$par$$$ where $$$par[x]$$$ denotes the parent of node $$$x$$$, initially $$$par[i]=-1$$$ for every $$$i(1 \le i \le n)$$$.

2. we will iterate for $$$x = 1, 2, 3, \cdots , n$$$ in this order and for every $$$y(1 \le y \le n)$$$ we will update $$$par[y] = x$$$ if $$$a_{xy}=x$$$.

Time Complexity : $$$O(n^2)$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<vector<int>> v(n,vector<int>(n));
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>v[i][j];
                v[i][j]--;
            }
        }
        bool ok=true;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==j && v[i][j]!=i) ok=false;
                if(v[i][j]!=v[j][i]) ok=false;
                if(v[i][j]>min(i,j)) ok=false;
                if(i<j){
                    if(v[i][j]!=v[v[i][j]][j]) ok=false;
                }
            }
        }
        if(ok){
            vector<int> par(n,0);
            par[0]=-1;
            for(int i=1;i<n;i++){
                for(int j=0;j<n;j++){
                    if(i!=j && v[i][j]==i) par[j]=i;
                }
            }
            for(int i=1;i<n;i++){
                cout<<par[i]+1<<" "<<i+1<<"\n";
            }
        }
        else cout<<"-1\n";
    }
}

Good problem! :
Average problem :
Bad problem... :

dp tree

We can solve this problem using Dynamic programming. Perform $$$DFS$$$(depth first search) and solve the problem from the leaves to root.

Let $$$dp_{ij}$$$ denotes the number of ways to use the nodes from the subtree of $$$i$$$ such that there are $$$j$$$ connected components. Before processing $$$i$$$ we need to combine the tables of $$$dp_k$$$, where $$$k$$$ is the set of childeren nodes of $$$i$$$. In this combining process every $$$j_1$$$ number of components in $$$dp_{i_{1}j_{1}}$$$ and every $$$j_2$$$ number of components in $$$dp_{i_{2}j_{2}}$$$ will contribute for new $$$dp$$$ states $$$j_1 + j_2$$$ number of components, where $$$i_1$$$ and $$$i_2$$$ belongs to set $$$k$$$.

Time Complexity : $$$O(n^2)$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

ll mod=1e9+7;

long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}
 
long long modular_inverse(long long n){
  return power(n,mod-2);
}

#define MAXN 2000005
 
long long factorial[MAXN];
long long invfact[MAXN];
 
void cfact(){
  long long i;
  factorial[0]=1;
  factorial[1]=1;
  for(i=2;i<MAXN;i++){
    factorial[i]=factorial[i-1]*i;
    factorial[i]%=mod;
  }
  invfact[MAXN-1]=modular_inverse(factorial[MAXN-1]);
  for(i=MAXN-2;i>=0;i--){
    invfact[i]=invfact[i+1]*(i+1);
    invfact[i]%=mod;
  }
}
 
long long calcnCr(long long n,long long k){
  if(k<0 || n<k){return 0;}
  return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod;
}

vector<vector<ll>> adj,dp;
vector<ll> sz,dp1,v1;
ll xx,yy;

void dfs(ll x, ll p){
    dp[x][0]=1;
    for(auto i:adj[x]){
        if(i!=p){
            dfs(i,x);
            for(ll j=0;j<=sz[x]+sz[i];j++) dp1[j]=0;
            for(ll j=0;j<=sz[x];j++){
                for(ll k=1;k<=sz[i];k++){
                    dp1[j+k]=(dp1[j+k]+(((dp[x][j]*dp[i][k])%mod)*calcnCr(j+k-v1[x]-v1[i],j-v1[x]))%mod)%mod;
                }
            }
            sz[x]+=sz[i];
            v1[x]+=v1[i];
            for(ll j=0;j<=sz[x];j++){
                dp[x][j]=dp1[j];
            }
        }
    }
    sz[x]++;
    for(ll j=0;j<=sz[x];j++) dp1[j]=0;
    for(ll j=0;j<sz[x];j++){
        dp1[j+1]=(dp1[j+1]+(dp[x][j]*(j+1-v1[x]))%mod)%mod;
        dp1[j]=(dp1[j]+(dp[x][j+1]*j)%mod)%mod;
        dp1[j]=(dp1[j]+(dp[x][j]*(2*j-v1[x]))%mod)%mod;
    }
    for(ll j=0;j<=sz[x];j++){
        dp[x][j]=dp1[j];
    }
}
 
int main(){
    fast;
    cfact();
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        adj.clear();
        adj.resize(n);
        for(ll i=0;i<n-1;i++){
            ll u,v;
            cin>>u>>v;
            u--;
            v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        dp.clear();
        dp.resize(n+2);
        for(ll i=0;i<n+2;i++) dp[i].resize(n+2);
        dp1.clear();
        dp1.resize(n+2);
        sz.clear();
        sz.resize(n+2);
        v1.clear();
        v1.resize(n+2);
        dfs(0,-1);
        cout<<dp[0][1]<<"\n";
    }
}

can you construnct any permutation which satisfies the condition for $$$n \le 10^6$$$ ?

Good problem! :
Average problem :
Bad problem... :

It will posted after the first solve or tomorrow

It will posted after the first solve or tomorrow

It will posted after the first solve or tomorrow

Good problem! :
Average problem :
Bad problem... :

TheForces is a project uniting individuals with a shared interest in competitive programming contests. You can join our discord server with more than $$$2500$$$ members to communicate with founders and members of TheForces.

In the other words TheForces rounds are series of educational contests for beginners to masters which are created by a group of CP lovers in the CF community, It's where anyone can propose and prepare his own interesting problems and receive money!

Not to mention that we've already created two official codeforces Div($$$1 + 2$$$) rounds before ;) So join us now!

Discord link

TheForces website

The problemset has at least $$$0$$$ bruteforce problem.

For odd values of $$$n$$$ we can re-express string $$$s$$$ as

Note that $$$s_1+s_2+...+s_{\lfloor \frac{n}{2} \rfloor}=s_{\lceil \frac{n}{2} \rceil+1}+....+s_n$$$ , so we can assume the sum as $$$f$$$.

And let's denote the median digit by $$$h$$$ , thus the sum is $$$2f+h$$$ , it can be shown that $$$h$$$ can be possibly any digit , thus we can construct all sums which lies between minimum and maximum inclusive .

Now Let's do the same for even values of $$$n$$$ we can re-express $$$s$$$ as

Using the symmetric property we can see $$$s_{\lfloor \frac{n}{2} \rfloor}=s_{\lfloor \frac{n}{2} \rfloor+1}$$$ , if we denote one digit by $$$h$$$ thus the sum of medians is $$$2h$$$ and if we denote the left and right segments by $$$f$$$ as we did for odd $$$n$$$ then we have $$$m=2f+2h=2(f+h)$$$ thus for even $$$n$$$ we have an additional condition that sum must be even

Thus Total Complexity for each test case is $$$\mathcal{O}(1)$$$ time .

for _ in range(int(input())): 
  n,m= map(int, input().split())
  if(m >= n and m <= 9 * n and (n % 2 != 0 or m % 2 == 0)):
    print("YES")
  else:
    print("NO")

If $$$x<z$$$, the answer is obviously $$$-1$$$. We only consider the case of $$$x \ge z$$$.

Maximum number of interviews per day can happen is the number of distinct interviews can happen , which is the number of interviewers times the capacity of each interviewer integer divided by the needed interviewers in one interview , Formally

The construction is simple:

consider a sequence of length $$$x \cdot y$$$ — $$$[1,2,\ldots,x,1,2,\ldots,x,\ldots]$$$ , and simply output consecutive segments of length $$$z$$$ in order.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
 
using namespace std;
 
#define _int64 long long
#define mo 998244353


int main()
{
	int i,j,k,n,l,t,m,x,y,o,b1,z,ans,now;
	scanf("%d",&t);
	for (l=0;l<t;l++)
	{
		scanf("%d%d%d",&x,&y,&z);
		if (z>x)
		{
			printf("0\n");
			continue;
		}
		ans=x*y/z;
		printf("%d\n",ans);
		now=1;
		for (i=0;i<ans;i++)
		{
			for (j=0;j<z;j++)
			{
				printf("%d ",now);
				now++;
				if (now>x) now=1;
			}
			printf("\n");
		}
	}
}

Note $$$f_i=\Sigma_{j=1}^i a_j·...·a_i$$$. We can get $$$f_1=a_1$$$ and $$$f_i=a_i + a_i \cdot f_{i-1}$$$ for $$$2 \le i \le n$$$.

The answer is $$$\Sigma_{i=1}^n f_i$$$.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
 
using namespace std;
 
#define _int64 long long
#define mo 1000000007

int a[1100000];
_int64 d[1100000];

int main()
{
	int i,j,k,n,l,t,m,x,y,o,b1,qq,ll,rr;
	_int64 ans;
	scanf("%d",&t);
	for (l=0;l<t;l++)
	{
		scanf("%d%d",&n,&qq);
		for (i=0;i<n;i++)
			scanf("%d",&a[i]);
		for (o=0;o<qq;o++)
		{
			scanf("%d%d",&ll,&rr);
			ll--;rr--;
			d[ll]=a[ll];
			d[ll]%=mo;
			ans=d[ll];
			for (i=ll+1;i<=rr;i++)
			{
				d[i]=d[i-1]*a[i]+a[i];
				d[i]%=mo;
				ans+=d[i];
				ans%=mo;
			}
			printf("%lld\n",ans);
		}
	}
}

For $$$n,m \ge 4$$$, we have trival construct $$$p_i=i$$$ to make condition $$$1$$$ holds.

Then check all $$$a_i+a_{i+1}=0 (\mod m)$$$, we can just swap $$$a_i$$$ and $$$a_{i-1}$$$ to make condition $$$2$$$ holds.

For $$$n,m < 4$$$, we need to some case work. Be careful of $$$n=4,m=3$$$ case and $$$n=2$$$ case.

For $$$k=3$$$ generate cases separately (Exercise) , for $$$k=2$$$ the permutation $$$[1,2,3,...,n]$$$ always works .

we need to see all cases (pairs) for which violates the condition , well let's see how we determine the number of pairs for only (odd numbers) since even $$$k$$$ can be solved with typical standard permutation .\ Using \textbf{Mod Array} this is how we can get the number of invalid pairs, $$$(0,0)$$$ is always invalid pair , then there are another pairs depending on $$$k$$$ , there are $$$\lfloor \frac{n}{2} \rfloor$$$ different pairs to do sum with, for example $$$k=3 \Rightarrow {(1,2),(2,1)}$$$ which can be counted $$$2 \lfloor \frac{n}{2} \rfloor=n-1$$$ for odd numbers and there's also base case yields $$$n$$$ invalid pairs, Now our mission is to construct a permutation without facing any pair of these. Let's analyze the situation , for all numbers in $$$[1,n]$$$ it has a specific value $$$\mod k$$$ , we want to calculate how many values $$$i$$$ such that : $$$1 \le i \le n$$$ satisfy \ $$$ i \mod k=x$$$ , let's construct a \textbf{Mini Mod Array} that will determine the \textbf{Final Mod Array} and depending on it we'll construct the permutation.

Again we separate 3 because it's an edge case and it's a triangular number of the second degree,Let's see how we can arrange the \textbf{Final Mod Array} , we want to count all the mods by $$$k$$$ for the numbers , it can be calculated as follows:- Considering $$$n \mod k=x$$$\ Every mod has at least $$$\lfloor \frac{n}{k} \rfloor$$$ values for mod in the array , and $$$\forall : 1 \le i \le x$$$ it'll increase by 1 , let's denote the number of mod values such $$$i \textbf{ mod } k =z$$$ appears on the \textbf{Final Mod Array} as $$$c_{z}$$$ , so we obtain the following fact:-

Using The Past Fact , we can construct a valid permutation for all odd $$$k$$$ except $$$3$$$ , let the \textbf{Final Mod Array} be expanded like this :-

Now we let's reflect what we made in the expanded mod array , the sum of each pair can be \textbf{even} because 2 numbers has the same mod and of course won't be divisible by $$$k$$$ , or some number $$$b$$$ will collide with the next so the new number making $$$(2b+1) \mod k$$$ , so since $$$2b+1$$$ is always odd we make sure that $$$2b+1$$$ is not equal to $$$k$$$ by \textit{swap}$$$(\lfloor \frac{k}{2} \rfloor , \lfloor \frac{k}{2} \rfloor -1$$$),Finally still to distribute $$$0$$$'s so that no pair is equal to (0,0) , since

then we can distribute pairs : $$$(k-1,0)$$$ so if $$$c_{k-1}=c_0$$$ we can distribute it like this

and if $$$c_{k-1}=c_0+1$$$ then it can be distributed like this:-

so we make sure that no (0,0) pair is in the expanded mod array. Let's work an example to finish the explanation $$$(n,k)=(20,9)$$$:-

$$$20 \mod 9=2 \Rightarrow c_1=c_2=\lfloor \frac{n}{k} \rfloor+1=3$$$ and $$$c_3=c_4=..=c_8=c_0=2$$$ so the final mod array

Finally generate numbers W.R.T mods , one valid permutation is:-

\textbf{Note: In practice we'll put $$$0$$$ as $$$k$$$ for generating correct answers but mathematically it's just $$$0$$$}\ We used $$$\mathtt{map}$$$ Structure ($$$\mathtt{dict}$$$ in $$$\mathtt{python}$$$) to optimize the storing operation in average $$$\mathcal{O}(1)$$$ time, and constructing operation takes $$$\mathcal{O}(n)$$$ time , since time for storing values in $$$\mathtt{map}$$$ structure we consider the worst case of $$$\mathtt{map}$$$ , so complexity (worst case) is $$$\mathcal{O}(n+k)$$$ because the $$$\mathtt{dict}$$$ structure in $$$\mathtt{python}$$$ .

~~~~~

This problem can be solved by classical DDP (https://en.oi-wiki.org/dp/dynamic/) in $$$O(n \log n)$$$. So we ask for $$$O(n)$$$ solution.

Note $$$f_i=\Sigma_{j=1}^i a_j·...·a_i$$$. We can get $$$f_1=a_1$$$ and $$$f_i=a_i + a_i \cdot f_{i-1}$$$ for $$$2 \le i \le n$$$. And $$$g_i=\Sigma_{j=1}^i f_i$$$.

For query $$$l,r$$$, consider $$$ans=g_r-g_l$$$. We have not done. We still need to substract $$$ans$$$ by $$$ \Sigma_{1 \le j \le l, l+1 \le k \le r} a_j·...·a_k$$$.

Nore $$$P_i=a_1·...·a_i$$$, and $$$IP_i=P_i^{-1}$$$

In fact, $$$ \Sigma_{1 \le j \le l, l+1 \le k \le r} a_j·...·a_k$$$ is equal to $$$(IP_0+IP_1+...+IP_{l-1})·(P_{l+1}+P_{l+2}+...+P_r)$$$

All this formula can be calculated in $$$O(n)$$$.

Complexity: $$$O(n+q)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=998244353;
const ll  INF=2147483647;
int T,n,q;
ll  a[N],dp[N],P[N],SP[N],IP[N],SIP[N];

ll pw(ll x,ll p)
{
	if(!p) return 1;
	ll y=pw(x,p>>1);
	y=(y*y)%TMD;
	if(p&1) y=(y*(x%TMD))%TMD;	
	return y;
}

ll INV(ll x)
{
    return pw(x,TMD-2);
}

void init()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
}

void solve()
{
    dp[1]=a[1];
    for(int i=2;i<=n;i++)
        dp[i]=(dp[i-1]+a[i]+a[i]*(dp[i-1]-dp[i-2]))%TMD;
    P[0]=SP[0]=IP[0]=SIP[0]=1;
    for(int i=1;i<=n;i++)
        P[i]=(P[i-1]*a[i])%TMD;
    IP[n]=INV(P[n]);
    for(int i=n-1;i;i--) IP[i]=IP[i+1]*a[i+1]%TMD;
    for(int i=1;i<=n;i++)
    {
        SP[i]=(SP[i-1]+P[i])%TMD;
        SIP[i]=(SIP[i-1]+IP[i])%TMD;
    }
    for(int i=1;i<=q;i++)
    {
        int l,r;
        ll  ans;
        cin>>l>>r;
        ans=(dp[r]-dp[l-1]+TMD)%TMD;
        if(l>1) ans=(ans-(SP[r]-SP[l-1])*(SIP[l-2])+TMD*TMD)%TMD;
        cout<<ans<<'\n';
    }
}

int main()
{
    fastio;

	cin>>T;
	while(T--)
	{
		init();
		solve();
	}

	return 0;
}

We found that the probability of taking a certain number is only related to its rank. Let $$$P[i][j]$$$ represent the probability that, out of a total of $$$i$$$ numbers, Alice selects the $$$j$$$-th smallest number.

When the coin is on the obverse side, Alice's probability of picking it up is $$$\frac{1}{2} \cdot \frac{j}{1 + \dots + i}$$$. When a coin is reversed, consider two situations:

• The number with rank smaller than $$$j$$$ have been taken. If so Alice's probability of picking it up is $$$\frac{1 + \dots + (j-1)}{1 + \dots + i} P[i-1][j-1]$$$;

• The number with rank greater than $$$j$$$ has been taken. If so Alice's probability of picking it up is $$$\frac{(j+1) + \dots + i}{1 + \dots + i} P[i-1][j]$$$.

So the recurrence relation for $$$P[i][j]$$$ is given by:

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=2010;
const int LOGN=28;
const ll  TMD=998244353;
const ll  INF=2147483647;
int T,n;
int a[N];
ll  P[N][N];

ll pw(ll x,ll p)
{
	if(!p) return 1;
	ll y=pw(x,p>>1);
	y=(y*y)%TMD;
	if(p&1) y=(y*(x%TMD))%TMD;
	return y;
}

ll INV(ll x)
{
    return pw(x,TMD-2);
}

ll SUM(ll x)
{
	return x*(x+1)/2;
}

ll SUM(ll L,ll R)
{
	if(L>R) return 0;
	return SUM(R)-SUM(L-1);
}

void init_P()
{
	P[1][1]=INV(2);
	for(int i=2;i<N;i++)
	{
		for(int j=1;j<=i;j++)
		{
			P[i][j]=INV(2)*j%TMD*INV(SUM(1,i))%TMD;
			P[i][j]=(P[i][j]+INV(2)*SUM(j+1,i)%TMD*INV(SUM(1,i))%TMD*P[i-1][j])%TMD;
			P[i][j]=(P[i][j]+INV(2)*SUM(1,j-1)%TMD*INV(SUM(1,i))%TMD*P[i-1][j-1])%TMD;
		}
	}
}

void init()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
}

void solve()
{
	ll ans=0;
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++) ans=(ans+P[n][i]*a[i])%TMD;
	printf("%I64d\n",ans);
}

int main()
{
	init_P();
	scanf("%d",&T);
	while(T--)
	{
		init();
		solve();
	}
	
	return 0;
}

Note $$$X$$$ as set of $$$a_i$$$.

Note that $$$f(N)$$$ is defined only when $$$N < \text{lcm}(X)$$$.

How do we find $$$f(N)$$$ greedily? In each step, it's sufficient to keep track of the smallest achievable element in that step.

Let's build $$$f$$$ manually, where for every $$$0 \leq i \leq m$$$, $$$f[i] = \min(f[i - i \% y]) + 1$$$ for all $$$y \in X$$$. This is doable in $$$O(m \times |X|)$$$, which is too slow to pass the time limit.

Firstly, let's prove that $$$f$$$ is a non-decreasing function. For all $$$i$$$, it can be shown that $$$f(i) \leq f(i+1)$$$, because for any integer $$$y$$$, $$$(i + 1) - (i + 1) \% y \geq i - i \% y$$$.

It can also be proven that for any $$$i$$$, one of the following is true: $$$f(i) = f(i+1)$$$ or $$$f(i) + 1 = f(i + 1)$$$.

Now, we can use binary search to find the lengths of each value's occurrences. Let the current index be $$$i$$$. We can find the rightmost index (let it be $$$j$$$), for which $$$f(j) = f(i) + 1$$$. In each iteration, we add $$$(j - i) \times f(j)$$$.

This works in $$$O(|X| \times f(m) \times \log(m))$$$ time. This is sufficient because it can be proven that $$$|X| \times f(m) \leq 2 \times m$$$.

Let $$$mx = \max(X)$$$. In each step, we choose $$$mx$$$ if the number is not divisible by $$$mx$$$ ($$$m \to m - m \% mx$$$), otherwise we choose any other element, which decreases $$$m$$$ by at least $$$1$$$. Then, it's clear that for every $$$2$$$ steps, the current value decreases by at least $$$mx$$$, where $$$mx \geq |X|$$$. Thus, $$$|X| \times f(m) \leq mx \times 2 \times (m / mx) \leq 2 \times m$$$.

Overall time complexity is $$$O(|X| \times f(m) \times \log(m))$$$ or $$$O(|X| \times f(m))$$$, depending on the implementation.

Bonus: Try to prove that $$$|X| \times f(m) \leq m + 1$$$, for any given input values.

Conclusion:

• $$$f$$$ is sorted

• $$$f(n)$$$ is defined only when $$$n < \text{lcm}(X)$$$

• $$$f(m) \times |X| = O(m)$$$

• $$$f(i) = f(i-1) + 1$$$ or $$$f(i) = f(i-1)$$$ for any $$$i$$$

For greedy computation of $$$f(m)$$$, we can choose the smallest value achievable from one operation in each step.

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        vector<int> X(n);
        for (auto &i : X)
            cin >> i;
        int ans = 0;
        int cur = 0;
        int i = 0;
        while (i < m)
        {
            int mx = i + 1;
            for (auto &j : X)
                mx = max(mx, (i) / j * j + j - 1);
            mx = min(mx, m);
            cur++;
            ans += cur * (mx - i);
            i = mx;
        }
        cout << ans << '\n';
    }
    return 0;
}

TheForces is a project uniting individuals with a shared interest in competitive programming contests. You can join our discord server with more than $$$2500$$$ members to communicate with founders and members of TheForces.

In the other words TheForces rounds are series of educational contests for beginners to masters which are created by a group of CP lovers in the CF community, It's where anyone can propose and prepare his own interesting problems and receive money!

Not to mention that we've already created two official codeforces Div($$$1 + 2$$$) rounds before ;) So join us now!

Discord link

TheForces website

Let $$$count$$$ be the number of $$$1's$$$ in the given binary string $$$S$$$.

Note that if we perform atleast one operation there will be atleast $$$k$$$ $$$0's$$$. So it is always optimal to get minimum $$$k$$$ $$$0's$$$ once we start doing operations.

Let $$$S$$$ = $$$s_1s_2s_3s_4s_5s_6s_7s_8s_9s_{10}$$$ and $$$k = 3$$$

we can do operations in the following way to get $$$k$$$ $$$0's$$$.

1. Choose $$$i=3$$$, $$$S$$$ = $$$111000s_7s_8s_9s_{10}$$$

2. Choose $$$i=6$$$, $$$S$$$ = $$$111111000s_{10}$$$

3. Choose $$$i=7$$$, $$$S$$$ = $$$1111111000$$$.

By this way we can always get minimum of $$$k$$$ $$$0's$$$ once we start doing operations.

Hence, the answer to the problem is maximum( $$$count$$$ , $$$n-k$$$ ).

Time Complexity : $$$O(n)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        int ans=count(s.begin(),s.end(),'1');
        ans=max(ans,n-k);
        cout<<ans<<"\n";
    }
}

From the above problem, we can know what are the maximum possible $$$1's$$$ in $$$S$$$ we can get for a given $$$k$$$. Now we have to think minimum operations required to get those maximum $$$1's$$$. For given $$$i$$$ let's call $$$S_{i},S_{i-1},S_{i-2},...,S_{i-k+2},S_{i-k+1}$$$ as Left part and $$$S_{i+1},S_{i+2},S_{i+3},...,S_{i+k-1},S_{i+k}$$$ as Right part. It is easy to see that If we wish to do operation then there will be atleast one $$$0$$$ in Left part makes the operation optimal(Because it will decrease the $$$0$$$ count and gradually increase the $$$1$$$ count). So we can come to conclusion that, whenever we have to do the operation, Left part have more number of $$$0's$$$ and $$$S_1 = S_2 = S_3 = ... = S_{i-k} = 1$$$.

Time Complexity : $$$O(n)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        string s;
        cin>>s;
        ll ind1=-1,ind2=-1;
        for(ll i=0;i<n;i++){
            if(s[i]=='0') ind2=i;
        }
        for(ll i=n-1;i>=0;i--){
            if(s[i]=='0') ind1=i;
        }
        ll cnt=count(s.begin(),s.end(),'1');
        for(ll k=1;k<=(n/2);k++){
            if(cnt>=(n-k)) cout<<"0 ";
            else{
                ll l=ind1,r=ind2;
                r-=k;
                cout<<(r-l+k)/k<<" ";
            }
        }
        cout<<"\n";
    }
}

Bob will win the game if all piles contains even number of stones, because Bob can follow the Alice operations. Otherwise Alice wins(i.e., atlest one pile conatins odd number of stones).

So Now our task is to construct a permutation $$$p$$$ where subarrays containing atleast one odd element are maximum possible.

It is easy to see that odd elements at odd position increases the subarray count. So we can construct the permutation $$$1,2,3,...,n$$$.

Time Complexity : $$$O(n)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        for(ll i=0;i<n;i++) cout<<i+1<<" ";
        cout<<"\n";
    }
}

Note that, for winning of Alice we need odd elements so, let $$$v$$$ is the answer for odd $$$i$$$, then for $$$i+1$$$ the answer is $$$2*v$$$, because from odd $$$i$$$ to even $$$i+1$$$ we are taking extra even element so this element shares either end of the array.

Let $$$v$$$ is the answer for even $$$i$$$, then for $$$i+1$$$ the answer is $$$v*\frac{((i/2)+2)*((i/2)+1)}{2}$$$, because of the extra odd element in $$$i+1$$$.

By this way we can calculate our answer.

Time Complexity : $$$O(n)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

ll mod=1e9+7;
const ll N=3e5+11;
vector<ll> v;
 
int main(){
    fast;
    v.resize(N);
    v[1]=1;
    v[2]=2;
    ll val=3,diff=3;
    for(ll i=3;i<N;i+=2){
        v[i]=(v[i-1]*(val%mod))%mod;
        v[i+1]=(v[i]*2)%mod;
        val+=diff;
        diff++;
    }
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        cout<<v[n]<<"\n";
    }
}

If you observe carefully we don't need to care about the characters in the given string.

Let $$$+$$$ be operation 1 and $$$-$$$ be operation 2. Now our task is to count the different strings of length $$$m$$$ $$$+++--++--++--...$$$ such that prefix sum at point $$$i$$$ is maximum( $$$0$$$, sum of first $$$i$$$ elements) and prefix sum at point $$$m$$$ is equal to $$$n$$$.

This can done using dynamic programing.

Time Complexity : $$$O(nm)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
ll mod=1e9+7;
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll m,n;
        cin>>m>>n;
        string s;
        cin>>s;
        if(m>n) cout<<"0\n";
        else{
            vector<ll> dp(n+1);
            dp[0]=1;
            for(ll i=0;i<n;i++){
                vector<ll> ndp(n+1);
                for(ll j=0;j<=i;j++){
                    ndp[j+1]=(ndp[j+1]+dp[j])%mod;
                    if(j>0) ndp[j-1]=(ndp[j-1]+(26*dp[j])%mod)%mod;
                    else ndp[j]=(ndp[j]+dp[j])%mod;
                }
                dp=ndp;
            }
            cout<<dp[m]<<"\n";
        }
    }
}

It is easy to see that, for a given query we need the count of the lowerbound of given $$$x$$$ in $$$l$$$ to $$$r$$$ segment.

This can be done using various data structures, but in Merge sort tree the constant factor is high so it will give TLE if you didn't implement it properly.

Divide the array into $$$B$$$ blocks, each with a length of $$$L= \frac{n}{B}$$$. We use set to maintain the information of each block, so that the query only uses the lower_bond() function. The complexity of the modification is $$$O(\log(n))$$$. The complexity of the query is $$$O(L+B\log(n))$$$. So we choose $$$L=\sqrt{n\log(n)}$$$

Time Complexity : $$$O(n\sqrt{n\log(n)})$$$

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
//#define int long long
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=1000000001;
const int B=3000;//100;
int T,n,q;
int a[N],bnum[N];

struct block
{
    set<pair<int,int> >    S;
    unordered_map<int,int> cnt;
}blk[N];

void init()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n+4;i++)
    {
        blk[i].S.clear();
        blk[i].cnt.clear();
    }
    for(int i=1;i<=n;i++)
    {
        bnum[i]=i/B+1;
        blk[bnum[i]].S.insert(make_pair(a[i],i));
        blk[bnum[i]].cnt[a[i]]++;
    }
}

void solve()
{
    for(int i=1;i<=q;i++)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            int l,r,x,mxl=-INF,cl=0,mnr=INF,cr=0; //l:<x,r:>=x
            cin>>l>>r>>x;
            if(bnum[l]==bnum[r])
            {
                for(int i=l;i<=r;i++)
                {
                    if(a[i]<x)
                    {
                        if(a[i]>mxl) mxl=a[i],cl=1;
                        else if(a[i]==mxl) cl++;
                    }
                    else
                    {
                        if(a[i]<mnr) mnr=a[i],cr=1;
                        else if(a[i]==mnr) cr++;
                    }
                }
            }
            else
            {
                for(int i=l;bnum[i]==bnum[l];i++)
                {
                    if(a[i]<x)
                    {
                        if(a[i]>mxl) mxl=a[i],cl=1;
                        else if(a[i]==mxl) cl++;
                    }
                    else
                    {
                        if(a[i]<mnr) mnr=a[i],cr=1;
                        else if(a[i]==mnr) cr++;
                    }
                }
                for(int i=r;bnum[i]==bnum[r];i--)
                {
                    if(a[i]<x)
                    {
                        if(a[i]>mxl) mxl=a[i],cl=1;
                        else if(a[i]==mxl) cl++;
                    }
                    else
                    {
                        if(a[i]<mnr) mnr=a[i],cr=1;
                        else if(a[i]==mnr) cr++;
                    }
                }
                for(int i=bnum[l]+1;i<=bnum[r]-1;i++)
                {
                    set<pair<int,int> >::iterator it=blk[i].S.lower_bound(make_pair(x,0));
                    if(it!=blk[i].S.end())
                    {
                        if(it->first<mnr) mnr=it->first,cr=blk[i].cnt[it->first];
                        else if(it->first==mnr) cr+=blk[i].cnt[it->first];
                    }
                    if(it==blk[i].S.begin()) continue;
                    it--;
                    if(it->first>mxl) mxl=it->first,cl=blk[i].cnt[it->first];
                    else if(it->first==mxl) cl+=blk[i].cnt[it->first];
                }
            }
            //
            //cout<<"mxl="<<mxl<<" mnr="<<mnr<<'\n';
            //
            if(mxl==-INF) cout<<cr<<'\n';
            else if(mnr==INF) cout<<cl<<'\n';
            else if(x-mxl==mnr-x) cout<<cl+cr<<'\n';
            else if(x-mxl<mnr-x) cout<<cl<<'\n';
            else cout<<cr<<'\n';
        }
        else
        {
            int p,v;
            cin>>p>>v;
            blk[bnum[p]].S.erase(make_pair(a[p],p));
            blk[bnum[p]].cnt[a[p]]--;
            a[p]=v;
            blk[bnum[p]].S.insert(make_pair(a[p],p));
            blk[bnum[p]].cnt[a[p]]++;
        }
    }
}

//-------------------------------------------------------

void gen_data()
{
    srand(time(NULL));
}

int bruteforce()
{
    return 0;
}

//-------------------------------------------------------

signed main()
{
    fastio;

	cin>>T;
	while(T--)
	{
		init();
		solve();

		/*

		//Stress Test

		gen_data();
		auto ans1=solve(),ans2=bruteforce();
		if(ans1==ans2) printf("OK!\n");
		else
		{
			//Output Data
 		}

		*/
	}

	return 0;
}

Lets root the tree at any node, let $$$r$$$ be the root of the tree.

We can solve the problem using $$$DP$$$ in the following way:

$$$dp1[i][j]$$$ = The minimum beauty of the component that contains node $$$i$$$, when the subtree rooted at node $$$i$$$ is divided into exactly $$$j$$$ components, such that the colour of all nodes containing in the component where node $$$i$$$ is included is red.

$$$dp2[i][j]$$$ =The minimum beauty of the component that contains node $$$i$$$, when the subtree rooted at node $$$i$$$ is divided into exactly $$$j$$$ components, where all components except the one containing node $$$i$$$ doesn't satisfy the condition of "Perfect Tree"(i.e., all other components are non-perfect trees).

If there is no value for particular $$$DP$$$ state, then set it into $$$♾️$$$.

The answer to problem is $$$j-1$$$ where $$$dp1[r][j]<♾️$$$ or $$$dp2[r][j] < 0$$$.

Time Complexity : $$$O(n^2)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
ll n;
vector<ll> a;
vector<vector<ll>> adj;

vector<pair<ll,ll>> dfs(ll x, ll p){
    vector<pair<ll,ll>> dp;
    dp.push_back({0,1e18});
    for(auto i:adj[x]){
        if(i!=p){
            vector<pair<ll,ll>> dp1=dfs(i,x);
            ll n1=(ll)dp1.size();
            dp1.push_back({1e18,1e18});
            for(ll j=n1-1;j>=0;j--){
                if(dp1[j].first<1e18 || dp1[j].second<0){
                    dp1[j+1].first=min((ll)0,dp1[j+1].first);
                }
            }
            ll n2=(ll)dp.size()-1;
            vector<pair<ll,ll>> dp2(n1+n2+1,{1e18,1e18});
            for(ll j=0;j<=n2;j++){
                for(ll k=0;k<=n1;k++){
                    dp2[j+k].first=min(dp2[j+k].first,dp[j].first+dp1[k].first);
                    dp2[j+k].second=min(dp2[j+k].second,dp[j].first+dp1[k].second);
                    dp2[j+k].second=min(dp2[j+k].second,dp[j].second+dp1[k].first);
                    dp2[j+k].second=min(dp2[j+k].second,dp[j].second+dp1[k].second);
                }
            }
            dp=dp2;
        }
    }
    ll n2=(ll)dp.size()-1;
    vector<pair<ll,ll>> dp2(n2+1);
    for(ll i=0;i<=n2;i++){
        if(a[x]>0){
            dp2[i].first=dp[i].first+a[x];
            dp2[i].second=dp[i].second+a[x];
        }
        else{
            dp2[i].first=1e18;
            dp2[i].second=min(dp[i].first,dp[i].second)+a[x];
        }
    }
    return dp2;
}
 
int main(){
    fast;
    ll t;
    t=1;
    while(t--){
        cin>>n;
        a.clear();
        a.resize(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        string s;
        cin>>s;
        for(ll i=0;i<n;i++){
            if(s[i]=='1') a[i]=-a[i];
        }
        adj.clear();
        adj.resize(n);
        for(ll i=0;i<n-1;i++){
            ll u,v;
            cin>>u>>v;
            u--;
            v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        vector<pair<ll,ll>> dp=dfs(0,-1);
        for(ll i=0;i<n;i++){
            if(dp[i].first<1e18 || dp[i].second<0){
                cout<<i;
                break;
            }
        }
    }
}

TheForces is a project uniting individuals with a shared interest in competitive programming contests. You can join our discord server with more than $$$2500$$$ members to communicate with founders and members of TheForces.

In the other words TheForces rounds are series of educational contests for beginners to masters which are created by a group of CP lovers in the CF community, It's where anyone can propose and prepare his own interesting problems and receive money!

Not to mention that we've already created two official codeforces Div($$$1 + 2$$$) rounds before ;) So join us now!

Discord link

TheForces website

We can observe that "O" and "K" do not "interlock" with each other. So this problem is just finding two disjoint $$$4 \times 3$$$ sub-grids. Using brute force is enough.

Bonus: solve the problem when $$$n,m \le 10^3$$$.

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, m; cin >> n >> m;
    int ans = 0;
    for (int i = 0; i < n-3; i++) {
        for (int j = 0; j < m-2; j++) {
            for (int i2 = 0; i2 < n-3; i2++) {
                for (int j2 = 0; j2 < m-2; j2++) {
                    if (min(i, i2) + 3 < max(i, i2) || min(j, j2) + 2 < max(j, j2)) {
                        ans++;
                    }
                }
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.in", "r", stdin)
    //freopen("file.out", "w", stdout);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Note $$$k$$$ is the maximum integer such that $$$2^k \le n$$$. We can proof $$$a+b \le 2^(k+1)-1$$$.

Proof:since $$$a$$$ & $$$b=0$$$, there is no carry bit in $$$a+b$$$. And we can pick $$$a=2^{k}-1$$$ and $$$b=2^{k}$$$ to make $$$a+b=2^(k+1)-1$$$.

When $$$a+b=2^(k+1)-1$$$, we can see picking $$$a=2^{k}-1$$$ and $$$b=2^{k}$$$ makes $$$a \cdot b$$$ maximum. So the answer is $$$2^{k} \cdot (2^{k}-1)$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        ll val=0;
        for(ll i=0;i<31;i++){
            if((n&(1LL<<i))>0) val=i;
        }
        cout<<(1LL<<val)*((1LL<<val)-1)<<"\n";
    }
}

Note $$$k$$$ is the maximum integer such that $$$2^k \le n$$$. At first, we can easily see a lower bound of the answer — $$$2^{k-1}$$$. To reach this lower bound, we just pick $$$a=2^{k-1}$$$ and $$$b=2^k$$$.

Next, we only consider $$$a∈[2^{k-1}+1,2^{k}-1]$$$ and $$$b∈[2^k+1,2^k+2^{k-1}-1]$$$ which make $$$\gcd(a,b)>2^{k-1}$$$ possible.

We can see the following conclusions.

Conclution 1: $$$\gcd(a,b)=a$$$.

Proof 1: if $$$\gcd(a,b)<a$$$, it means $$$\gcd(a,b)\le a/2 <2^{k-1}$$$, which is too small.

Conclution 2: $$$b=2a$$$.

Proof 2: if $$$b=ka(k>2)$$$, it means $$$b>2^k+2^{k-1}$$$, which is too large.

Now, we need to find the maximum $$$a$$$ that satisfies $$$a$$$ & $$$2a=0$$$. This only holds when there are no two consecutive $$$1$$$'s in the binary representation of $$$a$$$. So, the answer is a number — the largest, not exceeding $$$n$$$, where there are no two consecutive $$$1$$$'s in binary representation.

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()

using namespace std;
using ll = long long;

const int _N = 1e5 + 5;

void solve() {
	ll n; cin >> n;
	ll x = 0;
	int lst = 0;
	for (ll bit = 29; bit >= 0; bit--) {
		if (x + (1 << bit) <= n && lst == 0) {
			lst = 1;
			x |= (1 << bit);
		} else lst = 0;
	}
	cout << x / 2 << '\n';
}

int main() {
	int T; cin >> T;
	while (T--) {
		solve();
	}
}

First, since $$$(a+b)^2 = a^2 + b^2 + 2ab > a^2+b^2$$$, it's obvious that sum up the numbers first will give a better answer.

Also if there's only one tuple left having positive value, choosing operation $$$1$$$ will give a better answer.

Therefore we will first sum up $$$max(a_i,b_i)$$$ for all tuples, then check $$$min(a_i,b_i)$$$ for all tuples for being the one to perform operation $$$1$$$ to, and find the best answer.

The time complexity will be $$$O(n\ log\ n)$$$ or $$$O(n)$$$ depends on your implementation.

#include<bits/stdc++.h>
#define pi 3.14159265358979323846
#define eb emplace_back
#define ll long long
#define w(t) while(t--)
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define iofast ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
//give sin(),cos() radian, and asin(),acos() gives you radian
struct aaa{
	ll a,b;
}arr[200010];
void solve(){
	int n;
	ll ans=0,sum=0,maxn=0;
	cin>>n;
	for(int i=0;i<n;i++) cin>>arr[i].a>>arr[i].b;
	for(int i=0;i<n;i++){
		sum+=max(arr[i].a,arr[i].b);
		ans+=min(arr[i].a,arr[i].b)*min(arr[i].a,arr[i].b);
		maxn=max(maxn,min(arr[i].a,arr[i].b));
	}
	sum+=maxn;
	ans-=(maxn*maxn);
	ans+=sum*sum;
	cout<<ans<<'\n';
	return;
}
int main(){
	iofast
	int t;
	cin>>t;
	w(t) solve();
	return 0;
}

Note $$$mx=max(a_1,a_2,\ldots,a_n)$$$ and $$$mn=min(a_1,a_2,\ldots,a_n)$$$.

Case $$$1$$$: $$$mx-mn>1$$$, the answer is $$$0$$$.

Case $$$2$$$: $$$mx=mn$$$

• if $$$mx=n-1$$$, the answer is $$$3$$$ when $$$n=2$$$ and $$$1$$$ otherwise;

• otherwise, we can see all numbers are not unique. This problem is equivalent to: there are $$$n$$$ balls and $$$mx$$$ boxes, and the balls and boxes are the same. Find the number of solutions where each box has at least two balls. This is a variation of a classic problem, and the answer is $$$C(n-mx-1,mx-1)$$$(don't forge to check $$$n \ge 2mx$$$).

Case $$$3$$$: $$$mx=mn+1$$$

For $$$a_i=mn$$$, we can see $$$b_i$$$ are unique and for $$$a_i=mx$$$, $$$b_i$$$ are not unique. We first assign unique numbers, and then the problem is transformed into Case $$$2$$$.

The time complexity is $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
ll mod=998244353;
 
long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}
 
long long modular_inverse(long long n){
  return power(n,mod-2);
}
 
#define MAXN 2000005
 
long long factorial[MAXN];
long long invfact[MAXN];
 
void cfact(){
  long long i;
  factorial[0]=1;
  factorial[1]=1;
  for(i=2;i<MAXN;i++){
    factorial[i]=factorial[i-1]*i;
    factorial[i]%=mod;
  }
  invfact[MAXN-1]=modular_inverse(factorial[MAXN-1]);
  for(i=MAXN-2;i>=0;i--){
    invfact[i]=invfact[i+1]*(i+1);
    invfact[i]%=mod;
  }
}
 
long long calcnCr(long long n,long long k){
  if(k<0 || n<k){return 0;}
  return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod;
}
 
int main(){
    fast;
    cfact();
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vector<ll> a(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        ll maxi=*max_element(a.begin(),a.end());
        ll mini=*min_element(a.begin(),a.end());
        ll res=0;
        if(maxi==mini){
            if(maxi==(n-1)){
                res=1;
                if(n==2) res=3;
            }
            else if(maxi<=(n/2)){
                ll m=(a[0]);
                res=calcnCr(n,m);
                res=(res*calcnCr(n-m-1,m-1))%mod;
            }
        }
        else if(maxi==(mini+1)){
            ll cntmax=count(a.begin(),a.end(),maxi);
            ll cntmin=count(a.begin(),a.end(),mini);
            if(maxi>cntmin && maxi<=cntmin+(cntmax/2)){
                ll m=maxi,m1=mini;
                m1=count(a.begin(),a.end(),m1);
                res=calcnCr(n,m);
                res=(res*calcnCr(m,m1))%mod;
                res=(res*calcnCr(n-m-1,m-m1-1))%mod;
            }
        }
        cout<<res<<"\n";
    }
}

Consider we already get the answer for $$$[i,r](1 \le i \le r)$$$, we can use it to get the answer for $$$[i,r+1](1 \le i \le r+1)$$$.

Note $$$pre_i$$$ is the max index such that $$$pre_i<i$$$ and $$$a_{pre_i}=a_i$$$. At first, $$$answer[r+1,r+1]=0$$$. For $$$answer[i,r+1](1 \le i \le r)$$$, there are two cases:

• $$$answer[i,r+1]=answer[i,r]$$$. We won't make any changes;

• $$$answer[i,r+1]=a_{i+1}$$$. It is only possible for $$$1 \le i \le pre_i$$$. We can use a lazy tag segment tree to maintain the answer.

The time complexity will be $$$O(n\ log\ n)$$$ or $$$O(n\ log^2\ n)$$$ depends on your implementation.

// Author: sendyuripics
// Created: 2024.09.13 21:28:43
// Url: https://codeforces.me/gym/547746/problem/F

#include<bits/stdc++.h>
#define int long long
using namespace std;
void ts(){cout<<"IAKIOI\n";}
inline int read(){
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
//max once, max twice
int N;
int a[200005];
int o[200005];
int lst[200005];
using ll = long long;
const int MAXN = 200001;
const ll llINF=(1ll<<60);  // 1-based
ll A[MAXN];

struct Node {
	ll sum;   // Sum tag
	ll max1;  // Max value
	ll max2;  // Second Max value
	ll maxc;  // Max value count
	ll min1;  // Min value
	ll min2;  // Second Min value
	ll minc;  // Min value count
	ll lazy;  // Lazy tag
} T[MAXN * 4];

void merge(int t) {
	// sum
	T[t].sum = T[t << 1].sum + T[t << 1 | 1].sum;

	// max
	if (T[t << 1].max1 == T[t << 1 | 1].max1) {
		T[t].max1 = T[t << 1].max1;
		T[t].max2 = max(T[t << 1].max2, T[t << 1 | 1].max2);
		T[t].maxc = T[t << 1].maxc + T[t << 1 | 1].maxc;
	} else {
		if (T[t << 1].max1 > T[t << 1 | 1].max1) {
			T[t].max1 = T[t << 1].max1;
			T[t].max2 = max(T[t << 1].max2, T[t << 1 | 1].max1);
			T[t].maxc = T[t << 1].maxc;
		} else {
			T[t].max1 = T[t << 1 | 1].max1;
			T[t].max2 = max(T[t << 1].max1, T[t << 1 | 1].max2);
			T[t].maxc = T[t << 1 | 1].maxc;
		}
	}

	// min
	if (T[t << 1].min1 == T[t << 1 | 1].min1) {
		T[t].min1 = T[t << 1].min1;
		T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min2);
		T[t].minc = T[t << 1].minc + T[t << 1 | 1].minc;
	} else {
		if (T[t << 1].min1 < T[t << 1 | 1].min1) {
			T[t].min1 = T[t << 1].min1;
			T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min1);
			T[t].minc = T[t << 1].minc;
		} else {
			T[t].min1 = T[t << 1 | 1].min1;
			T[t].min2 = min(T[t << 1].min1, T[t << 1 | 1].min2);
			T[t].minc = T[t << 1 | 1].minc;
		}
	}
}

void push_add(int t, int tl, int tr, ll v) {
	if (v == 0) { return; }
	T[t].sum += (tr - tl + 1) * v;
	T[t].max1 += v;
	if (T[t].max2 != -llINF) { T[t].max2 += v; }
	T[t].min1 += v;
	if (T[t].min2 != llINF) { T[t].min2 += v; }
	T[t].lazy += v;
}

// corresponds to a chmin update
void push_max(int t, ll v, bool l) {
	if (v >= T[t].max1) { return; }
	T[t].sum -= T[t].max1 * T[t].maxc;
	T[t].max1 = v;
	T[t].sum += T[t].max1 * T[t].maxc;
	if (l) {
		T[t].min1 = T[t].max1;
	} else {
		if (v <= T[t].min1) {
			T[t].min1 = v;
		} else if (v < T[t].min2) {
			T[t].min2 = v;
		}
	}
}

// corresponds to a chmax update
void push_min(int t, ll v, bool l) {
	if (v <= T[t].min1) { return; }
	T[t].sum -= T[t].min1 * T[t].minc;
	T[t].min1 = v;
	T[t].sum += T[t].min1 * T[t].minc;
	if (l) {
		T[t].max1 = T[t].min1;
	} else {
		if (v >= T[t].max1) {
			T[t].max1 = v;
		} else if (v > T[t].max2) {
			T[t].max2 = v;
		}
	}
}

void pushdown(int t, int tl, int tr) {
	if (tl == tr) return;
	// sum
	int tm = (tl + tr) >> 1;
	push_add(t << 1, tl, tm, T[t].lazy);
	push_add(t << 1 | 1, tm + 1, tr, T[t].lazy);
	T[t].lazy = 0;

	// max
	push_max(t << 1, T[t].max1, tl == tm);
	push_max(t << 1 | 1, T[t].max1, tm + 1 == tr);

	// min
	push_min(t << 1, T[t].min1, tl == tm);
	push_min(t << 1 | 1, T[t].min1, tm + 1 == tr);
}

void build(int t = 1, int tl = 0, int tr = N - 1) {
	T[t].lazy = 0;
	if (tl == tr) {
		T[t].sum = T[t].max1 = T[t].min1 = A[tl];
		T[t].maxc = T[t].minc = 1;
		T[t].max2 = -llINF;
		T[t].min2 = llINF;
		return;
	}

	int tm = (tl + tr) >> 1;
	build(t << 1, tl, tm);
	build(t << 1 | 1, tm + 1, tr);
	merge(t);
}

void update_add(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l) { return; }
	if (l <= tl && tr <= r) {
		push_add(t, tl, tr, v);
		return;
	}
	pushdown(t, tl, tr);

	int tm = (tl + tr) >> 1;
	update_add(l, r, v, t << 1, tl, tm);
	update_add(l, r, v, t << 1 | 1, tm + 1, tr);
	merge(t);
}

void update_chmin(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l || v >= T[t].max1) { return; }
	if (l <= tl && tr <= r && v > T[t].max2) {
		push_max(t, v, tl == tr);
		return;
	}
	pushdown(t, tl, tr);

	int tm = (tl + tr) >> 1;
	update_chmin(l, r, v, t << 1, tl, tm);
	update_chmin(l, r, v, t << 1 | 1, tm + 1, tr);
	merge(t);
}

void update_chmax(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l || v <= T[t].min1) { return; }
	if (l <= tl && tr <= r && v < T[t].min2) {
		push_min(t, v, tl == tr);
		return;
	}
	pushdown(t, tl, tr);

	int tm = (tl + tr) >> 1;
	update_chmax(l, r, v, t << 1, tl, tm);
	update_chmax(l, r, v, t << 1 | 1, tm + 1, tr);
	merge(t);
}

ll query_sum(int l, int r, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l) { return 0; }
	if (l <= tl && tr <= r) { return T[t].sum; }
	pushdown(t, tl, tr);

	int tm = (tl + tr) >> 1;
	return query_sum(l, r, t << 1, tl, tm) + query_sum(l, r, t << 1 | 1, tm + 1, tr);
}
void solve(){
	N=read();
	map<int,int> mp;
	for(int i=0;i<N;i++){
		a[i]=read();
		lst[i]=(mp.count(a[i])?mp[a[i]]:-1ll);
		mp[a[i]]=i;
		o[i]=0;
	}
	build();
	int res=0;
	for(int i=0;i<N;i++){
		if(lst[i]!=-1)update_chmax(0,lst[i],a[i]);
		res+=query_sum(0,N-1);
	}
	cout<<res<<"\n";
}
signed main(){
	int t=read();
	while(t--)solve();
	return 0;
}
//look at my code
//my code is amazing

Use a variant of the Euler tour. Let's call it BFS-children-first-DFS.

First, node $$$1$$$ is added to the sequence, then $$$DFS(1)$$$ is performed. When $$$DFS(x)$$$ is called, all child nodes of $$$x$$$ are added to the sequence, and then $$$DFS(son[x][i])$$$ is performed.

For example, for the tree shown above, the BFS-children-first-DFS order is $$$[1,2,11,3,4,5,6,7,8,10,9]$$$.

In this way, the subtree rooted at node $$$x$$$ (excluding $$$x$$$ itself) and all the child nodes of node $$$x$$$ are within a contiguous segment of the sequence. This makes it easy to maintain the operations in $$$O(n log n)$$$.

#include <bits/stdc++.h>
#define GO cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
typedef long long ll;
using namespace std;
const int N = 3e5 + 50;
vector<int> adj[N];
ll T[N * 4], lazy[N * 4];
int ind[N], in[N], out[N], out2[N];
int Time = 1;
int n;

void push(int x, int l, int r){
    if(!lazy[x]) return;
    T[x] += lazy[x];
    if(l < r){
        lazy[x * 2] += lazy[x];
        lazy[x * 2 + 1] += lazy[x];
    }
    lazy[x] = 0;
}

void update(int i, int j, int val, int x = 1, int l = 1, int r = n){
    push(x, l, r);
    if(r < i || l > j) return;
    if(l >= i && r <= j){
        lazy[x] = val;
        push(x, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(i, j, val, x * 2, l, mid);
    update(i, j, val, x * 2 + 1, mid + 1, r);
    T[x] = max(T[x * 2], T[x * 2 + 1]);
}

ll query(int i, int j, int x = 1, int l = 1, int r = n){
    push(x, l, r);
    if(r < i || l > j) return -1e18;
    if(l >= i && r <= j) return T[x];
    int mid = (l + r) / 2;
    ll q1 = query(i, j, x * 2, l, mid);
    ll q2 = query(i, j, x * 2 + 1, mid + 1, r);
    return max(q1, q2);
}

void DFS(int u = 1, int p = 1){
    bool f = 0;
    for(int v : adj[u]){
        if(v == p) continue;
        ++Time;
        if(!f) in[u] = Time;
        out[u] = Time;
        ind[v] = Time;
        f = 1;
    }
    for(int v : adj[u]){
        if(v == p) continue;
        DFS(v, u);
    }
    out2[u] = Time;
}

int main()
{
    GO
    int q;
    cin >> n >>q;
    ind[1] = 1;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    DFS();
   // cin >> q;
    while(q--){
        int t;
        cin >> t;
        //
       // cout<<"t="<<t<<'\n';
        //
        if(t == 1){ //Add v to all nodes in the subtree rooted at node x
            int u, x;
            cin >> u >> x;
            update(ind[u], ind[u], x);
            if(in[u])
            update(in[u], out2[u], x);
        }
        else if(t == 2){ //Add v to all children of node x.if it has children
            int u, x;
            cin >> u >> x;
            if(in[u])
            update(in[u], out[u], x);
        }
        else if(t == 3){ //Query the maximum value in the subtree rooted at node x.
            int u;
            cin >> u;
            ll ans = query(ind[u], ind[u]);
            if(in[u]) ans = max(ans, query(in[u], out2[u]));
            cout << ans << '\n';
        }
        else{ //Query the maximum value among all children of node x if there's children otherwise print 0
            int u;
            cin >> u;
            ll ans = -1e18;
            if(in[u]) ans = max(ans, query(in[u], out[u]));
            cout << ans << '\n';
        }
    }
    return 0;
}

TheForces is a project uniting individuals with a shared interest in competitive programming contests. You can join our discord server with more than $$$2200$$$ members to communicate with founders and members of TheForces.

In the other words TheForces rounds are series of educational contests for beginners to masters which are created by a group of CP lovers in the CF community, It's where anyone can propose and prepare his own interesting problems and receive money!

Not to mention that we've already created two official codeforces div(1 + 2) rounds before ;) so join us now!

Discord link

TheForces website

If $$$n=1$$$, There is only one possible $$$\it{Lucky \ array}$$$. It is guaranteed that the given array is $$$\it{Lucky \ array}$$$ so there is no other $$$\it{Lucky \ array}$$$ to output. Hence the answer is $$$-1$$$.

For $$$n>1$$$, it is easy to see that there are more than one possible $$$\it{Lucky \ array}$$$. So we can use the following pattern to construct the $$$\it{Lucky \ array}$$$ :

$$$ 0 \ 1 \ 0 \ 1 \ 0 \ 1 \ ....$$$

If this constructed array is equal to the given array then we can swap the elements in $$$2^{nd}$$$ and $$$3^{rd}$$$ positions if $$$n>2$$$, otherwise we can just set the $$$2^{nd}$$$ to $$$0$$$.

Note that there are many possible constructions, the above mentioned is one of them

Time Complexity : $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int> a(n);
        for(int i=0;i<n;i++) cin>>a[i];
        if(n==1) cout<<"-1\n";
        else if(n==2){
            if(a[1]==1) cout<<"0 0\n";
            else cout<<"0 1\n";
        }
        else{
            vector<int> b(n,0);
            for(int i=1;i<n;i+=2) b[i]=1;
            if(a==b) swap(b[1],b[2]);
            for(auto i:b) cout<<i<<" ";
            cout<<"\n";
        }
    }
}

Let's call array $$$c$$$ good if it contains non-positive integers. Now our task is to make array $$$c$$$ good using minimum number of given operations.

It is always optimal to choose the largest element in $$$c$$$ and decrease it by $$$a$$$ and decrease all other elements by $$$b$$$ until array $$$c$$$ becomes good. But this solution is very slow. We can optimise the solution by using the fact that if we can make the array good using $$$x$$$ operations then we can definitely make the array good using $$$x+1$$$ operations because if all elements in the array are non-positive then using extra operation will not make any element positive. So we can use binary search on our answer.

Binary search follows for fixed $$$m$$$ like decrease all elements by $$$bm$$$ and decrease the remaining positive elements by $$$(a-b)$$$ until it becomes non-positive, call these as extra operations, if the extra operations are not greater than $$$m$$$ decrease the upper bound of the answer, otherwise increase the lower bound of the answer.

Time Complexity : $$$O(nlog(\frac{M}{b}))$$$. where $$$M$$$ is the maximum element in the array $$$c$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n,a,b;
        cin>>n>>a>>b;
        vector<ll> v(n);
        for(ll i=0;i<n;i++) cin>>v[i];
        ll l=0,r=1e9,ans=1e9;
        while(l<=r){
            ll m=(l+r)/2;
            ll ops=0;
            for(ll i=0;i<n;i++){
                if(v[i]>b*m){
                    ops+=((v[i]-b*m+(a-b-1))/(a-b));
                }
            }
            if(ops<=m){
                ans=m;
                r=m-1;
            }
            else l=m+1;
        }
        cout<<ans<<"\n";
    }
}

We can observe that for an index $$$i$$$, if $$$1,2,\ldots,max(h_1,h_2,\ldots,h_i)$$$ all appears in $$$h_1,h_2,\ldots,h_i$$$, the game will end after choose $$$x∈[1,max(h_1,h_2,\ldots,h_i)]$$$.

We can greedily consider the smallest index $$$i+1$$$ such that $$$1,2,\ldots,max(h_1,h_2,\ldots,h_i)$$$ all appears in $$$h_1,h_2,\ldots,h_i$$$, and $$$h_{i+1}>1+max(h_1,h_2,\ldots,h_i)$$$.

We want to decrease $$$h_i$$$ with as many operations as possible, so we pick $$$x=1+max(h_1,h_2,\ldots,h_i)$$$(the minimum we can pick to let the game not end) until $$$h_{i+1}\le 1+max(h_1,h_2,\ldots,h_i)$$$.

A corner case is $$$h_{i+1}=k \cdot (1+max(h_1,h_2,\ldots,h_i))(k>1)$$$, when $$$h_{i+1}=2 \cdot (1+max(h_1,h_2,\ldots,h_i))$$$ we can pick $$$x=(2+max(h_1,h_2,\ldots,h_i))$$$ to make $$$h_{i+1}<1+max(h_1,h_2,\ldots,h_i)$$$, such that $$$max(h_1,h_2,\ldots,h_{i+1})=max(h_1,h_2,\ldots,h_i)$$$.

Run the greedy process in sequence.

Time Complexity : $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vector<ll> a(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        ll ans=0,val=1;
        for(ll i=0;i<n;i++){
            ll res=(a[i]-1)/val;
            if(res>0){
                ans+=res;
                a[i]=1;
            }
            if(val==a[i]) val++;
        }
        ans++;
        cout<<ans<<"\n";
    }
}

An important observation is that the answer always takes the following form：

$$$sig_1 \cdot 1+sig_2 \cdot 2+\ldots+sig_n \cdot n$$$, where $$$sig_i=1$$$ or $$$-1$$$ and $$$-n<\Sigma_{i=1}^{n} sig_i<n$$$

We will provide the construction method later. Firstly, we need to find $$$sig_1,sig_2,\ldots,sig_n$$$ such that $$$sig_1 \cdot 1+sig_2 \cdot 2+\ldots+sig_n \cdot n=m$$$. We can see for $$$-\frac{n(n+1)}{2}+1<m<\frac{n(n+1)}{2}-1$$$ it is always possible. The construction is to find the minimum $$$i$$$ such that $$$1+2+\dots+i-(i+1)-(i+2)-\ldots-n \ge m$$$, then set $$$sig_1,sig_2,\ldots,sig_i$$$ to $$$1$$$ and set $$$sig_{i+1},sig_{i+2},\ldots,sig_n$$$ to $$$-1$$$. After that, if $$$delta=m-(1+2+\dots+i-(i+1)-(i+2)-\ldots-n)>0$$$, set $$$sig_{delta}$$$ to $$$-1$$$.

Now we have decided on the symbol for each number. Let's say we have some numbers $$$posi_1,posi_2,\ldots,posi_x$$$ and $$$nega_1,nega_2,\ldots,nega_y(x+y=n)$$$. The construction for $$$S={m}$$$ is to make $$$A=posi_1-nega_2-nega_3-\ldots-nega_y$$$ and $$$B=nega_1-posi_2-posi_3-\ldots-posi_x$$$, then do $$$A-B$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T;
ll  n,m;
int tag[N];

int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
		scanf("%I64d%I64d",&n,&m);
		ll mx=n*(n+1)/2-2,mn=-mx,sum=mn,cur1,cur2;
		vector<ll> v[2];
		if(m<mn||m>mx||((mx&1)^(m&1)))
		{
			printf("NO\n");
			continue;
		}
		printf("YES\n");
		tag[1]=1;
		for(int i=2;i<=n;i++) tag[i]=0;
		for(int i=2;i<=n;i++)
		{
			tag[i]=1;
			sum+=2*i;
			if(sum>=m)
			{
				tag[(sum-m)/2]=0;
				break;
			}
		}
		for(int i=1;i<=n;i++) v[tag[i]].push_back(i);
		cur1=v[1][0];
		for(int i=1;i<v[0].size();i++) 
		{
			printf("%I64d %I64d\n",cur1,v[0][i]);
			cur1-=v[0][i];
		}
		cur2=v[0][0];
		for(int i=1;i<v[1].size();i++) 
		{
			printf("%I64d %I64d\n",cur2,v[1][i]);
			cur2-=v[1][i];
		}
		printf("%I64d %I64d\n",cur1,cur2);
	}
	
	//fclose(stdin);
	return 0;
}

We can see the maximum of $$$f(p,q)$$$ is $$$2\cdot(n+(n-1)+\ldots+\frac{n}{2}+1)-2\cdot(\frac{n}{2}+\ldots+2+1)$$$.

let $$$x=\frac{n}{2}$$$, To maximize the value of $$$f(p,q)$$$ we have to set the permutation $$$q$$$ such that $$$p_{q_{i}}<=x$$$ for odd values of $$$i$$$ and $$$p_{q_{i}}>x$$$ for even values of $$$i$$$.

So now our task is simplified as find whether each element is $$$<=x$$$ or $$$>x$$$.

For that we have to do some observations on a permutation that there will be a index $$$i$$$ such median($$$i+1,i+2,...,i+\frac{n}{2}$$$)$$$<=x$$$ and median($$$i+2,i+3,...,i+\frac{n}{2}+1$$$)$$$>x$$$ and vice-versa. we can find this by binary search using $$$log(x)$$$ queries. Now $$$p_{i+1}<=x$$$ and $$$p_{i+\frac{n}{2}+1}>x$$$ and vice-versa.

Later we can check other elements using this $$$2$$$ elements.

For every element with index $$$j=i+2,i+3,....,i+\frac{n}{2}$$$ we can check by asking following type of query

$$$? \ 1 \ 2 \ .... \ i \ j \ (i+\frac{n}{2}+2) \ (i+\frac{n}{2}+3) n$$$

For every remaining indices $$$j$$$ we can check by asking following type of query

$$$? \ j \ (i+2) \ (i+3) \ .....\ (i+\frac{n}{2})$$$

So total queries used are $$$n+log(x)$$$ which are less than $$$n+30$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int n;
 
int query(vector<int> v){
    cout<<"? ";
    for(int i=0;i<(int)v.size();i++) cout<<v[i]+1<<" ";
    cout<<endl;
    int x;
    cin>>x;
    if(x>(n/2)) return 1;
    return 0;
}
 
int sol(int j){
    vector<int> v(n/2);
    for(int i=0;i<n/2;i++) v[i]=i+j;
    return query(v);
}
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        cin>>n;
        int l=0,r=n/2;
        int vl=sol(0),vr=sol(n/2);
        while(l+1<r){
            int m=(l+r)/2;
            int vm=sol(m);
            if(vm==vl) l=m;
            else r=m;
        }
        vector<int> v2,v3;
        for(int i=r;i<(r+(n/2)-1);i++){
            v2.push_back(i);
            v3.push_back((i+(n/2))%n);
        }
        vector<int> ans(n);
        ans[l]=vl;
        ans[l+(n/2)]=vr;
        for(int i=0;i<(int)v2.size();i++){
            vector<int> v=v3;
            v.push_back(v2[i]);
            ans[v2[i]]=query(v);
        }
        for(int i=0;i<(int)v3.size();i++){
            vector<int> v=v2;
            v.push_back(v3[i]);
            ans[v3[i]]=query(v);
        }
        vector<int> even,odd;
        for(int i=0;i<n;i++){
            if(ans[i]==0) even.push_back(i+1);
            else odd.push_back(i+1);
        }
        cout<<"! ";
        for(int i=0;i<(int)even.size();i++){
            cout<<even[i]<<" ";
            cout<<odd[i]<<" ";
        }
        cout<<endl;
    }
}

coming soon...

coming soon...

TheForces is a project uniting individuals with a shared interest in competitive programming contests. You can join our discord server with more than $$$2200$$$ members to communicate with founders and members of TheForces.

In the other words TheForces rounds are series of educational contests for beginners to masters which are created by a group of CP lovers in the CF community, It's where anyone can propose and prepare his own interesting problems and receive money!

Not to mention that we've already created two official codeforces div(1 + 2) rounds before ;) so join us now!

Discord link

TheForces website

If the array contains more than $$$2$$$ elements then it is definitely possible to do given operation because array will definitely contain atleast $$$2$$$ $$$even$$$ numbers or atleast $$$2$$$ $$$odd$$$ numbers, in both cases sum of the numbers is $$$even(even+even =even, odd+odd=even)$$$.

Hence, we can do the given operation until array size becomes lesser than or equal to $$$2$$$.

If the array size is $$$2$$$, we can do operation only if both elements parity is equal. If the array size is $$$1$$$, we can’t do any operation.

The below proof mentioned for an array of atleast size $$$2$$$.

The minimum size of the array we obtain is determined by the number of $$$odd$$$ elements in the array, if number of $$$odd$$$ elements is $$$odd$$$ then the minimum size of the array is 2 because $$$(odd+odd+…+odd).._{odd times} \rightarrow (even+odd = odd)$$$, so array must contain an $$$odd$$$ element every time. So now we can determine our answer as $$$maximum(n-k,1+(cntodd \% 2))$$$, where $$$cntodd$$$ is the number of $$$odd$$$ elements in the array.

Time complexity : $$$O(n)$$$.

Note that you can also do simulation brutly, where time complexity : $$$O(Σ n^2)$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        int cnt=0;
        for(int i=0;i<n;i++){
            int x;
            cin>>x;
            if(x%2==1) cnt++;
        }
        int val=1;
        if(cnt%2) val=min(n,2);
        cout<<max(n-k,val)<<"\n";
    }
}

The $$$Maximum MEX$$$ possible in the given sub-array is $$$MEX$$$ of the whole array, because $$$MEX$$$ may increase only by adding extra elements. Hence first calculate the $$$MEX$$$ of the given array and we will use the $$$\underline{two \ pointer \ technique}$$$ to get the $$$\bf{minimum}$$$ size of the subsegment whose $$$MEX$$$ is equal to $$$maximum MEX$$$.

Time Complexity : $$$O(nlogn)$$$, if you use maps or sets to find $$$MEX$$$.

Time Complexity : $$$O(n)$$$, if you use vectors to find to find $$$MEX$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vector<ll> a(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        vector<ll> b(n+1,0);
        for(ll i=0;i<n;i++){
            if(a[i]<=n) b[a[i]]++;
        }
        ll mex=0;
        for(ll i=0;i<=n;i++){
            if(b[i]==0){
                mex=i;
                break;
            }
        }
        ll ans=n,l=0;
        vector<ll> v(mex,0);
        ll cnt=0;
        for(ll i=0;i<n;i++){
            if(a[i]<mex){
                if(v[a[i]]==0) cnt++;
                v[a[i]]++;
            }
            while(l<=i && cnt==mex){
                ans=min(ans,(i-l+1));
                if(a[l]<mex){
                    if(v[a[l]]==1) cnt--;
                    v[a[l]]--;
                }
                l++;
            }
        }
        cout<<ans<<"\n";
    }
}

Given operation is nothing but you can $$$rearrange$$$ your array as you wish.

So now the problem is re-arrange the array to decrease the value of $$$f(b)$$$.

Let the $$$maxi$$$ be the maximum element in $$$a$$$ and $$$mini$$$ be the minimum element in $$$a$$$. It is easy to see that both $$$maxi$$$ and $$$mini$$$ will be in $$$S_1(b)$$$ or $$$S_2(b)$$$, or $$$maxi$$$ in $$$S_1(b)$$$ and $$$mini$$$ in $$$S_2(b)$$$ and vice-versa.

Let’s consider about $$$f(b)$$$, what is happening here actually?

To minimize the value of $$$f(b)$$$, we have to minimize $$$R(S_1(b))*R(S_2(b))$$$(obviously from the definition), i.e., atleast we have to minimize one of the $$$R(S_1(b))$$$ or $$$R(S_2(b))$$$.

Let’s sort the array and traverse through the array to find the minimum value of $$$f(b)$$$.

For a given element what is the maximum element that decreases the range . yes, for a given $$$a_{i}(1 \le i \le \frac{n}{2})$$$ taking $$$(a_i,a_{i+1},….,a_{i+\frac{n}{2}-1})$$$ in either $$$S_1$$$ or $$$S_2$$$ and the remaining elements in other set will decreases the $$$f(b)$$$. hence for every $$$i(1 \le i \le \frac{n}{2})$$$ find the maximum element which decreases the $$$f(b)$$$. Choose anything which gives minimum $$$f(b)$$$ and construct the resultant array accordingly.

See the implementation below for better clarity.

Time complexity : $$$O(nlogn)$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vector<ll> a(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        if(n==2) cout<<a[0]<<" "<<a[1]<<"\n";
        else{
            sort(a.begin(),a.end());
            ll val1=(a[n-1]-a[0]),ind=0,ans=(a[(n/2)-1]-a[0])*(a[n-1]-a[(n/2)]);
            for(ll i=1;i<(n/2);i++){
                ll res=val1*(a[(n/2)+i-1]-a[i]);
                if(res<ans){
                    ans=res;
                    ind=i;
                }
            }
            vector<ll> b(n);
            ll i1=0;
            for(ll i=ind;i<ind+(n/2);i++){
                b[i1]=a[i];
                i1+=2;
            }
            i1=1;
            for(ll i=0;i<ind;i++){
                b[i1]=a[i];
                i1+=2;
            }
            for(ll i=ind+(n/2);i<n;i++){
                b[i1]=a[i];
                i1+=2;
            }
            for(auto i:b) cout<<i<<" ";
            cout<<"\n";
        }
    }
}

Let’s try to solve the problem for single $$$m$$$.

The given $$$XOR$$$ operation is nothing but flipping characters, so rephrase the statement that, flip $$$m$$$ characters in $$$S$$$ to get maximum number of substrings which are equal to $$$“11”$$$.

To increase the number of substrings $$$“11”$$$ , it is optimal to get more $$$1’s$$$ in $$$T$$$. so we have to flip the characters in S which are equal to $$$0$$$.

Let $$$m \le cnt0$$$, where $$$cnt0$$$ is the number of $$$0’s$$$ in $$$S$$$. Consider two possible scenes in $$$S$$$ :

$$$1.$$$ $$$....1001....$$$

$$$2.$$$ $$$....101....$$$

If you change single $$$0$$$ to $$$1$$$ in $$$1^{st}$$$ case the answer will increase by $$$1$$$, but in second case the answer will increase by $$$2$$$(easy to see, right?).

Which implies that it is always optimal to change $$$0$$$ to $$$1$$$ in substring where contiguous $$$0’s$$$ are minimum.

The cases $$$....11000....$$$ and $$$....00011....$$$ are both similar where changing single $$$0$$$ to $$$1$$$ will increase answer by $$$1$$$.

Note the case where $$$....0000....$$$, i.e., all are $$$0’s$$$, in this case initially atleast we have to change two $$$0’s$$$ to increase our answer.

What if $$$m > cnt0$$$ ?

Yes, now we have to turn the initial $$$1’s$$$ in $$$S$$$ to $$$0’s$$$ which will decrease the answer by minimum (initial $$$1’s$$$ in $$$S$$$ means not flipped $$$1’s$$$ in $$$S$$$).

Again, lets consider two possible scenes in $$$S$$$.

$$$1.$$$ $$$....1(11)1....$$$

$$$2.$$$ $$$....(11)11....$$$

$$$1’s$$$ in the brackets are initial $$$1’s$$$ in $$$S$$$, now changing $$$1$$$ to $$$0$$$ in first case decreases the answer by $$$2$$$, but in second case answer decreases by $$$1$$$(easy to see, right?).

Which implies that changing initial $$$1’s$$$ to $$$0$$$ in segment where $$$S$$$ contains maximum $$$1’s$$$ is optimal.

The cases $$$....1000....$$$ and $$$....00011....$$$ are both similar where changing single $$$1$$$ to $$$0$$$ will decrease answer by $$$1$$$.

We can do precomputations on the above information. (Yeah I know it’s weird to implement things, but expecting some smarter implementations).

So, Time Complexity : $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        string s;
        cin>>s;
        vector<ll> v1,v0;
        ll ex1=0,ex0=0;
        ll ind1=-1,ind2=-1;
        for(ll i=0;i<n;i++){
            if(s[i]=='1') ind2=i;
        }
        for(ll i=n-1;i>=0;i--){
            if(s[i]=='1') ind1=i;
        }
        if(ind1!=-1){
            ll cnt=0;
            for(ll i=ind1;i<=ind2;i++){
                if(s[i]=='0') cnt++;
                else{
                    if(cnt>0) v0.push_back(cnt);
                    cnt=0;
                }
            }
            sort(v0.begin(),v0.end());
            for(ll i=1;i<(ll)v0.size();i++) v0[i]+=v0[i-1];
            ex0=(ind1+(n-1-ind2));
        }
        else ex0=n;
        ind1=-1;
        ind2=-1;
        for(ll i=0;i<n;i++){
            if(s[i]=='0') ind2=i;
        }
        for(ll i=n-1;i>=0;i--){
            if(s[i]=='0') ind1=i;
        }
        if(ind1!=-1){
            ll cnt=0;
            for(ll i=ind1;i<=ind2;i++){
                if(s[i]=='1') cnt++;
                else{
                    if(cnt>0) v1.push_back(cnt);
                    cnt=0;
                }
            }
            sort(v1.begin(),v1.end());
            for(ll i=1;i<(ll)v1.size();i++) v1[i]+=v1[i-1];
            ex1=(ind1+(n-1-ind2));
        }
        else ex1=n;
        ll n0=ex0,n1=ex1;
        if((ll)v0.size()>0) n0+=v0.back();
        if((ll)v1.size()>0) n1+=v1.back();
        vector<ll> res0(n0+1),res1(n1+1);
        ll j=0;
        for(ll i=1;i<=n0;i++){
            res0[i]=res0[i-1]+1;
            if(j<(ll)v0.size() && i==v0[j]){
                res0[i]++;
                j++;
            }
        }
        j=0;
        for(ll i=1;i<=n1;i++){
            res1[i]=res1[i-1]+1;
            if(j<(ll)v1.size() && i==v1[j]){
                res1[i]++;
                j++;
            }
        }
        ll cnt0=0,cnt1=0;
        for(ll i=0;i<n-1;i++){
            if(s[i]=='1' && s[i+1]=='1') cnt0++;
            if(s[i]=='0' && s[i+1]=='0') cnt1++;
        }
        for(ll i=0;i<=n;i++){
            ll k=i;
            if(n0==n) cout<<max((ll)0,k-1)<<" ";
            else if(n1==n) cout<<max((ll)0,n-k-1)<<" ";
            else if(k<=n0) cout<<cnt0+res0[k]<<" ";
            else{
                k=n-k;
                cout<<cnt1+res1[k]<<" ";
            }
        }
        cout<<"\n";
    }
}

It is quite difficult to get optimal operations for changing $$$a$$$ to $$$b$$$. But it was easy to change $$$b$$$ to $$$a$$$(i.e, reversing operation).

Now the problem is choose any $$$i(0 \le i \le n-1)$$$ and select $$$k$$$ elements from left side of $$$b_i$$$ and $$$k$$$ elements from right side $$$b_i$$$ and remove it’s sum from $$$b_i$$$.

It's easy to see that every element has a contribution on the left $$$k$$$ elements and right $$$k$$$ elements, so it’s obviously optimal to do operations first on bigger element in $$$b$$$. Otherwise this maximum $$$b$$$ comes to attack and decrease other element to less than $$$0$$$ $$$(less \ than \ maximum \ - \ maximum \ < \ 0)$$$.

We can decrease the element to as much as possible in a single operation, so every element was considered atmost $$$log(b_i)$$$ times in an operation.

We can use $$$BIT(Fenwick \ Tree)$$$ to handle the segmental operations(i.e., range query, point update).

Time complexity : $$$O(nlognlog(M/k))$$$, where $$$M$$$ is the maximum element in the array $$$b$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
ll N,K;

template <typename T>
struct BIT {
  ll N;
  vector<T> tree;

  BIT(ll n_) : N(n_+1) {
    tree.resize(N);
  }

  void update(ll ind,T val) {
    for(++ind;ind<N;ind+=ind&-ind) tree[ind]+=val;
  }

  T query(ll in) {
    T sum=0;
    for(++in;in>0;in-=in&-in) sum+=tree[in];
    return sum;
  }

  T query(ll l, ll r) {
    return query(r)-query(l-1);
  }
};

int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        cin>>N>>K;
        vector<ll> A(N),B(N);
        for(ll i=0;i<N;i++) cin>>A[i];
        for(ll i=0;i<N;i++) cin>>B[i];
        BIT<ll> Bit(N);
        for(ll i=0;i<N;++i)
        Bit.update(i,B[i]);
        ll sum = Bit.query(0,N-1);
        auto get = [&](ll l, ll r) {
            if(l>r) {
                if(r+1>l-1)
                return sum;
                return sum-Bit.query(r+1,l-1);
            }
            return Bit.query(l,r);
        };
        
        if(K==0){
            cout<<(A!=B?-1:0)<<"\n";
        }
        else{
            auto index = [&](ll x) {
                x%=N;
                if(x<0)
                    x+=N;
                if(x>=N)
                    x-=N;
                return x;
            };

            vector<ll> ps(N+1);
            priority_queue<pair<ll, ll>> pq;
            for(ll i=0;i<N;++i) if(A[i]!=B[i]){
                pq.emplace(B[i],i);
            }
            ll ops=0;
            while(!pq.empty()){
                ll y=pq.top().first;
                ll p=pq.top().second;
                pq.pop();

                auto F = get(index(p-K),index(p+K));
                    if(A[p]>y%(F-y) && A[p]%(F-y)!=y%(F-y)) {
                    break;
                }
                B[p]=max((ll)A[p],y%(F-y));
                ops+=(y-B[p])/(F-y);
                Bit.update(p,B[p]-y);
                sum+=B[p]-y;

                if(B[p]==y) {
                    assert(A[p]!=B[p]);
                    break;
                }   

                if(B[p]<A[p])
                    break;

                if(A[p]!=B[p])
                    pq.emplace(B[p],p);
            }
            if(A==B) cout<<ops<<"\n";
            else cout<<"-1\n";
        }
    }
}

The useless part in the problem is number of queries, it is always optimal to put a single edge between two nodes and the remaining unnecessary edges will be considered as your wish. we can find optimal answer for every $$$k(1 \le k \le n-1)$$$ edges added to graph and we will answer every query in $$$O(1)$$$ time.

Let's solve the problem using $$$Dynamic \ Programming$$$.

Let $$$dp1[i][j]$$$ is maximum number of coins obtained when $$$j$$$ edges are choosen in the first $$$i+1$$$ nodes while considering $$$i^{th}$$$ edge is choosen.

Let $$$dp2[i][j]$$$ is maximum number of coins obtained when $$$j$$$ edges are choosen in the first $$$i+1$$$ nodes while considering $$$i^{th}$$$ edge is not choosen.

$$$1.$$$ $$$dp1[i][j] = \max_{k=1}^i(dp2[k][j-i+k]+d[k][i])$$$, where $$$d[k][i]$$$ means maximum coins obtained when adding every edge from $$$k^{th}$$$ node to $$$i^{th}$$$ node.

$$$2.$$$ $$$dp2[i][j] = max(dp2[i-1][j],dp1[i-1][j])$$$.

From this bruteforce $$$DP$$$, we can solve the problem in $$$O(n^3)$$$ which is too slow for both versions, Let's try to optimize for easier version first.

Note that $$$dp1[i][j]$$$ is dependent on $$$dp2[i][j]$$$ for only same differences in $$$(i-j)$$$. so just precompute the values of $$$d[k][i]$$$ and update the information of $$$dp2[i][j]$$$ on segment tree to get the maximum value of $$$dp2[k][j-i+k]+d[k][i]$$$ in $$$logn$$$ time. By this optimization we can solve the Easy Version of the problem with the Time Complexity : $$$O(n^{2}logn)$$$.

For solving Hard version we need some more classical data structure which will do the above operations quite faster.

Since we are only adding positive integers to the segment tree, there will only be merging of segments and not splitting of segments. Using a disjoint set data structure, we can maintain which segment each number belongs to in a reasonable amount of time.

From this optimization, now we can solve the problem in Time Complexity : $$$O(nm(invack(n)))$$$, where $$$invack(n)$$$ stands for inverse Ackermann function in the union-find complexity.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
ll n,m,maxi;
vector<vector<pair<ll,ll>>> adj(10010);
vector<ll> dp(10010),ans(10010),par(10010);
ll dp1[10010];

ll find(ll u){
    if(par[u]==u) return u;
    return par[u]=find(par[u]);
}

void push(ll cur,ll val){
	if(val<=maxi){
		par[cur]=cur+1;
		return;
	}
	dp1[cur]=val-maxi;
	maxi=val;
}

void update(ll cur,ll p,ll val){
	if(find(1)>p) return;
	ll u=find(p+1),v;
	if(u>cur){
		maxi+=val;
		return;
	}
	dp1[u]-=val;
	while(dp1[u]<=0){
		v=find(u+1);
		if(v>cur){
			maxi-=dp1[u];
			par[u]=v;
			return;
		}
		dp1[v]+=dp1[u];
		par[u]=v;
		u=v;
	}
}

int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll q;
        cin>>n>>m>>q;
        n--;
        for(ll i=1;i<=n;i++){
            adj[i].clear();
            dp[i]=0;
            ans[i]=0;
        }
        for(ll i=0;i<m;i++){
            ll u,v,w;
            cin>>u>>v>>w;
            if(u>v) swap(u,v);
            v--;
            adj[v].push_back({u,w});
        }
        dp[0]=0;
        for(ll i=1;i<=n;i++){
            dp[i]=dp[i-1];
            for(auto j:adj[i]) dp[i]+=j.second;
        }
        for(ll i=0;i<n;i++){
            ans[n-i]=dp[n];
            for(ll j=n;j>0;j--){
                dp[j]=dp[j-1];
            }
            dp[0]=-1e18;
            for(ll i1=1;i1<=i+1;i1++) par[i1]=i+2;
            for(ll i1=i+2;i1<=n+1;i1++) par[i1]=i1;
            fill(dp1,dp1+n+1,0);
            maxi=-1e9;
            for(ll i1=i+2;i1<=n;i1++){
                push(i1,dp[i1-1]);
                for(auto j:adj[i1]) if(j.first>=i+2) update(i1,j.first,j.second);
			    dp[i1]=max(dp[i1],maxi);
            }
        }
        while(q--){
            ll kk;
            cin>>kk;
            kk=min(kk,n);
            cout<<ans[kk]<<"\n";
        }
    }
}

TheForces is a project uniting individuals with a shared interest in competitive programming contests. You can join our discord server with more than $$$2200$$$ members to communicate with founders and members of TheForces.

In the other words TheForces rounds are series of educational contests for beginners to masters which are created by a group of CP lovers in the CF community, It's where anyone can propose and prepare his own interesting problems and receive money!

Not to mention that we've already created two official codeforces div(1 + 2) rounds before ;) so join us now!

Discord link

TheForces website

For Alice, what if choosing the maximum value doesn't work?

Consider parity.

Case $$$1$$$: When all values appear an even number of times, Alice will lose. This is because no matter which number Alice chooses, Bob can mimic Alice's move.

Case $$$2$$$: When at least one value appears an odd number of times, Alice will win. Alice only needs to choose the maximum value that appears an odd number of times, which will force Bob into Case $$$1$$$.

Time complexity: $$$O(n)$$$.

Sort the array $$$a$$$ in non-increasing order. We can observe that any state can be represented as a prefix of the array $$$a$$$. Consider dynamic programming: let $$$dp_i$$$ denote whether the first player is guaranteed to win when the state is $$$a_{1...i}$$$ ($$$dp_i=1$$$ indicates a guaranteed win for the first player). We have the following formula:

• $$$dp_1=1$$$;

• $$$dp_i= \sim (dp_{i-1}$$$ & $$$dp_{id_1-1}$$$ & $$$dp_{id_2-1} \ldots)$$$, where $$$id_j$$$ satisfies $$$a_{id_j} \neq a_{id_j+1}$$$ and $$$id_j < i$$$.

Time complexity: $$$O(n^2)$$$.

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 55;

int n;
int q[N];

void solv()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        q[i] = 0;
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;
        ++q[x];
    }

    for (int i = 1; i <= n; ++i)
    {
        if (q[i] % 2 == 1)
        {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

Starting from a trival construction.

Utilize the condition $$$x > y$$$.

First, we consider making $$$presum_x > presum_j$$$ for all $$$x < i \le n$$$, and similarly for $$$y$$$. We can think of a trivial construction: $$$a[r, \ldots ,l]=[1, \ldots ,1], a[1, \ldots...,r-1]=[-1, \ldots, -1]$$$ and $$$a[l+1,\ldots,n]=[-1, \ldots, -1]$$$.

The construction doesn't works when $$$presum_x<0$$$, but we are close to the correct solution. Next, we will make a little adjustment: $$$a[r, \ldots, l]=[1,\ldots,1], a[1, \ldots...,r-1]=[\ldots,1, -1]$$$ and $$$a[l+1,\ldots,n]=[-1,1, \ldots]$$$.

It is not hard to see $$$presum_x \ge presum_j$$$ for all $$$x < i \le n$$$, and for $$$1 \le i \le y$$$, $$$\max(presum_i)-min(presum_i)\le 1$$$. Thus, we get $$$presum_x \ge 2+presum_{y-1} \ge 2+min(presum_i) \ge 1+max(presum_i)$$$. The same applies to the suffix sum as well. Therefore, this construction is valid.

Time complexity: $$$O(n)$$$.

Solve the problem when $$$x \le y$$$.

#include<bits/stdc++.h>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    int n,x,y;
    cin >> n >> x >> y;
    x--; y--;
    vector<int> a(n,1);
    int e;
    e=-1;
    for(int i=x+1;i<n;i++){
      a[i]=e;
      e*=-1;
    }
    e=-1;
    for(int i=y-1;i>=0;i--){
      a[i]=e;
      e*=-1;
    }
    for(int i=0;i<n;i++){
      if(i){cout << " ";}
      cout << a[i];
    }cout << "\n";
  }
  return 0;
}

After one operation, the array becomes non-decreasing.

Consider $$$a_1=a_2=\ldots=a_n$$$, the operation seems to have shifted the array right.

When does the "right shift" parttern happen?

Read hints first.

Let's consider only non-decreasing arrays. Observe a continuous segments $$$a[l...r]=x(l<r,x>0)$$$, after one operation, we get $$$a[l+1,min(r+1,n)]=x$$$ holds. We can conclude that if, for all non-zero contiguous segments in the array (except the last one), their lengths are all greater than $$$1$$$, then the array follows the "right shift" parttern. Let's say this kind of array "good".

The last problem is when will the array become "good". Let's assume we get the array $$$b$$$ after one operation on array $$$a$$$, we get $$$b_i<b_{i+1}<b_{i+2}$$$. We can infer that $$$b_i=a_i,b_{i+1}=a_{i+1}$$$ and there is at least $$$a_j=a_{i+1}(j \le i)$$$, which shows that $$$a$$$ is not non-decreasing. In other words, after two operations, we can always get a "good" array. Then the calculating is trival.

Time complexity: $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005;

int n;
int a[N];

bool c[N];
void doit()
{
    for (int i = 1; i <= n; ++i)
        c[i] = false;
    int maxu = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (c[a[i]])
            maxu = max(maxu, a[i]);
        c[a[i]] = true;
        a[i] = maxu;
    }
}

void solv()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    ll ans = 0;
    for (int i = 1; i <= n; ++i)
        ans += a[i];
    doit();
    for (int i = 1; i <= n; ++i)
        ans += a[i];
    doit();

    for (int i = 1; i <= n; ++i)
        ans += (n - i + 1) * 1LL * a[i];
    cout << ans << "\n";
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

The title "Mad MAD Sum" is not only a pun on the words Mad and MAD (Maximum Appearing Duplicate), but also implies the solution to the problem :)

Obviously, when $$$a_i$$$ is large enough, we will definitely use operation $$$2$$$ on the $$$i$$$-th row. What is its specific value?

It is $$$5$$$(try to prove it). Now we can only consider $$$a_i \le 4$$$ cases.

From left to right, consider a greedy solution or a DP solution.

Read hints first.

For $$$a_i \ge 5$$$, we will definitely use operation $$$2$$$ on the $$$i$$$-th row because at least three $$$2 \times 2$$$ subgrid are needed to cover it, which is not better then do three times operation $$$2$$$ in the $$$i-1,i$$$ and $$$i+1$$$ row.

Now we can only consider $$$a_i \le 4$$$ cases. Let's consider from left to right.

In the left most row, there are $$$3$$$ cases:

• there is no black cells Do nothing;

• there is $$$\le 2$$$ black cells. We can put one $$$2 \times 2$$$ subgrid greedily;

• there is $$$> 2$$$ black cells. We just use one time operation $$$2$$$ in this row(try to prove it).

We can summarize that for the $$$i$$$-th row, there are only three situations where it is affected by the $$$i-1$$$-th row:

• it is not affected;

• the cells in the third and fourth columns have been colored white;

• the cells in the first and second columns have been colored white.

We can greedily process this process from left to right, or use DP.

Time complexity: $$$O(n)$$$.

#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MODD 998244353

long long int bigmod(long long int a,long long int b){
    long long int ans=1,powa=a;
    while(b>0){
        if(b%2==1){
            ans*=powa;
            ans%=MOD;
        }
        powa=powa*powa;
        powa%=MOD;
        b/=2;
    }
    return ans;
}

void func(){
    int n;
    cin >> n;
    int arr[n];
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }
    bool b1=0,b2=0;
    int ans=0;
    for(int i=0;i<n;i++){
        if((!b1)&&(!b2)){
            if(arr[i]==0) continue;
            ans++;
            if(arr[i]<=2) b1=1;
        }
        else if(b1){
            b1=0;
            if(arr[i]<=2) continue;
            ans++;
            if(arr[i]<=4) b2=1;
        }
        else{
            b2=0;
            if(arr[i]==0) continue;
            ans++;
            if(arr[i]<=4) b1=1;
        }
    }
    cout << ans << '\n';
    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        func();
    }
}
//i added the bigmod func to my code cause yes

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005;

int n;
int a[N];

int dp[N];
void minh(int& x, int y)
{
    x = min(x, y);
}

void solv()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    int minu[2] = {N, N};
    for (int i = 1; i <= n; ++i)
    {
        dp[i] = dp[i - 1] + 1;
        if (a[i] == 0)
            minh(dp[i], dp[i - 1]);
        if (a[i] <= 2)
            minh(dp[i], i + minu[1 - i % 2]);

        if (a[i] <= 2)
            minh(minu[i % 2], dp[i - 1] - i);
        else if (a[i] > 4)
            minu[0] = minu[1] = N;
    }

    cout << dp[n] << "\n";
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

Consider querying a subtree. If the jury returns $$$0$$$, we can delete the entire subtree.

We can query any leaf node. If the jury returns $$$1$$$, we are done; otherwise, the mole will move up.

Consider querying a subtree. If the jury returns $$$1$$$, we can "drive" it out of this subtree using the method in hint2.

Combime the idea in hint $$$1$$$ and $$$3$$$.

Read hints first.

For easy version, we can pick a vertex $$$v$$$ such that $$$maxdep_v-dep_v+1=50$$$:

1. if the jury returns $$$0$$$, we can delete the entire subtree;

2. otherwise, make queries until it is out and answer $$$fa_v$$$(a special case is $$$v=1$$$); 

3. if there is no such vertex, then make $$$100$$$ queries and answer the root node $$$1$$$.

This costs about $$$200$$$ queries, which can not pass hard version. But we can optimize it.

The bottleneck is the step $$$2$$$, when we drive away this mole once, we need to immediately check if it is still in the subtree $$$v$$$, which can be optimized. In fact, we can drive the mole 50 times and then perform a binary search on the chain from $$$v$$$ to the root node.

Number of queries: $$$O(2sqrt(n)+log(n))$$$

Query any leaf $$$70$$$ times, then delete all nodes $$$x$$$ such that $$$maxdep_v-dep_v+1<=70$$$. Then the tree can be split into $$$\le 70$$$ chains. Do binary search for these chains.

Solve the problem in $$$100$$$ queries.

#include<bits/stdc++.h>
using namespace std;

#define all(a) a.begin(),a.end()
#define pb push_back
#define sz(a) ((int)a.size())

using ll=long long;
using u32=unsigned int;
using u64=unsigned long long;
using i128=__int128;
using u128=unsigned __int128;
using f128=__float128;

using pii=pair<int,int>;
using pll=pair<ll,ll>;

template<typename T> using vc=vector<T>;
template<typename T> using vvc=vc<vc<T>>;
template<typename T> using vvvc=vc<vvc<T>>;

using vi=vc<int>;
using vll=vc<ll>;
using vvi=vc<vi>;
using vvll=vc<vll>;

#define vv(type,name,n,...) \
    vector<vector<type>> name(n,vector<type>(__VA_ARGS__))
#define vvv(type,name,n,m,...) \
    vector<vector<vector<type>>> name(n,vector<vector<type>>(m,vector<type>(__VA_ARGS__)))

template<typename T> using min_heap=priority_queue<T,vector<T>,greater<T>>;
template<typename T> using max_heap=priority_queue<T>;

// https://trap.jp/post/1224/
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define rep_subset(i,s) for(ll i=(s); i>=0; i=(i==0?-1:(i-1)&(s)))

template<typename T, typename S> constexpr T ifloor(const T a, const S b){return a/b-(a%b&&(a^b)<0);}
template<typename T, typename S> constexpr T iceil(const T a, const S b){return ifloor(a+b-1,b);}

template<typename T>
void sort_unique(vector<T> &vec){
    sort(vec.begin(),vec.end());
    vec.resize(unique(vec.begin(),vec.end())-vec.begin());
}

template<typename T, typename S> constexpr bool chmin(T &a, const S b){if(a>b) return a=b,true; return false;}
template<typename T, typename S> constexpr bool chmax(T &a, const S b){if(a<b) return a=b,true; return false;}

template<typename T, typename S> istream& operator >> (istream& i, pair<T,S> &p){return i >> p.first >> p.second;}
template<typename T, typename S> ostream& operator << (ostream& o, const pair<T,S> &p){return o << p.first << ' ' << p.second;}

#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 777771449
#endif

template<typename T> void print(vector<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(unordered_set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(T && x) {cout << x << "\n";}
template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);}

template<typename T> istream& operator >> (istream& i, vector<T> &vec){for(auto &x: vec) i >> x; return i;}

vvi read_graph(int n, int m, int base=1){
    vvi adj(n);
    for(int i=0,u,v; i<m; ++i){
        cin >> u >> v,u-=base,v-=base;
        adj[u].pb(v),adj[v].pb(u);
    }
    return adj;
}

vvi read_tree(int n, int base=1){return read_graph(n,n-1,base);}

template<typename T, typename S> pair<T,S> operator + (const pair<T,S> &a, const pair<T,S> &b){return {a.first+b.first,a.second+b.second};}

template<typename T> constexpr T inf=0;
template<> constexpr int inf<int> = 0x3f3f3f3f;
template<> constexpr ll inf<ll> = 0x3f3f3f3f3f3f3f3f;

template<typename T> vector<T> operator += (vector<T> &a, int val){for(auto &i: a) i+=val; return a;}

template<typename T> T isqrt(const T &x){T y=sqrt(x+2); while(y*y>x) y--; return y;}

#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())

//#include<atcoder/all>
//using namespace atcoder;

//using mint=modint998244353;
//using mint=modint1000000007;

struct Tree{
    int n;
    vector<vector<int>> adj,anc;
    vector<int> par,tl,tr,dep,ord,siz,ch,head;
    Tree(int _n=0){
        n=_n;
        adj.resize(n);
    }
    void add_edge(int u, int v){
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void init(){
        par.resize(n),tl.resize(n),tr.resize(n),dep.resize(n),anc.resize(n),siz.resize(n),ch.resize(n),head.resize(n);
        int cur=-1,m=0;
        while((1<<m)<=n) m++;
        for(int i=0; i<n; ++i) anc[i].resize(m),ch[i]=-1;
        auto dfs1=[&](auto &self, int u, int fa) -> void{
            par[u]=fa;
            siz[u]=1;
            for(int v: adj[u]) if(v!=fa) self(self,v,u),siz[u]+=siz[v];
            for(int v: adj[u]) if(v!=fa&&(ch[u]==-1||siz[v]>siz[ch[u]])) ch[u]=v;
        };
        auto dfs2=[&](auto &self, int u, int fa) -> void{
            ord.push_back(u);
            tl[u]=++cur;
            anc[u][0]=fa;
            if(fa==-1) dep[u]=0;
            else dep[u]=dep[fa]+1;
            for(int i=1; i<m; ++i){
                if(anc[u][i-1]==-1) anc[u][i]=-1;
                else anc[u][i]=anc[anc[u][i-1]][i-1];
            }
            if(ch[u]!=-1) self(self,ch[u],u);
            for(int v: adj[u]) if(v!=fa&&v!=ch[u]) self(self,v,u);
            tr[u]=cur;
        };
        dfs1(dfs1,0,-1);
        dfs2(dfs2,0,-1);
        head[0]=0;
        for(int u: ord){
            for(int v: adj[u]) if(v!=par[u]){
                if(v==ch[u]) head[v]=head[u];
                else head[v]=v;
            }
        }
    }
    bool is_anc(int u, int v){return tl[u]<=tl[v]&&tr[u]>=tr[v];}
    int get_anc(int u, int x){
        for(int i=anc[0].size()-1; i>=0; --i) if(u!=-1&&(x>>i&1)) u=anc[u][i];
        return u;
    }
    int lca(int u, int v){
        if(is_anc(u,v)) return u;
        for(int i=anc[0].size()-1; i>=0; --i) if(anc[u][i]!=-1&&!is_anc(anc[u][i],v)) u=anc[u][i];
        return par[u];
    }
};

void ahcorz(){
    int lft=150;
    auto query=[&](int u){
        assert(lft>0);
        cout << "? " << u+1 << endl;
        lft--;
        int res; cin >> res; return res;
    };
    int n; cin >> n;
    Tree tree(n);
    rep(n-1){
        int u,v; cin >> u >> v; u--,v--;
        tree.add_edge(u,v);
    }
    tree.init();
    vi vis(n);
    auto fill_vis=[&](auto &self, int u){
        if(vis[u]) return;
        vis[u]=1;
        for(int v: tree.adj[u]) if(v!=tree.par[u]) self(self,v);
    };
    vi ord(n); iota(all(ord),0);
    sort(all(ord),[&](int i, int j){return tree.dep[i]<tree.dep[j];});
    per(n){
        int u=ord[i];
        if(vis[u]) continue;
        int v=u;
        rep(_,(lft-1)/2-1){
            if(v==0) break;
            v=tree.par[v];
        }
        if(!query(v)){
            fill_vis(fill_vis,v);
            continue;
        }
        int x=tree.ord.back();
        int m=tree.dep[u]-tree.dep[v]+1;
        rep(_,m){
            if(query(x)){
                cout << "! " << x+1 << endl;
                return;
            }
            if(!query(v)){
                int y=tree.par[v];
                if(y!=-1) y=tree.par[y];
                if(y==-1) y=0;
                cout << "! " << y+1 << endl;
                return;
            }
        }
        cout << "! 1" << endl;
        return;
    }
    assert(0);
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cout << fixed << setprecision(20);
    int t=1;
    cin >> t;
    while(t--) ahcorz();
}

Consider using a segment tree to solve this problem. We need to merge the information of two intervals. First, we take the maximum value of the answers in the two intervals, and then calculate the polygon segment spanning the two intervals.

We notice that a local maximal polygon segment $$$[l, r]$$$ must satisfy $$$min(a_{l-1}, a_{r+1}) >= 2(a_l + ... + a_r)$$$(or $$$l=1$$$,$$$r=n$$$).

Define the suffix $$$[i, r]$$$ of the interval $$$[l, r]$$$ as a special suffix if and only if $$$a_i+ \ldots +a_r$$$ $$$\le 2 \cdot a_i$$$. The same principle applies to special prefixes.

We can observe that there are at most $$$O(log(maxa))$$$ special suffixes, because the sum of one special suffix is at least twice the sum of the previous special suffix. Therefore, we can merge the special suffixes of the left interval and the special prefixes of the right interval (using the two-pointer algorithm) to obtain the answer spanning the two intervals.

Number of queries: $$$O(nlog^2(n))$$$

Consider the following process:

query(l,r)
    if r-l+1<3 return -1
    mxp=getmaxpos(l,r)
    if 2*a[mxp]<getsum(l,r) return r-l+1
    else return max(query(l,mxp-1),query(mxp+1,r))

This looks $$$O(n^2)$$$ when $$$a=[1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,16,... ]$$$. However, if we store all the ranges which are already calculated, it becomes $$$O(n log n)$$$.

Why? Let's call a range $$$[l,r]$$$ "key range" when $$$sum(a[l...r])<=2min(a[l-1],a[r+1])$$$. We can see:

1.There're only $$$O(n log n)$$$ different key ranges;

2.We only visit at most $$$2$$$ ranges which are not key range in each query.

Assume we have changed $$$a_p$$$. We need to clear all the answer of key ranges which pass through $$$p$$$. We can use interval tree to achieve it.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,q;
ll  a[N];

//---------------------------------------------------------- 

struct INFO
{
	int ans,l,r;
	ll  sum;
	vector<int> lpos,rpos;
	vector<ll>  lsum,rsum;
};

struct nod
{
	INFO info;
	nod  *lc,*rc;
};

struct Segtree
{
	nod *root;
	
	Segtree() 
	{
		build(&root,1,n);
	}
	
	void newnod(nod **p,int l,int r)
	{
		*p=new nod;
		(*p)->info.l=l;
		(*p)->info.r=r;
		(*p)->info.sum=(*p)->info.ans=0;
		(*p)->lc=(*p)->rc=NULL;
	}
	
	INFO merge_info(INFO x,INFO y)
	{
		INFO z;
		z.l=x.l;
		z.r=y.r;
		z.sum=x.sum+y.sum;
		z.ans=max(x.ans,y.ans);
		int px=(int)x.lpos.size()-1,py=0;
		ll  mx=0;
		//
		//return z;
		//
		//
		while(1) //two pointer
		{
			int len=0;
			ll  sum=0;
			if(px<0) 
			{
			    sum+=x.sum;
			    len+=(x.r-x.l+1);
			}
			else     
			{
			    sum+=x.lsum[px]-a[x.lpos[px]];
				len+=(x.r-x.lpos[px]);
			}
			if(py<y.rpos.size()) 
			{
			    sum+=y.rsum[py]-a[y.rpos[py]];
				len+=(y.rpos[py]-y.l);
			}
			else
			{
			    sum+=y.sum;
			    len+=(y.r-y.l+1);
			}
			if(sum>2*mx) z.ans=max(z.ans,len);
			if(px<0&&py>=y.rpos.size()) break;
			else if(px<0) mx=max(mx,a[y.rpos[py]]),py++;
			else if(py>=y.rpos.size()) mx=max(mx,a[x.lpos[px]]),px--;
			else if(a[x.lpos[px]]<a[y.rpos[py]]) mx=max(mx,a[x.lpos[px]]),px--;
			else mx=max(mx,a[y.rpos[py]]),py++;
		}
		//
		/*
		z.lpos.resize(1);
		z.rpos.resize(1);
		z.lsum.resize(1);
		z.rsum.resize(1);
		*/
		//
		if(z.ans<3) z.ans=-1;
		for(int i=0;i<x.lpos.size();i++)
		    if(2*a[x.lpos[i]]>=x.lsum[i]+y.sum) z.lpos.push_back(x.lpos[i]),z.lsum.push_back(x.lsum[i]+y.sum);
        for(int i=0;i<y.lpos.size();i++) 
		    z.lpos.push_back(y.lpos[i]),z.lsum.push_back(y.lsum[i]);
		for(int i=0;i<x.rpos.size();i++)
		    z.rpos.push_back(x.rpos[i]),z.rsum.push_back(x.rsum[i]);
        for(int i=0;i<y.rpos.size();i++) 
		    if(2*a[y.rpos[i]]>=y.rsum[i]+x.sum) z.rpos.push_back(y.rpos[i]),z.rsum.push_back(y.rsum[i]+x.sum);
		//
		return z;
	}
	
	void build(nod **p,int L,int R)
	{
		newnod(p,L,R);
		if(L==R)
		{
			(*p)->info.sum=a[L];
			(*p)->info.ans=-1;
			(*p)->info.lpos.push_back(L);
			(*p)->info.rpos.push_back(L);
			(*p)->info.lsum.push_back(a[L]);
			(*p)->info.rsum.push_back(a[L]);
			return ;
		}
		int M=(L+R)>>1;
		build(&(*p)->lc,L,M);
		build(&(*p)->rc,M+1,R);
		(*p)->info=merge_info((*p)->lc->info,(*p)->rc->info);
	}
	
	void modify(int pos,ll val)
	{
		_modify(root,pos,val);
	}
	
	void _modify(nod *p,int pos,ll val)
	{
		if(p->info.l==p->info.r)
		{
			p->info.sum=val;
			p->info.lpos[0]=pos;
			p->info.rpos[0]=pos;
			p->info.lsum[0]=val;
			p->info.rsum[0]=val;
			return ;
		}
		int M=(p->info.l+p->info.r)>>1;
		if(pos<=M) _modify(p->lc,pos,val);
		else       _modify(p->rc,pos,val);
		p->info=merge_info(p->lc->info,p->rc->info);
	}
	
	ll getans(int L,int R)
	{
		return _getans(root,L,R).ans;
	}
	
	INFO _getans(nod *p,int L,int R)
	{
		if(p->info.l==L&&p->info.r==R) return p->info;
		int M=(p->info.l+p->info.r)>>1;
		if(R<=M)     return _getans(p->lc,L,R);
		else if(L>M) return _getans(p->rc,L,R);
		else return merge_info(_getans(p->lc,L,M),_getans(p->rc,M+1,R));
	}
};

//---------------------------------------------------------- 


int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;i++) scanf("%I64d",&a[i]);
		Segtree TR;
		for(int i=1;i<=q;i++)
		{
			int t;
			scanf("%d",&t);
			if(t==1)
			{
				int l,r;
				scanf("%d%d",&l,&r);
				printf("%I64d\n",TR.getans(l,r));
			}
			else
			{
				int p;
				ll  x;
				scanf("%d%I64d",&p,&x);
				a[p]=x;
				TR.modify(p,x);
			}
		}
	}
	
	//fclose(stdin);
	return 0;
}

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

/**
 * Point-update Segment Tree
 * Source: kactl
 * Description: Iterative point-update segment tree, ranges are half-open i.e [L, R).
 *              f is any associative function.
 * Time: O(logn) update/query
 */

template<class T, T unit = T()>
struct SegTree {
	T f(T a, T b) {
        a[0] += b[0];
        if (a[1] < b[1]) a[1] = b[1], a[2] = b[2];
        return a;
    }
	vector<T> s; int n;
	SegTree(int _n = 0, T def = unit) : s(2*_n, def), n(_n) {}
	void update(int pos, T val) {
		for (s[pos += n] = val; pos /= 2;)
			s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
	}
	T query(int b, int e) {
		T ra = unit, rb = unit;
		for (b += n, e += n; b < e; b /= 2, e /= 2) {
			if (b % 2) ra = f(ra, s[b++]);
			if (e % 2) rb = f(s[--e], rb);
		}
		return f(ra, rb);
	}
};

#include <ext/pb_ds/assoc_container.hpp>

struct splitmix64_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};

template <typename K, typename V, typename Hash = splitmix64_hash>
using hash_map = __gnu_pbds::gp_hash_table<K, V, Hash>;

template <typename K, typename Hash = splitmix64_hash>
using hash_set = hash_map<K, __gnu_pbds::null_type, Hash>;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n, q; cin >> n >> q;
        vector<ll> a(n);
        for (auto &x : a) cin >> x;

        map<ll, int> cache;

        struct Node {
            int L, R, M; // [L, R)
            set<array<int, 2>> by_l, by_r;
            void ins(int l, int r) {
                by_l.insert({l, r});
                by_r.insert({r, l});
            }
            void del(int l, int r) {
                by_l.erase({l, r});
                by_r.erase({r, l});
            }
        };
        vector<Node> ITree(4*n);
        auto build = [&] (const auto &self, int node, int l, int r) -> void {
            int mid = (l + r)/2;
            ITree[node].L = l;
            ITree[node].R = r;
            ITree[node].M = mid;
            if (l+1 == r) return;
            self(self, 2*node + 1, l, mid);
            self(self, 2*node + 2, mid, r);
        };
        build(build, 0, 0, n);
        auto insert = [&] (const auto &self, int node, int l, int r) -> void { // Insert interval [l, r) into the tree
            if (ITree[node].L+1 == ITree[node].R) {
                ITree[node].ins(l, r);
                return;
            }

            if (l >= ITree[node].M) self(self, 2*node+2, l, r);
            else if (r <= ITree[node].M) self(self, 2*node+1, l, r);
            else ITree[node].ins(l, r);
        };
        auto erase = [&] (const auto &self, int node, int x) -> void { // Delete all intervals covering point x
            if (x < ITree[node].M) {
                // Delete some prefix
                auto &st = ITree[node].by_l;
                while (!st.empty()) {
                    auto [l, r] = *begin(st);
                    if (l <= x) {
                        ITree[node].del(l, r);
                        ll id = 1ll*(n+1)*l + r;
                        cache.erase(id);
                    }
                    else break;
                }
            }
            else {
                // Delete some suffix
                auto &st = ITree[node].by_r;
                while (!st.empty()) {
                    auto [r, l] = *rbegin(st);
                    if (r > x) {
                        ITree[node].del(l, r);
                        ll id = 1ll*(n+1)*l + r;
                        cache.erase(id);
                    }
                    else break;
                }
            }

            if (ITree[node].L+1 == ITree[node].R) return;
            if (x < ITree[node].M) self(self, 2*node+1, x);
            else self(self, 2*node+2, x);
        };

        constexpr array<ll, 3> unit = {0, 0, -1};
        SegTree<array<ll, 3>, unit> seg(n);
        for (int i = 0; i < n; ++i) seg.update(i, array<ll, 3>{a[i], a[i], i});
        
        auto solve = [&] (const auto &self, int L, int R) -> int {
            if (R-L <= 2) return -1;
            ll id = 1ll*L*(n+1) + R;
            if (cache.find(id) != cache.end()) return cache[id];
            
            auto [sm, mx, pivot] = seg.query(L, R);

            insert(insert, 0, L, R);
            if (mx < sm - mx) {
                return cache[id] = R-L;
            }
            else {
                int ret = self(self, L, pivot);
                ret = max(ret, self(self, pivot+1, R));
                return cache[id] = ret;
            }
        };

        while (q--) {
            int type; cin >> type;
            if (type == 1) {
                int l, r; cin >> l >> r;
                cout << solve(solve, l-1, r) << '\n';
            }
            else {
                ll pos, val; cin >> pos >> val; --pos;

                erase(erase, 0, pos);
                if (pos) erase(erase, 0, pos-1);
                if (pos+1 < n) erase(erase, 0, pos+1);
                seg.update(pos, array<ll, 3>{val, val, pos});
            }
        }
    }
}

Many testers have disappeared from the scoreboard because the current problem set is completely different from the initial one.

Let's handle each two lines separately. We greedily place kings in all the white squares in the first row. Then, we cannot place kings in the second row.

Overall, the answer is $$$\lfloor \frac{n+1}{2} \rfloor \cdot \lfloor \frac{m+1}{2} \rfloor$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        cout<<((n+1)/2)*((m+1)/2)<<"\n";
    }
}

First let's assign a number to each sector from $$$1$$$ to $$$n$$$ in clockwise order.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        if(n%2==0){
            if((n/2)%2==1) cout<<"-1\n";
            else{
                ll x=(n/2);
                cout<<(x*(x+1))/2-(n/4)<<"\n";
            }
        }
        else{
            ll x=(n-1)/2;
            cout<<(x*(x+1))/2<<"\n";
        }
    }
}

Root the tree at a node, say $$$1$$$. Now, calculate depths of all nodes from the root, and mark all nodes with even depth as $$$0$$$, and odd depth as $$$1$$$. Imagine we connect two nodes of the different parity. This would form a cycle of even length and so the diametrically opposite vertices on the cycle would violate the condition.

So, we are left with choices where we connect vertices of the same parity. This will always satisfy our conditions.

This is because precisely $$$1$$$ cycle is formed, with trees dangling to it. For 2 vertices on the cycle, there are never 2 shortest paths since total cycle length is odd. The trees hanging to the cycle trivially satisfy the condition.

Also since the path between two attached trees also goes through the cycle, it essentially reduces to shortest path between corresponding points on the cycle and is also unique.

So our answer is all pairs of nodes having the same parity. Complexity is $$$O(n)$$$.

#include<bits/stdc++.h>
#define pi 3.14159265358979323846
#define eb emplace_back
#define ll long long
#define w(t) while(t--)
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define iofast ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
//give sin(),cos() radian, and asin(),acos() gives you radian
vector<int> v[1000010];
bool ch[1000010];
ll cnt1,cnt0;
void DFS(int po,bool c){
	if(!c) cnt0++;
	else cnt1++;
	ch[po]=1;
	for(auto i:v[po]){
		if(!ch[i]){
			DFS(i,!c);
		}
	}
	return;
}
void solve(){
	int n,a,b;
	cnt1=0;
	cnt0=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		v[i].clear();
		ch[i]=0;
	}
	for(int i=1;i<n;i++){
		cin>>a>>b;
		v[a].eb(b);
		v[b].eb(a);
	}
	DFS(1,0);
	cout<<(((cnt1-1)*cnt1)/2)+(((cnt0-1)*cnt0)/2)<<'\n';
	return;
}
int main(){
	iofast
	int t;
	cin>>t;
	w(t) solve();
	return 0;
}

We can observe that the upper bound of the answer is $$$\frac{n(n+1)}{2}$$$(corresponding to $$$[0,1,...,n-1]$$$) and the lower bound is $$$n$$$(corresponding to $$$[n-1,n-2,...,1,0]$$$).

In fact, we construct the permutation for all $$$n \le S \le \frac{n(n+1)}{2}$$$. Note $$$x$$$ as the maximum number such that $$$x+(x+1)+(x+2)+...+n \ge S$$$, we have $$$S=y+(x+1)+(x+2)+...+n(y \le x)$$$.

• If $$$y \neq x$$$, we get $$$p=[1,...,y-1,y+1,...,0,y,x+1,x+2,...,n]$$$;

• Otherwise, we get $$$p=[1,2,...,...,x-1,0,x,x+1,x+2,...,n]$$$;

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n,k;
        cin>>n>>k;
        if(k<n || k>(n*(n+1))/2) cout<<"-1\n";
        else{
            if(k==n){
                for(ll i=1;i<n;i++) cout<<i<<" ";
                cout<<0<<"\n";
            }
            else if(k==(n*(n+1))/2){
                for(ll i=0;i<n;i++) cout<<i<<" ";
                cout<<"\n";
            }
            else{
                k-=n;
                vector<ll> ans(n);
                ll val=0,ind=0,ind1=0;
                for(ll i=0;i<n;i++) ans[i]=i;
                for(ll i=n-1;i>0;i--){
                    if(k>i) k-=i;
                    else{
                        swap(ans[i-1],ans[0]);
                        val=k;
                        ind=i;
                        break;
                    }
                }
                for(ll i=0;i<n;i++){
                    if(ans[i]==val){
                        ind1=i;
                        break;
                    }
                }
                swap(ans[ind],ans[ind1]);
                for(auto i:ans) cout<<i<<" ";
                cout<<"\n";
            }
        }
    }
}

Reimagine the integers in $$$a$$$ as binary integers. Since XOR operation is done before any addition, this means that we can count the contribution of each bit separately, because XOR operation can be done by doing the XOR operation for each bit, and addition can also be done in a similar way.

Let $$$s_k$$$ be the sum of costs from all $$$2^{n-1}$$$ possible expressions if we only consider the $$$k$$$-th bit from each integer as the elements. Then, the sum of costs is $$$\sum_{i=0}^{28} s_i \cdot 2^i$$$.

Let's try to count $$$s_0$$$. We will use dynamic programming to solve this. Let $$$dp_i$$$ be the sum of costs from all $$$2^{i-1}$$$ possible expressions if we only consider the $$$0$$$-th bit from each integer as the elements, and we only consider the first $$$i$$$ elements. Let the $$$0$$$-th bit of $$$a_i$$$ be $$$b_i$$$. Then, $$$dp_0 = 0$$$ and $$$dp_i = \sum_{x=0}^{i-1} (dp_x + (b_{x+1} \oplus b_{x+2} \oplus \dots \oplus b_i))$$$. Although doing this naively would result in $$$O(n^3)$$$ transition, we can optimize this to $$$O(n)$$$ using prefix sum.

Let $$$pdp_i = \sum_{x=0}^{i} dp_x$$$ and $$$pb_i = b_1 \oplus b_2 \oplus \dots \oplus b_i$$$. Then, $$$dp_i = pdp_{i-1} + \sum_{x=0}^{i-1} (pb_x \oplus pb_i)$$$. Notice that the second expression is still $$$O(n)$$$. So, to count it in $$$O(1)$$$, we just have to store two extra variables $$$c_{i,0}$$$ and $$$c_{i,1}$$$, where $$$c_{i,k}$$$ is the number of integers $$$x$$$ such that $$$1 \leq x \leq i$$$ and $$$pb_x = k$$$. If $$$pb_i = 0$$$, the second expression is equal to $$$c_{i,1}$$$. Otherwise, the second expression is equal to $$$c_{i,0}$$$.

Other values of $$$s_i$$$ can be counted in a similar way.

Time complexity: $$$O(n \log a_i)$$$

// #pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pob pop_back
const int MOD = 1e9 + 7;
const int MODD = 998244353;
const int MAXN = 5e5 + 2;
const ll BIGG = 2e18;
 
using namespace std;
 
int a[MAXN];
ll dp[MAXN], cnt[2], pref[MAXN];
 
void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    ll res = 0, comb;
    bool od;
    for (int i = 0; i < 29; i++) {
        od = true;
        cnt[0] = 0;
        cnt[1] = 1;
        comb = 1;
        if (a[0] % 2) {
            dp[0] = 1;
            pref[0] = 1;
            od = !od;
        }
        else {
            dp[0] = 0;
            pref[0] = 0;
        }
        a[0] >>= 1;
        cnt[od]++;
        for (int i = 1; i < n; i++) {
            comb = (comb * 2) % MODD;
            if (a[i] % 2) od = !od;
            a[i] >>= 1;
            dp[i] = (pref[i - 1] + cnt[!od]) % MODD;
            pref[i] = (pref[i - 1] + dp[i]) % MODD;
            cnt[od] = (cnt[od] + comb) % MODD;
        }
        res = (res + dp[n - 1] * (1 << i)) % MODD;
    }
    cout << res << endl;
}
 
int main(){
    // ios_base::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Case $$$1$$$:If both $$$a_i=1$$$ and $$$b_j=0$$$ exist, the answer is $$$0$$$.

Case $$$2$$$:If $$$a_i=1$$$ exist and $$$b_j=1$$$ for all $$$j$$$, the answer is $$$(2^n-1)^k$$$, where $$$k$$$ is the number of $$$i$$$ satisfying $$$a_i=0$$$;

Case $$$3$$$:If $$$b_j=0$$$ exist and $$$a_i=0$$$ for all $$$i$$$, it is similar to case $$$2$$$.

Case $$$4$$$:If $$$a_i=0$$$ and $$$b_j=1$$$ for all $$$i,j$$$, we need to exclude all invalid cases. That is, the caces that there is at least one row containing all $$$1's$$$, or there is at least one coloum containing all $$$0's$$$. Using the Inclusion-Exclusion Principle, we get the answer is $$$2^{n^2}-2\Sigma^{n}_{i=1}((-1)^{i} \cdot C(n,i)·2^{n^2-i·n})$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

ll mod=1e9+7;
 
long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}
 
long long modular_inverse(long long n){
  return power(n,mod-2);
}
 
#define MAXN 2000005
 
long long factorial[MAXN];
long long invfact[MAXN];
 
void cfact(){
  long long i;
  factorial[0]=1;
  factorial[1]=1;
  for(i=2;i<MAXN;i++){
    factorial[i]=factorial[i-1]*i;
    factorial[i]%=mod;
  }
  invfact[MAXN-1]=modular_inverse(factorial[MAXN-1]);
  for(i=MAXN-2;i>=0;i--){
    invfact[i]=invfact[i+1]*(i+1);
    invfact[i]%=mod;
  }
}
 
long long calcnCr(long long n,long long k){
  if(k<0 || n<k){return 0;}
  return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod;
}

int main(){
    fast;
    cfact();
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        string s1,s2;
        cin>>s1>>s2;
        ll cnt11=count(s1.begin(),s1.end(),'1');
        ll cnt20=count(s2.begin(),s2.end(),'0');
        if(cnt11>0 && cnt20>0) cout<<"0\n";
        else if(cnt11==0 && cnt20>0) cout<<power((power(2,n)-1)%mod,n-cnt20)%mod<<"\n";
        else if(cnt11>0 && cnt20==0) cout<<power((power(2,n)-1)%mod,n-cnt11)%mod<<"\n";
        else{
            ll res=0;
            for(ll i=0;i<n;i++){
                if(i%2==0){
                    res=(res-((calcnCr(n,i+1))*power(2,n*n-(i+1)*n))%mod+mod)%mod;
                }
                else{
                    res=(res+((calcnCr(n,i+1))*power(2,n*n-(i+1)*n))%mod)%mod;
                }
            }
            cout<<(power(2,n*n)+2*res)%mod<<"\n";
        }
    }
}

WLOG, assume that $$$x \geq y$$$. We desire for Alice to win. Let us check the scenarios where this is possible:

Case 1: $$$(x \geq 2y)$$$: This means Alice has to subtract a multiple of $$$y$$$ from $$$x$$$. There are, say $$$k$$$ choices of subtracting $$$y, 2y, .., ky$$$. We have more than $$$1$$$ choices $$$(k>1)$$$. If $$$ky$$$ is winning, Alice chooses that. If it is losing, then since $$$k>1$$$, Alice can choose $$$(k-1)y$$$ and Bob will then be forces to subtract $$$y$$$ in the next move, essentially making Bob choose the losing $$$ky$$$ state. So Alice always wins.

Case 2: $$$(x<2y)$$$: This means there is only one possible move, which is to subtract $$$y$$$ from $$$x$$$. If the resulting pair of numbers $$$(y,x-y)$$$ is losing, Alice wins. Else she loses.

Now, for her to loose, like in case 1, $$$(y \geq 2(x-y))$$$ (we already know $$$y$$$ is larger than $$$(x-y)$$$ since $$$x<2y$$$). So for her to win, $$$y \leq 2(x-y)$$$, which means $$$x \geq \frac{3y}{2}$$$.

If $$$y<2(x-y)$$$, we again subtract and go to the next iteration. The new pair is $$$(x-y,2y-x)$$$. For it the winning conditions come out to be $$$x \geq \frac{5y}{3}$$$.

If we keep doing the iterations, we observe that in the $$$n^{th}$$$ step the condition comes out to be $$$x \geq \frac{F(n+1)}{F(n)}$$$ where $$$F(n)$$$ is the $$$n^{th}$$$ Fibonacci number $$$(F(1)=1, F(2)=2)$$$. So, to get the exact bound, we take its limit as $$$n$$$ approaches infinity, and get $$$\lim_{n \to \infty} \frac{F(n+1)}{F(n)} = \frac{1+\sqrt{5}}{2} = \phi$$$. So Alice wins iff $$$(x> \phi y)$$$ (equality dropped since both $$$x$$$ and $$$y$$$ are integers).

So our problem becomes counting the number of $$$(l,r)$$$ such that $$$r> \phi l$$$. Since our numbers $$$\leq 10^9$$$, we can take an appropriate approximation of $$$\phi$$$, (say $$$\frac{p}{q}$$$).

For approximation you can use the fibonacci numbers just bigger than $$$10^9$$$. They match $$$\phi$$$ upto $$$14$$$ decimal places and works fine for our purpose.

Now our problem boils down to calculating $$$\sum_{x=L'}^{R} \lfloor \frac{xq}{p} \rfloor$$$ (here $$$L'$$$ is the first index such that $$$\lfloor \frac{L'q}{p} \rfloor \geq L $$$).

This is a standard problem and can be calculated in $$$O(log(max(p,q))$$$ complexity. Here is reference a blog with exact details about solving this: https://www.cnblogs.com/apjifengc/p/17492207.html

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;

const ll P = 1e18;
const ld phi=1.61803398874989;
const ll a=1134903170, b=0, c=1836311903;

//code for euclidean algo from blog mentioned in the editorial

struct Node {
    ll x, y, sumx, sumy;
    Node() : x(0), y(0), sumx(0), sumy(0) {}
    Node operator*(Node b) {
        Node a = *this, c;
        c.x = (a.x + b.x) % P;
        c.y = (a.y + b.y) % P;
        c.sumx = (a.sumx + b.sumx + a.x * b.x) % P;
        c.sumy = (a.sumy + b.sumy + a.y * b.x) % P;
        return c;
    }
};
Node pow(Node a, ll b) {
    Node ans;
    while (b) {
        if (b & 1ll) ans = ans * a;
        a = a * a;
        b >>= 1ll;
    }
    return ans;
}
Node euclid(ll p, ll q, ll r, ll n, Node U, Node R) {
    if (!n) return Node();
    if (r >= q) return pow(U, r / q) * euclid(p, q, r % q, n, U, R);
    if (p >= q) return euclid(p % q, q, r, n, U, pow(U, p / q) * R);
    ll m = (1ll * p * n + r) / q;
    if (!m) return pow(R, n);
    return pow(R, (q - r - 1) / p) * U * euclid(q, p, (q - r - 1) % p, m - 1, R, U) * pow(R, n - (q * m - r - 1) / p);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    Node U, R;
    U.y = 1, R.x = 1, R.sumx = 1;
    int t;cin>>t;while (t--){
    ll l, r;cin>>l>>r;
    ll sp=ceil(phi*l);
    ll fa=(r-l+1)%P;
    if (sp<=r){
    ll ne=r-sp+1;
    fa=(fa-((ne*(l-1))%P)+4*P)%P;
    auto ans_r = euclid(a, c, b, r, U, R);
        ans_r.sumy = (ans_r.sumy + (b / c)) % P;
        auto ans_sp = euclid(a, c, b, sp-1, U, R);
        ans_sp.sumy = (ans_sp.sumy + (b / c)) % P;
        fa=(fa+ans_r.sumy-ans_sp.sumy+5*P)%P;
    }
    cout<<fa<<endl;
    }
    return 0;
}

TheForces is a project uniting individuals with a shared interest in competitive programming contests. You can join our discord server with more than $$$2200$$$ members to communicate with founders and members of TheForces.

In the other words TheForces rounds are series of educational contests for beginners to masters which are created by a group of CP lovers in the CF community, It's where anyone can propose and prepare his own interesting problems and receive money!

Not to mention that we've already created two official codeforces div(1 + 2) rounds before ;) so join us now!

Discord link

TheForces website

The optimal way to hit $$$ n $$$ runs in minimum balls is to hit $$$ 6 $$$ runs on every ball until you reach $$$ n $$$ runs.
The optimal way to hit $$$ n $$$ runs in maximum balls is to hit $$$ 4 $$$ runs on every ball until you reach $$$ n $$$ runs.
Time Complexity: $$$ O(1) $$$.

Your code here...
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        cout<<((n+5)/6)<<" "<<((n+3)/4)<<"\n";
    }
}

From the definition of the Good string it clearly seems that string must contain either all 0’s or 1’s.

So all 0’s are converted into 1’s in the following ways:

1. Using Operation 1 by using $$$ a $$$ coins per operation.

2. Using Operation 2 by using $$$ b $$$ coins per operation by using any extra '1' in the string.

All 1’s are converted into 0’s in the following ways:

1. Using Operation 1 by using $$$ a $$$ coins per operation.

2. Using Operation 2 for pair of 1’s using $$$ b $$$ coins per operation. If there is single '1' left this can be converted to '0' by either using $$$ a $$$ coins or $$$ 2b $$$ coins.

The minimum coins will get in one of the above scenarios. Time Complexity: $$$ O(n) $$$.

Your code here...
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n,a,b;
        cin>>n>>a>>b;
        string s;
        cin>>s;
        int cnt0=count(s.begin(),s.end(),'0');
        int cnt1=n-cnt0;
        int ans1=a*cnt0;
        int ans2=b*cnt0;
        int ans3=a*cnt1;
        int ans4=((cnt1/2)*b+(cnt1%2)*(min(a,2*b)));
        cout<<min({ans1,ans2,ans3,ans4})<<"\n";
    }
}

The lower bound of $$$ F(p) $$$ will be $$$ \log_2(n) + 1 $$$.

Mathematically, Let's consider $$$ \sum \frac{p_i}{i} \geq \log_2(n) + 1 $$$ (ans).

Let $$$ 2^x \leq n \leq 2^{x+1} $$$, $$$ m = 2^{x+1} $$$.

Array $$$ b = p $$$. $$$ \left\lfloor \frac{p_m}{m} \right\rfloor \geq \left\lfloor \frac{2^{x+1}}{m} \right\rfloor = \left\lfloor \frac{(2^x+2^x)}{m} \right\rfloor \geq \left\lfloor \frac{(b_m+m)}{m} \right\rfloor $$$.

So $$$ \sum \frac{p_i}{i} \geq \sum \frac{(b_i+i)}{i} = \sum \frac{(p_i+i)}{i} = \sum \frac{p_i}{i} + 1 \geq \text{ans} + 1 $$$.

Hence showed that lower bound will be limited to $$$ \log_2(n) + 1 $$$.

So construct the permutation accordingly.

Time Complexity: $$$ O(n+\log n) $$$.

Your code here...
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int> a(n+1);
        for(int i=1;i<=n;i++) a[i]=i-1;
        int p=n;
        while(p!=0){
            int x=p/2;
            x++;
            swap(a[x],p);
        }
        for(int i=1;i<=n;i++) cout<<a[i]<<" ";
        cout<<endl;
    }
}

From the given queries we only know the information about number of zeroes and ones in the hidden string but how we can get to know the positions of ‘01’ and ‘10’ (Binary Search it!)

Just know the first character by asking queries like 000…n times and 1000…(n-1) times.

Later do the binary search to know the first occurrence of the character other than first character, similarly, do the binary search for another substring position.

Total queries used are $$$ 2\log(n) + 2 < 40 $$$.

Time Complexity: $$$ O(n\log n) $$$.

Your code here...
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    //t=1;
    while(t--){
        int n;
        cin>>n;
        string s="";
        for(int i=0;i<n;i++) s+='0';
        int cnt0,cnt1;
        cout<<"? "<<s<<endl;
        cin>>cnt0;
        cnt1=n-cnt0;
        if(cnt0==n || cnt0==0) cout<<"! -1 -1"<<endl;
        else{
            int pos1=-1,pos2=-1;
            s[0]='1';
            int x;
            cout<<"? "<<s<<endl;
            cin>>x;
            if(x<cnt0){
                pos1=0;
                int l=pos1,r=n-1;
                while(l<=r){
                    int m=(l+r)/2;
                    string s1="";
                    for(int i=0;i<=m;i++) s1+='1';
                    for(int i=m+1;i<n;i++) s1+='0';
                    cout<<"? "<<s1<<endl;
                    cin>>x;
                    if(x==(cnt0-(m+1))){
                        pos1=m;
                        l=m+1;
                    }
                    else r=m-1;
                }
                if((pos1+1)==cnt0) cout<<"! "<<pos1+1<<" "<<"-1"<<endl;
                else{
                    pos2=pos1+1;
                    l=pos2,r=n-1;
                    while(l<=r){
                        int m=(l+r)/2;
                        string s1="";
                        for(int i=0;i<=m;i++) s1+='1';
                        for(int i=m+1;i<n;i++) s1+='0';
                        cout<<"? "<<s1<<endl;
                        cin>>x;
                        x+=pos1+1;
                        if(x==(cnt0+(m-pos1))){
                            pos2=m;
                            l=m+1;
                        }
                        else r=m-1;
                    }
                    cout<<"! "<<pos1+1<<" "<<pos2+1<<endl;
                }
            }
            else{
                pos2=0;
                int l=pos2,r=n-1;
                while(l<=r){
                    int m=(l+r)/2;
                    string s1="";
                    for(int i=0;i<=m;i++) s1+='1';
                    for(int i=m+1;i<n;i++) s1+='0';
                    cout<<"? "<<s1<<endl;
                    cin>>x;
                    if(x==(cnt0+(m+1))){
                        pos2=m;
                        l=m+1;
                    }
                    else r=m-1;
                }
                if((pos2+1)==cnt1) cout<<"! -1"<<" "<<pos2+1<<endl;
                else{
                    pos1=pos2+1;
                    l=pos1,r=n-1;
                    while(l<=r){
                        int m=(l+r)/2;
                        string s1="";
                        for(int i=0;i<=m;i++) s1+='1';
                        for(int i=m+1;i<n;i++) s1+='0';
                        cout<<"? "<<s1<<endl;
                        cin>>x;
                        x-=(pos2+1);
                        if(x==(cnt0-(m-pos2))){
                            pos1=m;
                            l=m+1;
                        }
                        else r=m-1;
                    }
                    cout<<"! "<<pos1+1<<" "<<pos2+1<<endl;
                }
            }
        }
    }
}

In this problem we need to find the highest ancestor of the node which is empty.

We can do Binary Lifting, HLD etc., Time limit given to get accept any solution.

Time Complexity: $$$O(nlogn)$$$ (Binary Lifting)

Time Complexity: $$$O(nlog^2 n)$$$ (HLD)

Your code here...
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int n,m;
vector<vector<int>> adj;
vector<int> H,pH,tree,pos,horder,sz,par;

int getsum(int qs, int qe, int ss, int se, int si){
    if(se<qs || ss>qe) return 0;
    if(qs<=ss && qe>=se) return tree[si];
    int mid=(ss+se)/2;
    int v1=getsum(qs,qe,ss,mid,2*si+1);
    int v2=getsum(qs,qe,mid+1,se,2*si+2);
    return v1+v2;
}
 
void update(int ss, int se, int i, int si, int diff){
    if(i<ss || i>se) return;
    tree[si]=tree[si]+diff;
    if(se>ss){
        int mid=(ss+se)/2;
        update(ss,mid,i,2*si+1,diff);
        update(mid+1,se,i,2*si+2,diff);
    }
}

void dfs(int x, int p){
    sz[x]=1;
    par[x]=p;
    int pp=-1,maxi=0;
    for(auto i:adj[x]){
        if(i!=p){
            dfs(i,x);
            sz[x]+=sz[i];
            if(sz[i]>maxi){
                maxi=sz[i];
                pp=i;
            }
        }
    }
    if(pp!=-1){
        H[pp]=x;
    }
}

void dfs1(int x, int p){
    if(H[x]==p) pH[x]=pH[p];
    for(auto i:adj[x]){
        if(i!=p){
            dfs1(i,x);
        }
    }
}

void dfs2(int x, int p){
    horder.push_back(x);
    for(auto i:adj[x]){
        if(i!=p){
            if(H[i]==x) dfs2(i,x);
        }
    }
    for(auto i:adj[x]){
        if(i!=p){
            if(H[i]!=x) dfs2(i,x);
        }
    }
}
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        adj.clear();
        adj.resize(n);
        for(int i=0;i<n-1;i++){
            int u,v;
            cin>>u>>v;
            u--;
            v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        H.clear();
        H.resize(n);
        for(int i=0;i<n;i++) H[i]=i;
        pH.clear();
        pH.resize(n);
        for(int i=0;i<n;i++) pH[i]=i;
        tree.clear();
        tree.resize(4*n,0);
        pos.clear();
        pos.resize(n);
        sz.clear();
        sz.resize(n);
        par.clear();
        par.resize(n);
        horder.clear();
        dfs(0,-1);
        dfs1(0,-1);
        dfs2(0,-1);
        for(int i=0;i<n;i++) pos[horder[i]]=i;
        while(m--){
            int x;
            cin>>x;
            x--;
            if(getsum(pos[x],pos[x],0,n-1,0)==1) cout<<"-1 ";
            else{
                int prev=x;
                while(pH[x]!=0 && getsum(pos[pH[x]],pos[x],0,n-1,0)==0){
                    prev=pH[x];
                    x=par[pH[x]];
                }
                int l=pos[pH[x]],r=pos[x],ans=prev;
                while(l<=r){
                    int mid=(l+r)/2;
                    if(getsum(mid,pos[x],0,n-1,0)==0){
                        ans=horder[mid];
                        r=mid-1;
                    }
                    else l=mid+1;
                }
                cout<<ans+1<<" ";
                update(0,n-1,pos[ans],0,1);
            }
        }
        cout<<"\n";
    }
}

The Naveen’s array elements are the integers which has even number of set bits.

The Pavan Kalyan’s array elements are the integers which has odd number of set bits.

You can get it in OEIS but mentioned in statement for fun activity.

Now you need to find the number of simple of paths whose Bitwise Xor has even set bits and odd set bits. For that, Fix a root of the tree and create an array whose elements indicates ‘1’ if there are odd set bits in the bitwise Xor of the path between the root and that particular node and ‘0’ for vice-versa.

Let u→v path bitwise Xor has even set bits and v→w path bitwise Xor has even set bits the u→w path bitwise Xor has even set bits.

Proof: u→w path bitwise Xor bits= number of bits in u→v + number of bits in v→w – 2*(number of common bits in u→v and v→w).

it is even+even-even which is even.

From the above fact we can find the answer to queries easily.

Time Complexity: $$$O(n+q \cdot log(10^9))$$$.

Your code here...
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

const ll N=2e6+10;
ll n;
vector<vector<pair<ll,ll>>> adj;
vector<ll> X;
vector<bool> vis;

void bfs(ll s){
    vis[s]=true;
    X[s]=0;
    queue<ll> q;
    q.push(s);
    while(q.size()>0){
        ll u=q.front();
        q.pop();
        for(auto v:adj[u]){
            if(!vis[v.first]){
                vis[v.first]=true;
                X[v.first]=v.second^X[u];
                q.push(v.first);
            }
        }
    }
}
 
int main(){
    fast;
    ll t;
    t=1;
    while(t--){
        ll q;
        cin>>n>>q;
        adj.clear();
        adj.resize(n);
        for(ll i=0;i<n-1;i++){
            ll u,v,w;
            cin>>u>>v>>w;
            u--;
            v--;
            adj[u].push_back({v,w});
            adj[v].push_back({u,w});
        }
        X.clear();
        X.resize(N,0);
        vis.clear();
        vis.resize(N,false);
        bfs(0);
        ll cnt0=0,cnt1=0;
        for(ll i=0;i<n;i++){
            if((__builtin_popcount(X[i]))%2) cnt1++;
            else cnt0++;
        }
        while(q--){
            ll q1;
            cin>>q1;
            if(q1==1){
                ll u,v,w;
                cin>>u>>v>>w;
                u--;
                v--;
                if(vis[v]) swap(u,v);
                vis[v]=true;
                X[v]=X[u]^w;
                if((__builtin_popcount(X[v]))%2) cnt1++;
                else cnt0++;
            }
            else{
                ll c;
                cin>>c;
                if(c==0) cout<<(cnt1*(cnt1-1))+(cnt0*(cnt0-1))<<endl;
                else cout<<(2*cnt0*cnt1)<<endl;
            }
        }
    }
}

Observe that the given tree is similar to undirected tree but instead of single edge there are two directed edges with facing opposite directions.

First, let’s get the upper bound of the ans. For each tree edge let cnt be the number of times we pass through this edge. Since there are only two directions for this edge, ans will increase from this edge is at most min(cnt, 2). Thus, the upper bound of the ans is sum of min(cnt, 2) over all edges.

For the constructive part, Take two paths that involve u. Suppose that they are (u,v) and (u,w). Let (u,in) be the intersection of these two paths. Now, we add a restriction: if we choose v → u we must choose u → w, and if we choose u→ v we must choose w → u. With this restriction, we can ensure that the edges between u and in are covered in both directions, and in the future we can ignore those edges. Thus, v→ u and u→w is equivalent to v→w, and u→v and w → u is equivalent to w→ v. Now we can remove two paths (u,v) and (u,w) and add (v,w) instead. Repeat this process for every edge to get the optimal selection.

Time Complexity: $$$O(nm+n^2)$$$.

Your code here...
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

const int N=10010;
int n,m;
vector<vector<int>> adj;
vector<int> path,vec;
vector<vector<pair<int,int>>> adj1;
vector<pair<int,int>> res1;
vector<bool> vis;

void dfs(int x, int p, int ff){
    vec.push_back(x);
    if(x==ff){
        path=vec;
    }
    for(auto i:adj[x]){
        if(i!=p){
            dfs(i,x,ff);
        }
    }
    vec.pop_back();
}

void dfs1(int x){
    while((int)adj1[x].size()>0){
        auto it=adj1[x].back();
        adj1[x].pop_back();
        if(!vis[it.second]){
            vis[it.second]=true;
            dfs1(it.first);
            res1[it.second]={it.first,x};
        }
    }
}
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        adj.clear();
        adj.resize(n);
        for(int i=0;i<n-1;i++){
            int u,v;
            cin>>u>>v;
            u--;
            v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        vector<pair<int,int>> res(m);
        for(int i=0;i<m;i++){
            cin>>res[i].first>>res[i].second;
        }
        adj1.clear();
        adj1.resize(n+1);
        int ans=0;
        map<pair<int,int>,int> mp;
        for(int i=0;i<m;i++){
            adj1[res[i].first].push_back({res[i].second,i+1});
            adj1[res[i].second].push_back({res[i].first,i+1});
            vec.clear();
            path.clear();
            dfs(res[i].first-1,-1,res[i].second-1);
            for(int j=0;j<(int)path.size()-1;j++){
                int u=path[j],v=path[j+1];
                if(u>v) swap(u,v);
                mp[{u,v}]++;
            }
        }
        int cnt=m+1;
        for(int i=0;i<n;i++){
            for(auto j:adj[i]){
                if(j<i && mp[{j,i}]>0){
                    ans+=min(2,mp[{j,i}]);
                    if(mp[{j,i}]%2){
                        adj1[i+1].push_back({j+1,cnt});
                        adj1[j+1].push_back({i+1,cnt});
                        cnt++;
                    }
                }
            }
        }
        res1.clear();
        res1.resize(N);
        vis.clear();
        vis.resize(N,false);
        for(int i=1;i<=n;i++) dfs1(i);
        cout<<ans<<"\n";
        for(int i=1;i<=m;i++){
            if(res1[i].first==res[i-1].first) cout<<"1 ";
            else cout<<"2 ";
        }
        cout<<"\n";
    }
}

TheForces is a project uniting individuals with a shared interest in competitive programming contests. You can join our discord server with more than $$$2200$$$ members to communicate with founders and members of TheForces.

In the other words TheForces rounds are series of educational contests for beginners to masters which are created by a group of CP lovers in the CF community, It's where anyone can propose and prepare his own interesting problems and receive money!

Not to mention that we've already created two official codeforces div(1 + 2) rounds before ;) so join us now!

Discord link

TheForces website

If $$$m=4$$$ and $$$d=1$$$ output "YES". Otherwise, output "NO".

Output top $$$8$$$ in TheForce rating.

let's give look at $$$A$$$ and $$$B$$$ starting from max of most signinficant bit between $$$A$$$ and $$$B$$$.

$$$A = 18, B = 13$$$

So, at the $$$i-th$$$ bit of $$$A$$$ and $$$B$$$, $$$A_i \oplus B_i$$$ must equal to $$$1$$$ where $$$(0 \leq i \leq \max(msb(A), msb(B)))$$$

So, $$$A \oplus B = 11111$$$

So, if $$$A \oplus B=2^{\max(msb(A), msb(B)) + 1}-1$$$ output "YES". Otherwise, output "NO".

def msb(n):
    return n.bit_length() - 1

t = int(input())

for _ in range(t):
    a, b = list(map(int, input().split()))
    _msb = max(msb(a), msb(b))
    if( (a ^ b) == 2**(_msb + 1) - 1 and a != b):
        print("YES")
    else:
        print("NO")

Output the memory limit of the $$$i$$$-th problem.

Print the number of a blog with at least 1000 downvote (there are currently 8 blogs in total). the value of n actually represents the order of date, not the order from most downvoted blogs.

Google "apple codeforce" to get the link: https://mirror.codeforces.com/problemset/problem/1843/D

#include <bits/stdc++.h>
using namespace std;


int main() {

    #ifdef ABHISHEK_SRIVASTAVA
        freopen("Input.txt", "r", stdin);
        freopen("Output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n, k, curr = 1, cost = 0;
        cin >> n >> k;
        bool change = 0;
        while (k > 0) {
            k--;
            cost += curr;
            if (change)
                curr++;
            change = 1 - change;            
        }
        cout << cost << '\n';
    }

    return 0;

}

• For $$$k=0$$$, we don't color any cell;

• For $$$k=1$$$, we color cell $$$(1,1)$$$;

• For $$$k=2$$$, we color cells $$$(1,1),(n,n)$$$;

• For $$$k=3$$$, we color cells $$$(1,1),(n,n),(1,2),(2,1)$$$;

• For $$$k=4$$$, we color cells $$$(1,1),(n,n),(1,2),(2,1),(n-1,n),(n,n-1)$$$;

• $$$\ldots$$$

#include<bits/stdc++.h>
#define eb emplace_back
#define ll long long
#define w(t) while(t--)
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define iofast ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
vector<int> v[200010];
int a[200010]; 
void solve(){
	int n,m,po=-1,ans=1,b;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>a[i];
		v[a[i]].clear();
	}
	for(int i=0;i<m;i++){
		cin>>b;
		v[b].eb(i);
	}
	for(int i=0;i<n;i++){
		if(!v[a[i]].size()){
			cout<<"-1\n";
			return;
		}
		int p=upper_bound(v[a[i]].begin(),v[a[i]].end(),po)-v[a[i]].begin();
		if(p==v[a[i]].size()){
			po=v[a[i]][0];
			ans++;
		}
		else po=v[a[i]][p];
	}
	cout<<ans<<'\n';
	return;
}
int main(){
	iofast
	int t;
	cin>>t;
	w(t) solve();
	return 0;
}

We use vectors $$$pos_i$$$ to represent all positions (in increasing order) of elements with value $$$i$$$ in array $$$b$$$.

Let's start from $$$a_1$$$. We can greedily choose the smallest $$$p$$$ such that $$$b_p = a_1$$$, and match $$$a_1$$$ with $$$b_p$$$.

Assume we have matched $$$a_{1,2, \dots ,i}$$$, and $$$p$$$ satisfies $$$a_i = b_p$$$.

Next, we want to match $$$a_{i+1}$$$. Again, we can greedily choose $$$pos_{a_{i+1}}.\text{upper_bound}(p)$$$. If there is no such $$$p$$$, then $$$ans++$$$, and $$$p = pos_{a_{i+1}}.\text{head()}$$$.

The case with no solution can be easily determined using the above method.

#include<bits/stdc++.h>
#define pi 3.14159265358979323846
#define eb emplace_back
#define ll long long
#define w(t) while(t--)
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define iofast ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
const int mod=998244353;
//give sin(),cos() radian, and asin(),acos() gives you radian
void solve(){
	ll n,ans=1,sum,p;
	cin>>n;
	if(n%2){
		sum=8;
		p=3;
	}
	else{
		sum=4;
		p=2;
	}
	for(ll i=n/2;i>0;i--){
		ans*=sum;
		ans%=mod;
		sum--;
		ans*=sum;
		ans%=mod;
		sum--;
		sum+=((2*p)+2)*2;
		sum%=mod;
		p+=2;
	}
	cout<<ans<<'\n';
	return;
}
int main(){
	iofast
	int t;
	cin>>t;
	w(t) solve();
	return 0;
}

Consider $$$m = 1, 2, \ldots, \left\lfloor \frac{n}{2} \right\rfloor$$$(Here area $$$(x_1,y_1)$$$ to $$$(x_2,y_2)$$$ refers to the rectangular region with ($$$x_1$$$,$$$y_1$$$) as the top-left corner and ($$$x_2$$$,$$$y_2$$$) as the bottom-right corner ).

• $$$1$$$ can be put anywhere;

• $$$2$$$ can be covered by at most $$$4$$$ submatrices. To achieve the maximum, it can only be put in area $$$(2,2)$$$ to $$$(n-1,n-1)$$$;

• $$$3$$$ can be covered by at most $$$9$$$ submatrices. To achieve the maximum, it can only be put in area $$$(3,3)$$$ to $$$(n-2,n-2)$$$;

• $$$\ldots$$$

Consider $$$m = n, n-1, \ldots, \left\lfloor \frac{n}{2} \right\rfloor + 1$$$.

• $$$n$$$ can be put anywhere;

• Consider $$$(n-1)$$$. The intersection of all $$$(n-1) \times (n-1)$$$ submatrices is in area $$$(2,2)$$$ to $$$(n-1,n-1)$$$ so it can only be put in area $$$(2,2)$$$ to $$$(n-1,n-1)$$$;

• $$$(n-2)$$$ can only be put in area $$$(3,3)$$$ to $$$(n-2,n-2)$$$;

• $$$\ldots$$$

Afterward, the problem transforms into a classic counting problem. We start placing numbers within a central $$$k \times k$$$ matrix (if $$$n$$$ is odd, $$$k=1$$$; otherwise $$$k=2$$$); subsequently, numbers are placed within a $$$(k+2) \times (k+2)$$$ matrix centered around the previous one, and so on.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
vector<vector<ll>> adj,vv;
vector<ll> a,comp;

void dfs(ll x, ll p, ll val){
    for(auto i:adj[x]){
        if(i!=p){
            dfs(i,x,val);
            if(a[i]==a[x] && a[i]==val && comp[i]!=comp[x]){
                ll xxx=comp[i];
                for(auto j:vv[comp[i]]){
                    vv[comp[x]].push_back(j);
                    comp[j]=comp[x];
                }
                vv[xxx].clear();
                for(auto j:vv[comp[x]]){
                    a[j]=2*a[j];
                }
            }
        }
    }
}
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        a.clear();
        a.resize(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        ll mini=*min_element(a.begin(),a.end());
        bool ok=true;
        for(ll i=0;i<n;i++){
            if(a[i]%mini!=0) ok=false;
            a[i]=a[i]/mini;
        }
        adj.clear();
        adj.resize(n);
        for(ll i=0;i<n-1;i++){
            ll u,v;
            cin>>u>>v;
            u--;
            v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        if(!ok) cout<<"NO\n";
        else{
            comp.clear();
            comp.resize(n);
            for(ll i=0;i<n;i++) comp[i]=i;
            vv.clear();
            vv.resize(n);
            for(ll i=0;i<n;i++) vv[i].push_back(i);
            ll i=1;
            while(i<=1e9){
                dfs(0,-1,i);
                i=i*2;
            }
            ll cnt=count(a.begin(),a.end(),a[0]);
            if(cnt==n) cout<<"YES\n";
            else cout<<"NO\n";
        }
    }
}

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <unordered_map>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=200010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;
int a[N],fa[N];
ll sum[N];
vector<int>  v;
vector<int>  G[N];
unordered_map<int,int> del[N];

void DFS(int x,int pr)
{
	v.push_back(x); 
	fa[x]=pr;
	sum[x]=a[x];
	for(int i=0;i<G[x].size();i++)
	{
		int y=G[x][i];
		if(y==pr||del[x][y]) continue;
		DFS(y,x);
		sum[x]+=sum[y];
	}
}

int split(int x)
{
	v.clear();
	DFS(x,0);
	int y=0;
	if(v.size()==1) return 1;
	for(int i=0;i<v.size();i++) if(2*sum[v[i]]==sum[x]) y=v[i];
	if(y)
	{
		del[y][fa[y]]=del[fa[y]][y]=1;
		return 1;
	}
	else return 0;
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++) G[i].clear(),del[i].clear();		
		for(int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		int flg=1;
		for(int i=1;i<LOGN;i++){
			for(int j=1;j<=n;j++){
			    flg&=split(j);
			    if(!flg) break;
			}
		}
		printf("%s\n",flg?"YES":"NO");
	}
	
	return 0;
}

By observation, we can see that all values are in the form of $$$x \cdot 2^k$$$ (if not, then there is definitely no solution). For convenience, we convert all values to the form of $$$2^k$$$.

We consider each $$$k$$$ from small to large. We arbitrarily choose a root node for DFS. For a fixed $$$k$$$, if a node $$$x$$$ has a value of $$$2^k$$$ and it has the maximum depth, $$$x$$$ can only merge with its parent, otherwise there is definitely no solution. We only need to bruteforce merge $$$x$$$ with its parent.

What is the complexity?

Consider each edge. If an edge is involved in the merge process, the value of one endpoint of the edge will double. So, one edge can be merged up to $$$2\log n$$$ times.

The total time complexity is $$$O(n \log n)$$$.

Use reverse thinking.

Let's denote the sum of all node values as $$$sum$$$. The last step of merging must be to merge two nodes with values of $$$\frac{sum}{2}$$$.

This implies that there must be a subtree in the original tree with a sum of $$$\frac{sum}{2}$$$, regardless of which node we choose as the root.

We choose any node as the root and find the node $$$x$$$ with a subtree sum of $$$\frac{sum}{2}$$$. We then remove the edge between $$$x$$$ and its parent.

For the subtrees obtained after splitting, we recursively solve the problem on these subtrees, until there's no edges in this graph.

The total time complexity is $$$O(n \log n)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n,q;
ll   ans;
char s[N];
int  S[N];
set<int> ST[N];

//---------------------------------------------------------- 
//Segtree 1 

struct nod
{
	int l,r,mn;
	nod *lc,*rc;
};

struct Segtree
{
	nod *root;
	
	Segtree() {}
	
	void init()
	{
		build(&root,0,n,S);
	}
	
	void newnod(nod **p,int l,int r)
	{
		*p=new nod;
		(*p)->l=l;(*p)->r=r;(*p)->mn=0;
		(*p)->lc=(*p)->rc=NULL;
	}

	void build(nod **p,int L,int R,int x[])
	{
		newnod(p,L,R);
		if(L==R)
		{
			(*p)->mn=x[L];
			return ;
		}
		int M=(L+R)>>1;
		build(&(*p)->lc,L,M,x);
		build(&(*p)->rc,M+1,R,x);
		(*p)->mn=min((*p)->lc->mn,(*p)->rc->mn);
	}
	
	void add(int x,int v)
	{
		_add(root,x,v);
	}
	
	void _add(nod *p,int x,int v)
	{
		if(p->l==p->r)
		{
			p->mn+=v;
			return ;
		}
		int M=(p->l+p->r)>>1;
		if(x<=M)     _add(p->lc,x,v);
		else 		 _add(p->rc,x,v);
		p->mn=min(p->lc->mn,p->rc->mn);
	}
	
	int querymn(int L,int R)
	{
		return _querymn(root,L,R);
	}
	
	int _querymn(nod *p,int L,int R)
	{
		if(p->l==L&&p->r==R) return p->mn;
		int M=(p->l+p->r)>>1;
		if(R<=M)     return _querymn(p->lc,L,R);
		else if(L>M) return _querymn(p->rc,L,R);
		else return min(_querymn(p->lc,L,M),_querymn(p->rc,M+1,R));
	}
}TR;

//---------------------------------------------------------- 

//---------------------------------------------------------- 
//Segtree 2

struct Dnod
{
	int l,r,sum;
	Dnod *lc,*rc;
};

struct Dynamic_Segtree
{
	Dnod *root;
	
 	Dynamic_Segtree() 
	{
		root=NULL;
	}
	
	void newnod(Dnod **p,int l,int r)
	{
		*p=new Dnod;
		(*p)->l=l;(*p)->r=r;(*p)->sum=0;
		(*p)->lc=(*p)->rc=NULL;
	}

	void add(int p,int v)
	{
		_add(&root,0,n,p,v);
	}
	
	void _add(Dnod **p,int L,int R,int pos,int val)
	{
		if(*p==NULL) newnod(p,L,R);
		if(L==R)
		{
			(*p)->sum+=val;
			return ;
		}
		int M=(L+R)>>1;
		if(pos<=M) _add(&(*p)->lc,L,M,pos,val);
		else       _add(&(*p)->rc,M+1,R,pos,val);
		(*p)->sum=0;
		if((*p)->lc!=NULL) (*p)->sum+=(*p)->lc->sum;
		if((*p)->rc!=NULL) (*p)->sum+=(*p)->rc->sum;
	}
	
	int getsum(int L,int R)
	{
		return _getsum(root,L,R);
	}
	
	int _getsum(Dnod *p,int L,int R)
	{
		if(p==NULL) return 0;
		if(p->l==L&&p->r==R) return p->sum;
		int M=(p->l+p->r)>>1;
		if(R<=M)     return _getsum(p->lc,L,R);
		else if(L>M) return _getsum(p->rc,L,R);
		else return _getsum(p->lc,L,M)+_getsum(p->rc,M+1,R);
	}
}DT[N];

//---------------------------------------------------------- 

int LBS(int pos,int val)
{
	int L=-1,R=pos,M;
	while(L+1!=R)
	{
		M=(L+R)>>1;
		if(TR.querymn(M,pos)<val) L=M;
		else R=M;
	}
	return R;
}

int RBS(int pos,int val)
{
	int L=pos,R=n+1,M;
	while(L+1!=R)
	{
		M=(L+R)>>1;
		if(TR.querymn(pos,M)<val) R=M;
		else L=M;
	}
	return L;
}

int countk(int l,int r,int k)
{
	return DT[k+n].getsum(l,r);
}

int main()
{
	scanf("%d%d%s",&n,&q,s);
	for(int i=1;i<=n;i++) S[i]=S[i-1]+(s[i-1]=='('?1:-1);
	TR.init();
	for(int i=0;i<=n;i++) DT[S[i]+n].add(i,1);
	for(int i=1;i<=n;i++)
		ans+=countk(LBS(i,S[i]),i,S[i])-1;
	for(int i=1;i<=q;i++)
	{
		int p;
		scanf("%d",&p);
		if(s[p-1]==s[p]) 
		{
			printf("%I64d%c",ans,i==q?'\n':' ');
			continue;
		}
		swap(s[p-1],s[p]);
		if(s[p]==')')	
		{
			int l=LBS(p,S[p]),r=RBS(p,S[p]),L=countk(l,p,S[p])-1,R=countk(p,r,S[p])-1;
			ans-=(L+R);
			DT[S[p]+n].add(p,-1);
			S[p]+=2;
			TR.add(p,2);
			DT[S[p]+n].add(p,1);
			l=LBS(p,S[p]),r=RBS(p,S[p]),L=countk(l,p,S[p])-1,R=countk(p,r,S[p])-1;
			ans+=(ll)L*R;
			l=LBS(p,S[p]-1),r=RBS(p,S[p]-1),L=countk(l,p,S[p]-1),R=countk(p,r,S[p]-1);
			ans+=(ll)L*R;
		}
		else
		{
			int l=LBS(p,S[p]),r=RBS(p,S[p]),L=countk(l,p,S[p])-1,R=countk(p,r,S[p])-1;
			ans-=(ll)L*R;
			l=LBS(p,S[p]-1),r=RBS(p,S[p]-1),L=countk(l,p,S[p]-1),R=countk(p,r,S[p]-1);
			ans-=(ll)L*R;
			DT[S[p]+n].add(p,-1);
			S[p]-=2;
			TR.add(p,-2);
			DT[S[p]+n].add(p,1);
			l=LBS(p,S[p]),r=RBS(p,S[p]),L=countk(l,p,S[p])-1,R=countk(p,r,S[p])-1;
			ans+=(L+R);
		}
		printf("%I64d%c",ans,i==q?'\n':' ');
	}

	return 0;
}

Note $$$S$$$ as the prefix sum of $$$s$$$ (consider '(' as $$$1$$$ and ')' as $$$-1$$$). Firstly, we can easily calculate the initial answer $$$ans$$$.

We can see substring $$$s_{l+1,...,r}$$$ is regular if and only if $$$S_{l}==S_{r}$$$ and $$$\min(S_{l},...,S_{r})=S_{r}$$$.

Let’s see how swapping influences $$$S$$$ and $$$ans$$$.

①If we swap "()",then $$$S_{p_i} -= 2$$$, and $$$s_{l+1,...,r}$$$ will become irregular from regular if

• $$$l < p_i < r$$$;

• $$$S_{l} = S_{r} = S_{p_i} + 2$$$, or $$$S_{l} = S_{r} = S_{p_i} + 1$$$ (here $$$S_{p_i}$$$ has been subtracted by $$$2$$$);

• Before swapping, $$$\min(S_{l},...,S_{r}) = S_{l} = S_{r}$$$.

② If we swap ")(",then $$$S_{p_i} += 2$$$, and $$$s_{l+1,...,r}$$$ will become regular from irregular if

• $$$l < p_i < r$$$;

• $$$S_{l} = S_{r} = S_{p_i}$$$, or $$$S_{l} = S_{r} = S_{p_i} - 1$$$ (here $$$S_{p_i}$$$ has been added by $$$2$$$);

• After swapping, $$$\min(S_{l},...,S_{r}) = S_{l} = S_{r}$$$.

We can use binary search+segtree to maintain $$$S$$$ and update $$$ans$$$.

In addition, we find regular $$$s_{x,...,p_i}$$$ and $$$s_{p_i,...,y}$$$ similarly after each swap.

To achieve the above operations, we need to maintain two data structures that support the following operations:

1. Single Point modification;

2. Range minimum value query;

3. Query how many numbers in a range are equal to $$$k$$$.

Operations 1 and 2 can be done by using a common segment tree. For operation 3, we build $$$n$$$ dynamic segment trees $$$DT_{value}$$$ for all values.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,q;
int a[N],x[N],pre_height[N],suf_height[N];
vector<pair<int,int> > pr;

//---------------------------------------------------------------------
//ST-Table Template

int lg2[N];
int mn[N][LOGN],mnpos[N][LOGN];

void build_ST()
{
	for(int i=1;i<=n;i++) lg2[i]=(int)log2(i);
	for(int i=1;i<=n;i++) mn[i][0]=pr[i].second,mnpos[i][0]=i;
	for(int i=1;i<LOGN;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int p=j+(1<<(i-1));
			if(p>n) mn[j][i]=mn[j][i-1],mnpos[j][i]=mnpos[j][i-1];
			else    
			{
				mn[j][i]=min(mn[j][i-1],mn[p][i-1]);
				mnpos[j][i]=(mn[j][i-1]<mn[p][i-1])?mnpos[j][i-1]:mnpos[p][i-1];
			}
		}
	}
}

int getmin(int L,int R)
{
	int t=lg2[R-L+1];
	return min(mn[L][t],mn[R-(1<<t)+1][t]);
} 

int getminpos(int L,int R)
{
	int t=lg2[R-L+1];
	return mn[L][t]<mn[R-(1<<t)+1][t]?mnpos[L][t]:mnpos[R-(1<<t)+1][t];
} 
//---------------------------------------------------------------------

//---------------------------------------------------------------------
//Euler Sequence Template
int cnt;
int fa[N],dep[N],inid[N],ouid[N],euler_seq[N];
vector<int> G[N];

void DFS(int x,int pr)
{
	fa[x]=pr;
	dep[x]=dep[fa[x]]+1;
	inid[x]=(++cnt);
	euler_seq[inid[x]]=x;
	for(int i=0;i<G[x].size();i++)
	{
		int y=G[x][i];
		if(y==fa[x]) continue;
		DFS(y,x);
	}
	ouid[x]=(++cnt);
	euler_seq[ouid[x]]=x;
}
//---------------------------------------------------------------------

//---------------------------------------------------------------------
//Segtree Template

struct nod
{
	int l,r,mx,tag;
	nod *lc,*rc;
};

struct Segtree
{
	nod *root;
	
	Segtree(int sz,int x[])
	{
		build(&root,1,sz,x);
	}
	
	void newnod(nod **p,int l,int r)
	{
		*p=new nod;
		(*p)->l=l;(*p)->r=r;(*p)->mx=(*p)->tag=0;
		(*p)->lc=(*p)->rc=NULL;
	}
	
	void pushdown(nod *p)
	{
		if(p->tag)
		{
			p->mx+=p->tag;
			if(p->l!=p->r) p->lc->tag+=p->tag,p->rc->tag+=p->tag;
			p->tag=0;
		}
	}
	
	void build(nod **p,int L,int R,int x[])
	{
		newnod(p,L,R);
		if(L==R)
		{
			(*p)->mx=dep[x[L]];	
			return ;
		}
		int M=(L+R)>>1;
		build(&(*p)->lc,L,M,x);
		build(&(*p)->rc,M+1,R,x);
		(*p)->mx=max((*p)->lc->mx,(*p)->rc->mx);
	}
	
	void add(int L,int R,int v)
	{
		modify(L,R,v);
	}
	
	void modify(int L,int R,int v)
	{
		_modify(root,L,R,v);
	}
	
	void _modify(nod *p,int L,int R,int v)
	{
		pushdown(p);
		if(p->l==L&&p->r==R)
		{
			p->tag=v;
			return ;
		}
		int M=(p->l+p->r)>>1;
		if(R<=M)     _modify(p->lc,L,R,v);
		else if(L>M) _modify(p->rc,L,R,v);
		else
		{
			_modify(p->lc,L,M,v);
			_modify(p->rc,M+1,R,v);
		}
		pushdown(p->lc);
		pushdown(p->rc);
		p->mx=max(p->lc->mx,p->rc->mx);
	}
	
	int getmax(int L,int R)
	{
		return _querymx(root,L,R);
	}
	
	int _querymx(nod *p,int L,int R)
	{
		pushdown(p);
		if(p->l==L&&p->r==R) return p->mx;
		int M=(p->l+p->r)>>1;
		if(R<=M)     return _querymx(p->lc,L,R);
		else if(L>M) return _querymx(p->rc,L,R);
		else return max(_querymx(p->lc,L,M),_querymx(p->rc,M+1,R));
	}
};

//---------------------------------------------------------------------

void input()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=q;i++) scanf("%d",&x[i]);
	pr.clear();
	pr.push_back(make_pair(0,0));
	for(int i=1;i<=n;i++) pr.push_back(make_pair(a[i],i));
	sort(pr.begin(),pr.end());
}

void cal_fa(int L,int R,int FA)
{
	if(L>R) return ;
	int p=getminpos(L,R);
	fa[pr[p].second]=FA;
	cal_fa(L,p-1,pr[p].second);
	cal_fa(p+1,R,pr[p].second);
}

void build_tree()
{
	for(int i=1;i<=n;i++) G[i].clear();
	cal_fa(1,n,0);
	for(int i=2;i<=n;i++)
		G[i].push_back(fa[i]),G[fa[i]].push_back(i);
	cnt=0;	
	DFS(1,0);
}

void cal_pre()
{
	Segtree TR(2*n,euler_seq);
	for(int i=n;i;i--)
	{
		pre_height[i]=TR.getmax(1,2*n);
		int t=pr[i].second;
		TR.add(inid[t],inid[t],-n);
		TR.add(ouid[t],ouid[t],-n);
		TR.add(inid[t],ouid[t],-1);
	}
}

void cal_suf()
{
	Segtree TR(2*n,euler_seq);
	for(int i=1;i<=n;i++)
	{
		suf_height[i]=TR.getmax(1,2*n);
		int t=pr[i].second;
		TR.add(inid[t],inid[t],-n);
		TR.add(ouid[t],ouid[t],-n);
		TR.add(inid[t],ouid[t],-1);
	}
}

void solve()
{
	for(int i=1;i<=q;i++)
	{
		int L=0,R=n+1,M;
		while(L+1!=R)
		{
			M=(L+R)>>1;
			if(pr[M].first<x[i]) L=M;
			else R=M;
		}
		if(L==0) printf("%d",suf_height[1]);
		else if(L==n) printf("%d",pre_height[n]);
		else printf("%d",max(pre_height[L],suf_height[R]));
		printf("%c",i==q?'\n':' ');
	}
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
	 	input();
	 	build_ST();
	 	build_tree();
	 	cal_pre();
	 	cal_suf();
	 	solve();
	}
	
	return 0;
}

First sort $$$a_{1,\ldots,n}$$$ (let's call it $$$b_{1,\ldots,n}$$$).

For a fixed $$$x_j$$$, let's say $$$b_i < x_j < b_{i+1}$$$. The answer is $$$\max(\text{tree_height}(b_{1, \ldots ,i}), \text{tree_height}(b_{i+1, \ldots ,n})) + 1$$$. Here, $$$\text{tree_height}(b_{1,\ldots ,i})$$$ represents the height of the BST corresponding to $$$b_{1,\ldots,i}$$$ (the insertion order is based on their occurrence order in $$$a$$$).

So we want to get the $$$\text{tree_height}(b_{1,\ldots,i})$$$ for $$$1 \leq i \leq n$$$, and $$$\text{tree_height}(b_{i+1,\ldots,n})$$$ similarly.

At first,we can build the BST for $$$b_{1,\ldots,n}$$$ and its Euler sequence as well.

void cal_fa(int L,int R,int FA)
{
	if(L>R) return ;
	int p=getminpos(L,R);
	fa[pr[p].second]=FA;
	cal_fa(L,p-1,pr[p].second);
	cal_fa(p+1,R,pr[p].second);
}

Then we delete one node for each step. When we want to delete node $$$x$$$, we set $$$\text{dep}_x = 0$$$ and subtract $$$1$$$ in the subtree of $$$x$$$. This approach is based on classical Euler sequence and segment tree.

The total complexity is $$$O(n \log n)$$$.

If you think in terms of $$$k$$$, it might be hard to find the solution. Maybe it will be helpful if you fix $$$d$$$ and find the $$$k$$$ which will be swapped with $$$d$$$.

Try bruteforcing for, say, $$$n \le 20$$$. Do you see a pattern?

On $$$n=1$$$, the answer is trivially $$$1$$$.

On $$$n=2$$$, index $$$1$$$ and $$$2$$$ are swapped. The answer is therefore $$$2$$$.

For $$$n>2$$$, let us assume the element $$$1$$$ is on index $$$a$$$ and it will be swapped with index $$$k$$$. Then, $$$a$$$ must be $$$k/2$$$. We will prove this by contradiction. Let us assume that there is no divisor greater than $$$a$$$, and $$$a$$$ is lesser than $$$k/2$$$. But then, as $$$a$$$ is a multiple of $$$2$$$ in the base condition, $$$k$$$ must be a multiple of $$$2$$$, and $$$k/2$$$ is a divisor of $$$k$$$. This contradicts the assumption. By induction we can see that $$$a$$$ is always a multiple of $$$2$$$, and this proof will always hold. The element $$$1$$$ will move only when $$$k/2=a$$$.

Therefore, we can find the largest value of $$$v$$$ such that $$$2^v \le n$$$. The answer turns out to be $$$2^v$$$.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    ll q;cin>>q;
    while(q--)
    {
        ll n,p=1;cin>>n;
        while(p*2<=n)p<<=1;
        cout<<p<<"\n";
    }
}

Let’s call path $$$(1,1) \rightarrow \ldots \rightarrow (1,i)\rightarrow(2,i) \rightarrow \ldots \rightarrow (2,n)$$$ the $$$i$$$-th path. What's the difference between the $$$i$$$-th path and the $$$(i+1)$$$-th path?

What if $$$a_{2i}=1$$$ and $$$a_{1(i+1)}=0$$$ ?

What if $$$a_{2i}=0$$$ and $$$a_{1(i+1)}=1$$$ ?

• Let the string achieved by moving down on the $$$i$$$-th column be $$$S_i$$$. Then, for any $$$1 \le k < n$$$, one can observe that $$$S_k$$$ and $$$S_{k+1}$$$ can only differ by at most one index, which is index $$$k+1$$$. Thus, comparing $$$S_k$$$ and $$$S_{k+1}$$$ lexicographically can be done in $$$O(1)$$$, by comparing this one index.

• After finding the lexicographically smallest string, counting the occurrence of this string can be done straightforwardly in $$$O(n)$$$.

• The implementation can differ for each participant, but the following method provides a clean implementation. Let the initial coordinate be $$$(1,1)$$$, and maintain a counter which is initially reset to $$$1$$$. Then repeat the following until we reach $$$(2,n)$$$:

1. If we are on row $$$2$$$, move to the right.
2. If we are on column $$$n$$$, move downwards.
3. From here, let the character on the right be $$$a$$$, and one below be $$$b$$$.
4. If $$$a>b$$$, move downwards.
5. If $$$a<b$$$, move to the right and reset the counter to $$$1$$$.
6. If $$$a=b$$$, move to the right and increment the counter.

• In the end, the string on the path we passed through will be lexicographically smallest, and the integer on the counter will be the number of occurrences.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n;
char a[3][N];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
    	        scanf("%d",&n);
		for(int i=1;i<=2;i++)
		{
		    scanf("\n");
			for(int j=1;j<=n;j++)
				scanf("%c",&a[i][j]);
		}
		int max_down=n,min_down=1;
		for(int i=n;i>=2;i--)
			if(a[1][i]=='1'&&a[2][i-1]=='0') max_down=i-1;
		for(int i=1;i<max_down;i++)
			if(a[2][i]=='1'&&a[1][i+1]=='0') min_down=i+1;
		for(int i=1;i<=max_down;i++) printf("%c",a[1][i]);
		for(int i=max_down;i<=n;i++) printf("%c",a[2][i]);
		printf("\n");
		printf("%d\n",max_down-min_down+1);
	}
	
	return 0;
}

What's the maximum value of $$$p_i \oplus p_j$$$?

How to get $$$i$$$, such that $$$p_i = n-1$$$?

How to get $$$j$$$, such that $$$p_i \oplus p_j$$$ reaches the maximum value?

Step1:do queries $$$? \ x \ x \ y \ y$$$ like classic searching for the maximum value among $$$n$$$ numbers to get $$$p_i= n-1$$$;

Step2:do queries $$$? \ x \ i \ y \ i$$$ to find all index $$$k$$$ such that $$$p_i | p_{k}$$$ reaches the maximum value. We store all such indexes in a vector $$$id$$$ .

Step3:do queries $$$? \ id[x] \ id[x] \ id[y] \ id[y]$$$ to find $$$j$$$ in $$$id$$$ such that $$$p_j$$$ reaches the minimum value.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;

char query(int a,int b,int c,int d)
{
	char x;
	printf("? %d %d %d %d\n",a,b,c,d);
	fflush(stdout);
	cin>>x;
	fflush(stdout);
	return x;
}

int main()
{	
	scanf("%d",&T);
	while(T--)
	{
    	        scanf("%d",&n);
		int mx=0,ans1=0,ans2;
		vector<int> v;
		for(int i=1;i<n;i++)
		{
			int c=query(ans1,ans1,i,i);
			if(c=='<') ans1=i;
		}
		v.push_back(0);
		for(int i=1;i<n;i++)
		{
			int c=query(mx,ans1,i,ans1);
			if(c=='<')
			{
			    mx=i;
			    v.clear();
			    v.push_back(i);
			}
			else if(c=='=') v.push_back(i);
		}
		ans2=v[0];
		for(int i=1;i<v.size();i++)
		{
			int c=query(ans2,ans2,v[i],v[i]);
			if(c=='>') ans2=v[i];
		}
		printf("! %d %d\n",ans1,ans2);
		fflush(stdout);
	}
	
	return 0;
}

Observe: which cells actually change the direction of the pinball placed at position $$$p$$$ initially?

These cells are the $$$>$$$ to the left of $$$p$$$ and the $$$<$$$ to the right of $$$p$$$. Can you see the trace of the pinball?

How to quickly calculate the time when a pinball leaves the grid?

We observe that, in fact, only the $$$>$$$ to the left of $$$p$$$ and the $$$<$$$ to the right of $$$p$$$ change the direction of the pinball placed at position $$$p$$$ initially.

For convenience, let's assume $$$s_p$$$ is $$$>$$$, $$$k=min(countright(1,p),countleft(p+1,n))$$$, and the pinball leaves from the left boundary(for other situations, we can handle them in a similar way).

We can obtain $$$right[1,\ldots,k]$$$ and $$$left[1,\ldots,k]$$$ through prefix sum + binary search, where $$$right$$$ represents the indices of $$$>$$$ to the left of $$$p$$$ (in decreasing order), and $$$left$$$ represents the indices of $$$<$$$ to the right of $$$p$$$ (in increasing order).

We use $$$right$$$ and $$$left$$$ to describe the trace of the pinball:

The first segment: the pinball moves from $$$right_1$$$ to $$$left_1$$$;

The second segment: the pinball moves from $$$left_1$$$ to $$$right_2$$$;

The third segment: the pinball moves from $$$right_2$$$ to $$$left_3$$$;

$$$\ldots$$$

The $$$2k$$$-th segment: the pinball moves from $$$left_k$$$ to the left boundary.

It is not difficult to observe that we can use prefix sum to store the sum of indices, and then quickly calculate the time when the pinball moves.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n;
ll   Sl[N],Sr[N],IDl[N],IDr[N];
char s[N];

int findpre(int x)
{
	int L=0,R=n+1,M;
	while(L+1!=R)
	{
		M=(L+R)>>1;
		if(Sr[M]<x) L=M;
		else R=M; 
	}
	return R;
}

int findsuf(int x)
{
	int L=0,R=n+1,M;
	while(L+1!=R)
	{
		M=(L+R)>>1;
		if(Sl[n]-Sl[M-1]<x) R=M;
		else L=M; 
	}
	return L;
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
    	        scanf("%d%s",&n,s);
		for(int i=1;i<=n;i++) 
		{
	  	  Sr[i]=Sr[i-1]+(s[i-1]=='>');
	  	  Sl[i]=Sl[i-1]+(s[i-1]=='<');
 		  IDr[i]=IDr[i-1]+i*(s[i-1]=='>'); 	
 		  IDl[i]=IDl[i-1]+i*(s[i-1]=='<'); 	
		}		
		for(int i=1;i<=n;i++)
		{
			if(s[i-1]=='>')
			{
				if(Sr[i]>Sl[n]-Sl[i])
				{
					int p=findpre(Sr[i]-(Sl[n]-Sl[i]));
					printf("%I64d ",2*((IDl[n]-IDl[i])-(IDr[i]-IDr[p-1]))+i+(n+1));
				}
				else
				{
					int p=findsuf((Sl[n]-Sl[i])-Sr[i]+1);
					printf("%I64d ",2*((IDl[p]-IDl[i])-(IDr[i]-IDr[0]))+i);
				}
			}
			else
			{
				if(Sr[i]>=Sl[n]-Sl[i-1])
				{
					int p=findpre(Sr[i]-(Sl[n]-Sl[i-1])+1);
					printf("%I64d ",2*((IDl[n]-IDl[i-1])-(IDr[i]-IDr[p-1]))-i+(n+1));
				}
				else
				{
					int p=findsuf((Sl[n]-Sl[i-1])-Sr[i]);
					printf("%I64d ",2*((IDl[p]-IDl[i-1])-(IDr[i]-IDr[0]))-i);
				}
			}
		}
		printf("\n");
	}
	
	return 0;
}

In fact, you don't need to hire the same Pokemon more than once.

Consider graph building.

How to reduce the number of edges in the graph?

Let's consider $$$n$$$ Pokémon as nodes, and defeating Pokémon $$$u$$$ by Pokémon $$$v$$$ as the edge $$$u \rightarrow v$$$. Then the problem is essentially finding the shortest path from $$$n$$$ to $$$1$$$.

If we brute force to construct the graph, the time complexity will be $$$O(n^2m)$$$, which is unacceptable. How can we find a better way to build the graph?

Recalling, we need to represent all processes like "Pokémon $$$u$$$ increased attribute $$$x$$$ by some value and defeated Pokémon $$$v$$$" using paths in the graph.

We will use the following graph building to achieve this. Overall, we consider each attribute separately. For the $$$x$$$-th attribute, we construct $$$2n$$$ virtual nodes $$$X_1,...,X_n$$$ and $$$Y_1,...,Y_n$$$, and connect each Pokémon based on the $$$x$$$-th attribute.

For example, $$$n=3$$$ and $$$a_{1,1}=9, a_{2,1}=6, a_{3,1}=1$$$, we have the following graph building for attribute $$$1$$$:

In this graph,for example,"Pokémon $$$3$$$ increased attribute $$$1$$$ by $$$8$$$ and defeated Pokémon $$$1$$$" can be represented as path $$$3 \rightarrow X1 \rightarrow X2 \rightarrow X3 \rightarrow Y3 \rightarrow 1$$$.

More generally, our graph building method is :

• Consider each attribute separately. Assuming we are processing the $$$i$$$-th attribute, insert all $$$a_{1,i} , \ldots ,a_{n,i}$$$ into $$$val$$$ and sort it (for convenience, we assume that they are pairwise different).

• Construct $$$2n$$$ virtual nodes $$$X_1,...,X_n$$$ and $$$Y_1,...,Y_n$$$;

• Add edge $$$X_i \rightarrow X_{i+1}$$$ with a value of $$$(val_{i+1}-val_i)$$$ for $$$1 \le i < n$$$;

• Add edge $$$Y_{i+1} \rightarrow Y_{i}$$$ with a value of $$$0$$$ for $$$1 \le i < n$$$;

• Add edge $$$X_i \rightarrow Y_{i}$$$ with a value of $$$0$$$ for $$$1 \le i \le n$$$;

• Add edge $$$i \rightarrow X_{rank_i}$$$ with a value of $$$c_i$$$ for $$$1 \le i \le n$$$;

• Add edge $$$Y_{rank_i} \rightarrow i$$$ with a value of $$$0$$$ for $$$1 \le i \le n$$$.

Then we just run Dijkstra algorithm in this graph. The time complexity is $$$O(nmlog(nm))$$$.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int INFF = 1e18;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n, m;
                cin >> n >> m;

                vector<int> c(n + 1);
                for (int i = 1; i <= n; i++) cin >> c[i];

                vector<vector<int>> a(n + 1, vector<int>(m + 1));
                vector<vector<pair<int, int>>> b(m + 1);
                for (int i = 1; i <= n; i++) {
                        for (int j = 1; j <= m; j++) {
                                cin >> a[i][j];

                                b[j].push_back({a[i][j], i});
                        }
                }

                vector<vector<int>> rank(n + 1, vector<int>(m + 1));
                vector<vector<int>> dec(n + 1, vector<int>(m + 1));
                for (int j = 1; j <= m; j++) {
                        sort(b[j].begin(), b[j].end());

                        for (int i = 0; i < n; i++) {
                                auto [x, id] = b[j][i];
                                rank[id][j] = i + 1;
                                dec[i + 1][j] = id;
                        }
                }

                int ans = INFF;
                vector<int> vis(n + 1, 0);
                vector<vector<int>> dist(n + 1, vector<int>(m + 1, INFF));
                priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
                vis[1] = 1;
                for (int j = 1; j <= m; j++) dist[1][j] = 0, pq.push({dist[1][j], 1, j});
                while (!pq.empty()) {
                        auto [w, x, t] = pq.top();
                        pq.pop();

                        if (dist[x][t] < w) continue;

                        if (x == n) ans = min(ans, w + c[n]);

                        if (rank[x][t] < n) {
                                int z = dec[rank[x][t] + 1][t];
                                if (w < dist[z][t]) {
                                        dist[z][t] = w;
                                        pq.push({dist[z][t], z, t});
                                }
                        }

                        if (rank[x][t] > 1) {
                                int z = dec[rank[x][t] - 1][t];
                                if (w + a[x][t] - a[z][t] < dist[z][t]) {
                                        dist[z][t] = w + a[x][t] - a[z][t];
                                        pq.push({dist[z][t], z, t});
                                }
                        }

                        if (!vis[x]) {
                                vis[x] = 1;
                                for (int j = 1; j <= m; j++) {
                                        if (w + c[x] < dist[x][j]) {
                                                dist[x][j] = w + c[x];
                                                pq.push({dist[x][j], x, j});
                                        }
                                }
                        }
                }

                cout << ans << '\n';
        }
        
        return 0;
}

First we use the line segment tree to maintain sequence $$$b$$$. For the nodes $$$[l,r]$$$ on each line segment tree, we maintain the first and last occurrence positions of each binary bit in the interval.

We need to merge the two intervals, whether it is modification or query. Suppose you want to use the information of $$$[l, mid], [mid +1, r]$$$ to merge the information of $$$[l, r]$$$. Consider the answer that spans two intervals. If we want to make the $$$i$$$-th position of the interval OR $$$1$$$, then there are two possibilities

1. Select the last occurrence position $$$P$$$ of the $$$i$$$-th bit in $$$[l,mid].$$$

2. Select the first occurrence position $$$Q$$$ of the $$$i$$$-th bit in $$$[mid+1,r].$$$

Let $$$x = max(a[P], a[P+1],\ldots, a[mid]), y = max(a[mid + 1], a[mid + 2], \ldots, a[Q]).$$$

If $$$x<=y,$$$ we can choose the position $$$P$$$ greedily, because his price is smaller. If you choose $$$Q,$$$ then you must also choose $$$P,$$$ because choosing $$$P$$$ does not increase max $$$a.$$$ Otherwise, select $$$Q$$$ on the contrary.

With the above greedy, then you can enumerate the first binary bit $$$i$$$ that is larger than $$$v$$$. The $$$i$$$-th bit of the interval OR must be $$$1$$$, and the $$$i$$$-th bit of $$$v$$$ is $$$0$$$. For the $$$j$$$-th $$$(j >i)$$$ bit, if the $$$j$$$-th bit of $$$v$$$ is $$$1$$$, then the $$$j$$$-th bit must also be $$$1$$$. The rest of the bits can be regarded as $$$0$$$ or $$$1$$$, you only need to deal with these bits that must be selected $$$1$$$ greedily, and expand the interval.

You can use the st table $$$O(1)$$$ to find the interval max of $$$a$$$, so you can merge the information of the two intervals in the time of $$$O(log V)$$$. With the line segment tree, $$$O(q log n log V + n log V)$$$ can be done.

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 10, V = 30, inf = INT_MAX, L = 18;
int n, q, S, a[N], b[N];
struct Rmq
{
   int st[L][N];
   void init()
   {
      for (int i = 1; i <= n; i++)
         st[0][i] = a[i];
      for (int i = 1; i < L; i++)
      {
         for (int j = 1; j <= n - (1 << i) + 1; j++)
         {
            st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
         }
      }
   }
   int qry(int l, int r)
   {
      int k = __lg(r - l + 1);
      return max(st[k][l], st[k][r - (1 << k) + 1]);
   }
} ds;
struct Info
{
   int pre[V], suf[V];
   int ans, l, r;
   Info()
   {
      memset(pre, 0, sizeof(pre));
      memset(suf, 0, sizeof(suf));
      ans = inf, l = r = 0;
   }
   Info(const Info &x, const Info &y)
   {
      for (int i = 0; i < V; i++)
      {
         pre[i] = x.pre[i] ? x.pre[i] : y.pre[i];
         suf[i] = y.suf[i] ? y.suf[i] : x.suf[i];
      }
      ans = inf, l = r = 0;
   }
   friend Info operator+(const Info &x, const Info &y)
   {
      Info z(x, y);
      z.ans = min(x.ans, y.ans), z.l = x.l, z.r = y.r;
      int pl = x.r, pr = y.l;
      if (!pl)
         return z;
      for (int i = V - 1; i >= 0; i--)
      {
         int u = x.suf[i], v = y.pre[i];
         if (u)
            u = min(u, pl);
         if (v)
            v = max(v, pr);
         int lans = u ? ds.qry(u, pr) : inf;
         int rans = v ? ds.qry(pl, v) : inf;
         if (lans < rans)
         {
            if (S >> i & 1)
            {
               if (lans < z.ans)
                  pl = u;
               else
                  break;
            }
            else
               z.ans = min(z.ans, lans);
         }
         else
         {
            if (S >> i & 1)
            {
               if (rans < z.ans)
                  pr = v;
               else
                  break;
            }
            else
               z.ans = min(z.ans, rans);
         }
      }
      return z;
   }
   void clear()
   {
      *this = Info();
   }
   void upd(int p)
   {
      l = r = p, ans = b[p] > S ? a[p] : inf;
      memset(pre, 0, sizeof(pre));
      memset(suf, 0, sizeof(suf));
      for (int j = 0; j < V; j++)
      {
         if (b[p] >> j & 1)
         {
            suf[j] = p;
            pre[j] = p;
         }
      }
   }
} ans;
void reply(const Info &cur)
{
   ans = ans + cur;
}
struct Node
{
   Node *ls, *rs;
   int l, r, mid;
   Info info;
   void up()
   {
      info = ls->info + rs->info;
   }
   void update(int p)
   {
      if (l == r)
         return info.upd(l);
      p <= mid ? ls->update(p) : rs->update(p);
      up();
   }
   void query(int ql, int qr)
   {
      if (l >= ql && r <= qr)
         return reply(info);
      if (ql <= mid)
         ls->query(ql, qr);
      if (qr > mid)
         rs->query(ql, qr);
   }
} mempool[N + 5 << 1], *cnt = mempool, *rt;
Node *build(int l, int r)
{
   Node *u = cnt++;
   int mid = l + r >> 1;
   u->l = l, u->r = r, u->mid = mid;
   if (l == r)
   {
      u->info.upd(l);
      return u;
   }
   u->ls = build(l, mid);
   u->rs = build(mid + 1, r);
   u->up();
   return u;
}
 
void solve()
{
   cin >> n >> S;
   S--;
   for (int i = 1; i <= n; i++)
      cin >> a[i];
   ds.init();
   for (int i = 1; i <= n; i++)
      cin >> b[i];
   rt = build(1, n);
   cin >> q;
   for (int i = 0; i < q; i++)
   {
      int opt;
      cin >> opt;
      if (opt == 1)
      {
         int p, x;
         cin >> p >> x;
         b[p] = x;
         rt->update(p);
      }
      else
      {
         int l, r;
         cin >> l >> r;
         ans.clear();
         rt->query(l, r);
         cout << (ans.ans == inf ? -1 : ans.ans) << ' ';
      }
   }
   cout << "\n";
}
int main()
{
#ifndef ONLINE_JUDGE
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
#endif
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   ios::sync_with_stdio(false), cin.tie(0);
   int t = 0;
   cin >> t;
   while (t--)
   {
      solve();
   }
 
   // 	cerr << 1.0 * clock() / CLOCKS_PER_SEC << '\n';
   return 0;
}

We found it difficult to directly calculate all valid permutations. How about calculating all invalid permutations?

Can you come up with an $$$O(n^2)$$$ DP solution?

How to optimize the $$$O(n^2)$$$ DP solution?

We found it difficult to directly calculate all valid permutations. Consider calculating all invalid permutations and subtract it from $$$n!$$$.

Let's first make some notes. We note $$$P_i=max(p_1,...,p_i),Q_i=max(q_1,...,q_i)$$$,and $$$last_i=max(j)(P_j \neq P_i)$$$.And note the values of all extreme points is $$$val[1,...,m]$$$ and positions is $$$pos[1,...,m]$$$.

For example,$$$p=[3,1,4,2,6,5]$$$,we get $$$m=3$$$, $$$val=[3,4,6]$$$ and $$$pos=[1,3,5]$$$.

Let’s call a permutation $$$q$$$ “i-invalid” if there’s an index $$$j$$$ satisfying $$$Q_j=P_j=val_i$$$.

Note $$$S_i$$$ as the set of all “i-invalid” permutations.According to the Inclusion-Exclusion Principle,the answer is $$$n!-(|S_1|+|S_2|+...)+(|S_1∩S_2|+|S_1∩S_3|+...)-...$$$

Consider put $$$val_i$$$ in $$$q$$$ to make $$$q$$$ “i-invalid”.There’re $$$2$$$ kinds of ways:

• $$$q_j=val_i(1 \le j < pos_i)$$$ and $$$Q_{pos_i}=val_i$$$;

• $$$q_j=val_i(pos_i \le j< pos_{i+1})$$$ and $$$Q_{pos_i}=val_i$$$.

In both cases,we call the first $$$max(j,pos_i)$$$ numbers are “determined”. In other words,they’re some numbers in $$$[1,val_i]$$$.

Then we can find an $$$O(n^2)$$$ DP. Note $$$dp_{i,j}$$$ — $$$i$$$ stands for the first $$$i$$$ numbers is “determined”,and $$$j$$$ stands for $$$j$$$ extreme values are “invalid”. In fact we only care about the parity of $$$j$$$,so $$$j=0,1$$$. Note for the first $$$i$$$ numbers are “determined” automatically means $$$Q_i=P_i$$$. In addition,$$$q_i=P_i(P_i=P_{i-1})$$$ or $$$q_i<P_i(P_i \neq P_{i-1})$$$.

We get a DP formula $$$dp_{i,j}= \Sigma_{k=0}^{last_i} dp_{k,j \oplus 1} \cdot A^{P_i-k-1}_{i-k-1} \cdot (P_i==P_{i+1}?1:i-k)$$$

Here is a small trick to reduce the constant. If we note $$$f_i=dp_{i,0}-dp_{i,1}$$$, we get a more concise formula $$$f_{i}= -\Sigma_{j=0}^{last_i} f_{j} \cdot A^{P_i-j-1}_{i-j-1} \cdot (P_i==P_{i+1}?1:i-j)$$$

We perform the following transformation on the formula.

① For $$$i$$$ satisfying $$$P_i=P_{i-1}$$$, we get

$$$f_{i}= -\Sigma_{j=0}^{last_i} f_{j} \cdot A^{P_i-j-1}_{i-j-1} = -[(P_i-i)!]^{-1} \Sigma_{j=0}^{last_i} f_{j} \cdot (P_i-j-1)!$$$

② For $$$i$$$ satisfying $$$P_i \neq P_{i-1}$$$, we get

$$$f_{i}= -\Sigma_{j=0}^{last_i} f_{j} \cdot A^{P_i-j-1}_{i-j-1} \cdot (i-j) = -i[(P_i-i)!]^{-1} \Sigma_{j=0}^{last_i} f_{j} \cdot (P_i-j-1)! + [(P_i-i)!]^{-1} \Sigma_{j=0}^{last_i} jf_{j} \cdot (P_i-j-1)!$$$

After that, we have transformed the formula into a classical form $$$f(i)= h(i) \Sigma_{j=0}^{i-1} f(j) \cdot g(i-j)$$$, which can be calculate in $$$O(n log^2 n)$$$ by D&C+FFT.

#include<bits/stdc++.h>
using namespace std;

#define all(a) a.begin(),a.end()
#define pb push_back
#define sz(a) ((int)a.size())

using ll=long long;
using u32=unsigned int;
using u64=unsigned long long;
using i128=__int128;
using u128=unsigned __int128;
using f128=__float128;

using pii=pair<int,int>;
using pll=pair<ll,ll>;

template<typename T> using vc=vector<T>;
template<typename T> using vvc=vc<vc<T>>;
template<typename T> using vvvc=vc<vvc<T>>;

using vi=vc<int>;
using vll=vc<ll>;
using vvi=vc<vi>;
using vvll=vc<vll>;

#define vv(type,name,n,...) \
    vector<vector<type>> name(n,vector<type>(__VA_ARGS__))
#define vvv(type,name,n,m,...) \
    vector<vector<vector<type>>> name(n,vector<vector<type>>(m,vector<type>(__VA_ARGS__)))

template<typename T> using min_heap=priority_queue<T,vector<T>,greater<T>>;
template<typename T> using max_heap=priority_queue<T>;

// https://trap.jp/post/1224/
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define rep_subset(i,s) for(ll i=(s); i>=0; i=(i==0?-1:(i-1)&(s)))

template<typename T, typename S> constexpr T ifloor(const T a, const S b){return a/b-(a%b&&(a^b)<0);}
template<typename T, typename S> constexpr T iceil(const T a, const S b){return ifloor(a+b-1,b);}

template<typename T>
void sort_unique(vector<T> &vec){
    sort(vec.begin(),vec.end());
    vec.resize(unique(vec.begin(),vec.end())-vec.begin());
}

template<typename T, typename S> constexpr bool chmin(T &a, const S b){if(a>b) return a=b,true; return false;}
template<typename T, typename S> constexpr bool chmax(T &a, const S b){if(a<b) return a=b,true; return false;}

template<typename T, typename S> istream& operator >> (istream& i, pair<T,S> &p){return i >> p.first >> p.second;}
template<typename T, typename S> ostream& operator << (ostream& o, const pair<T,S> &p){return o << p.first << ' ' << p.second;}

#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 777771449
#endif

template<typename T> void print(vector<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(unordered_set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(T && x) {cout << x << "\n";}
template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);}

template<typename T> istream& operator >> (istream& i, vector<T> &vec){for(auto &x: vec) i >> x; return i;}

vvi read_graph(int n, int m, int base=1){
    vvi adj(n);
    for(int i=0,u,v; i<m; ++i){
        cin >> u >> v,u-=base,v-=base;
        adj[u].pb(v),adj[v].pb(u);
    }
    return adj;
}

vvi read_tree(int n, int base=1){return read_graph(n,n-1,base);}

template<typename T, typename S> pair<T,S> operator + (const pair<T,S> &a, const pair<T,S> &b){return {a.first+b.first,a.second+b.second};}

template<typename T> constexpr T inf=0;
template<> constexpr int inf<int> = 0x3f3f3f3f;
template<> constexpr ll inf<ll> = 0x3f3f3f3f3f3f3f3f;

template<typename T> vector<T> operator += (vector<T> &a, int val){for(auto &i: a) i+=val; return a;}

template<typename T> T isqrt(const T &x){T y=sqrt(x+2); while(y*y>x) y--; return y;}

#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())



#include <utility>

namespace atcoder {

namespace internal {

// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
    x %= m;
    if (x < 0) x += m;
    return x;
}

// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
    unsigned int _m;
    unsigned long long im;

    // @param m `1 <= m < 2^31`
    barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}

    // @return m
    unsigned int umod() const { return _m; }

    // @param a `0 <= a < m`
    // @param b `0 <= b < m`
    // @return `a * b % m`
    unsigned int mul(unsigned int a, unsigned int b) const {
        // [1] m = 1
        // a = b = im = 0, so okay

        // [2] m >= 2
        // im = ceil(2^64 / m)
        // -> im * m = 2^64 + r (0 <= r < m)
        // let z = a*b = c*m + d (0 <= c, d < m)
        // a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
        // c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
        // ((ab * im) >> 64) == c or c + 1
        unsigned long long z = a;
        z *= b;
#ifdef _MSC_VER
        unsigned long long x;
        _umul128(z, im, &x);
#else
        unsigned long long x =
            (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
        unsigned int v = (unsigned int)(z - x * _m);
        if (_m <= v) v += _m;
        return v;
    }
};

// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
    if (m == 1) return 0;
    unsigned int _m = (unsigned int)(m);
    unsigned long long r = 1;
    unsigned long long y = safe_mod(x, m);
    while (n) {
        if (n & 1) r = (r * y) % _m;
        y = (y * y) % _m;
        n >>= 1;
    }
    return r;
}

// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
    if (n <= 1) return false;
    if (n == 2 || n == 7 || n == 61) return true;
    if (n % 2 == 0) return false;
    long long d = n - 1;
    while (d % 2 == 0) d /= 2;
    constexpr long long bases[3] = {2, 7, 61};
    for (long long a : bases) {
        long long t = d;
        long long y = pow_mod_constexpr(a, t, n);
        while (t != n - 1 && y != 1 && y != n - 1) {
            y = y * y % n;
            t <<= 1;
        }
        if (y != n - 1 && t % 2 == 0) {
            return false;
        }
    }
    return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);

// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
    a = safe_mod(a, b);
    if (a == 0) return {b, 0};

    // Contracts:
    // [1] s - m0 * a = 0 (mod b)
    // [2] t - m1 * a = 0 (mod b)
    // [3] s * |m1| + t * |m0| <= b
    long long s = b, t = a;
    long long m0 = 0, m1 = 1;

    while (t) {
        long long u = s / t;
        s -= t * u;
        m0 -= m1 * u;  // |m1 * u| <= |m1| * s <= b

        // [3]:
        // (s - t * u) * |m1| + t * |m0 - m1 * u|
        // <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        // = s * |m1| + t * |m0| <= b

        auto tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    // by [3]: |m0| <= b/g
    // by g != b: |m0| < b/g
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}

// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
    if (m == 2) return 1;
    if (m == 167772161) return 3;
    if (m == 469762049) return 3;
    if (m == 754974721) return 11;
    if (m == 998244353) return 3;
    int divs[20] = {};
    divs[0] = 2;
    int cnt = 1;
    int x = (m - 1) / 2;
    while (x % 2 == 0) x /= 2;
    for (int i = 3; (long long)(i)*i <= x; i += 2) {
        if (x % i == 0) {
            divs[cnt++] = i;
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    if (x > 1) {
        divs[cnt++] = x;
    }
    for (int g = 2;; g++) {
        bool ok = true;
        for (int i = 0; i < cnt; i++) {
            if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
                ok = false;
                break;
            }
        }
        if (ok) return g;
    }
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);

}  // namespace internal

}  // namespace atcoder


#include <cassert>
#include <numeric>
#include <type_traits>

namespace atcoder {

namespace internal {

#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value ||
                                  std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value ||
                                  std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;

template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
                                                  is_signed_int128<T>::value ||
                                                  is_unsigned_int128<T>::value,
                                              std::true_type,
                                              std::false_type>::type;

template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                std::true_type,
                                                std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<(is_integral<T>::value &&
                               std::is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename std::conditional<std::is_signed<T>::value,
                              std::make_unsigned<T>,
                              std::common_type<T>>::type>::type;

#else

template <class T> using is_integral = typename std::is_integral<T>;

template <class T>
using is_signed_int =
    typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<is_integral<T>::value &&
                                  std::is_unsigned<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
                                              std::make_unsigned<T>,
                                              std::common_type<T>>::type;

#endif

template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

}  // namespace internal

}  // namespace atcoder

#include <cassert>
#include <numeric>
#include <type_traits>

#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

struct modint_base {};
struct static_modint_base : modint_base {};

template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;

}  // namespace internal

template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
    using mint = static_modint;

  public:
    static constexpr int mod() { return m; }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    static_modint() : _v(0) {}
    template <class T, internal::is_signed_int_t<T>* = nullptr>
    static_modint(T v) {
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }
    template <class T, internal::is_unsigned_int_t<T>* = nullptr>
    static_modint(T v) {
        _v = (unsigned int)(v % umod());
    }
    static_modint(bool v) { _v = ((unsigned int)(v) % umod()); }

    unsigned int val() const { return _v; }

    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        unsigned long long z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        if (prime) {
            assert(_v);
            return pow(umod() - 2);
        } else {
            auto eg = internal::inv_gcd(_v, m);
            assert(eg.first == 1);
            return eg.second;
        }
    }

    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

  private:
    unsigned int _v;
    static constexpr unsigned int umod() { return m; }
    static constexpr bool prime = internal::is_prime<m>;
};

template <int id> struct dynamic_modint : internal::modint_base {
    using mint = dynamic_modint;

  public:
    static int mod() { return (int)(bt.umod()); }
    static void set_mod(int m) {
        assert(1 <= m);
        bt = internal::barrett(m);
    }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    dynamic_modint() : _v(0) {}
    template <class T, internal::is_signed_int_t<T>* = nullptr>
    dynamic_modint(T v) {
        long long x = (long long)(v % (long long)(mod()));
        if (x < 0) x += mod();
        _v = (unsigned int)(x);
    }
    template <class T, internal::is_unsigned_int_t<T>* = nullptr>
    dynamic_modint(T v) {
        _v = (unsigned int)(v % mod());
    }
    dynamic_modint(bool v) { _v = ((unsigned int)(v) % mod()); }

    unsigned int val() const { return _v; }

    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v += mod() - rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        _v = bt.mul(_v, rhs._v);
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        auto eg = internal::inv_gcd(_v, mod());
        assert(eg.first == 1);
        return eg.second;
    }

    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

  private:
    unsigned int _v;
    static internal::barrett bt;
    static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt = 998244353;

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;

namespace internal {

template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;

template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;

template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};

template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;

}  // namespace internal

}  // namespace atcoder


#include <algorithm>
#include <array>

#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder

#include <cassert>
#include <type_traits>
#include <vector>

namespace atcoder {

namespace internal {

template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly(std::vector<mint>& a) {
    static constexpr int g = internal::primitive_root<mint::mod()>;
    int n = int(a.size());
    int h = internal::ceil_pow2(n);

    static bool first = true;
    static mint sum_e[30];  // sum_e[i] = ies[0] * ... * ies[i - 1] * es[i]
    if (first) {
        first = false;
        mint es[30], ies[30];  // es[i]^(2^(2+i)) == 1
        int cnt2 = bsf(mint::mod() - 1);
        mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv();
        for (int i = cnt2; i >= 2; i--) {
            // e^(2^i) == 1
            es[i - 2] = e;
            ies[i - 2] = ie;
            e *= e;
            ie *= ie;
        }
        mint now = 1;
        for (int i = 0; i <= cnt2 - 2; i++) {
            sum_e[i] = es[i] * now;
            now *= ies[i];
        }
    }
    for (int ph = 1; ph <= h; ph++) {
        int w = 1 << (ph - 1), p = 1 << (h - ph);
        mint now = 1;
        for (int s = 0; s < w; s++) {
            int offset = s << (h - ph + 1);
            for (int i = 0; i < p; i++) {
                auto l = a[i + offset];
                auto r = a[i + offset + p] * now;
                a[i + offset] = l + r;
                a[i + offset + p] = l - r;
            }
            now *= sum_e[bsf(~(unsigned int)(s))];
        }
    }
}

template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly_inv(std::vector<mint>& a) {
    static constexpr int g = internal::primitive_root<mint::mod()>;
    int n = int(a.size());
    int h = internal::ceil_pow2(n);

    static bool first = true;
    static mint sum_ie[30];  // sum_ie[i] = es[0] * ... * es[i - 1] * ies[i]
    if (first) {
        first = false;
        mint es[30], ies[30];  // es[i]^(2^(2+i)) == 1
        int cnt2 = bsf(mint::mod() - 1);
        mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv();
        for (int i = cnt2; i >= 2; i--) {
            // e^(2^i) == 1
            es[i - 2] = e;
            ies[i - 2] = ie;
            e *= e;
            ie *= ie;
        }
        mint now = 1;
        for (int i = 0; i <= cnt2 - 2; i++) {
            sum_ie[i] = ies[i] * now;
            now *= es[i];
        }
    }

    for (int ph = h; ph >= 1; ph--) {
        int w = 1 << (ph - 1), p = 1 << (h - ph);
        mint inow = 1;
        for (int s = 0; s < w; s++) {
            int offset = s << (h - ph + 1);
            for (int i = 0; i < p; i++) {
                auto l = a[i + offset];
                auto r = a[i + offset + p];
                a[i + offset] = l + r;
                a[i + offset + p] =
                    (unsigned long long)(mint::mod() + l.val() - r.val()) *
                    inow.val();
            }
            inow *= sum_ie[bsf(~(unsigned int)(s))];
        }
    }
}

}  // namespace internal

template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution(std::vector<mint> a, std::vector<mint> b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};
    if (std::min(n, m) <= 60) {
        if (n < m) {
            std::swap(n, m);
            std::swap(a, b);
        }
        std::vector<mint> ans(n + m - 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans[i + j] += a[i] * b[j];
            }
        }
        return ans;
    }
    int z = 1 << internal::ceil_pow2(n + m - 1);
    a.resize(z);
    internal::butterfly(a);
    b.resize(z);
    internal::butterfly(b);
    for (int i = 0; i < z; i++) {
        a[i] *= b[i];
    }
    internal::butterfly_inv(a);
    a.resize(n + m - 1);
    mint iz = mint(z).inv();
    for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
    return a;
}

template <unsigned int mod = 998244353,
          class T,
          std::enable_if_t<internal::is_integral<T>::value>* = nullptr>
std::vector<T> convolution(const std::vector<T>& a, const std::vector<T>& b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};

    using mint = static_modint<mod>;
    std::vector<mint> a2(n), b2(m);
    for (int i = 0; i < n; i++) {
        a2[i] = mint(a[i]);
    }
    for (int i = 0; i < m; i++) {
        b2[i] = mint(b[i]);
    }
    auto c2 = convolution(move(a2), move(b2));
    std::vector<T> c(n + m - 1);
    for (int i = 0; i < n + m - 1; i++) {
        c[i] = c2[i].val();
    }
    return c;
}

std::vector<long long> convolution_ll(const std::vector<long long>& a,
                                      const std::vector<long long>& b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};

    static constexpr unsigned long long MOD1 = 754974721;  // 2^24
    static constexpr unsigned long long MOD2 = 167772161;  // 2^25
    static constexpr unsigned long long MOD3 = 469762049;  // 2^26
    static constexpr unsigned long long M2M3 = MOD2 * MOD3;
    static constexpr unsigned long long M1M3 = MOD1 * MOD3;
    static constexpr unsigned long long M1M2 = MOD1 * MOD2;
    static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;

    static constexpr unsigned long long i1 =
        internal::inv_gcd(MOD2 * MOD3, MOD1).second;
    static constexpr unsigned long long i2 =
        internal::inv_gcd(MOD1 * MOD3, MOD2).second;
    static constexpr unsigned long long i3 =
        internal::inv_gcd(MOD1 * MOD2, MOD3).second;

    auto c1 = convolution<MOD1>(a, b);
    auto c2 = convolution<MOD2>(a, b);
    auto c3 = convolution<MOD3>(a, b);

    std::vector<long long> c(n + m - 1);
    for (int i = 0; i < n + m - 1; i++) {
        unsigned long long x = 0;
        x += (c1[i] * i1) % MOD1 * M2M3;
        x += (c2[i] * i2) % MOD2 * M1M3;
        x += (c3[i] * i3) % MOD3 * M1M2;
        // B = 2^63, -B <= x, r(real value) < B
        // (x, x - M, x - 2M, or x - 3M) = r (mod 2B)
        // r = c1[i] (mod MOD1)
        // focus on MOD1
        // r = x, x - M', x - 2M', x - 3M' (M' = M % 2^64) (mod 2B)
        // r = x,
        //     x - M' + (0 or 2B),
        //     x - 2M' + (0, 2B or 4B),
        //     x - 3M' + (0, 2B, 4B or 6B) (without mod!)
        // (r - x) = 0, (0)
        //           - M' + (0 or 2B), (1)
        //           -2M' + (0 or 2B or 4B), (2)
        //           -3M' + (0 or 2B or 4B or 6B) (3) (mod MOD1)
        // we checked that
        //   ((1) mod MOD1) mod 5 = 2
        //   ((2) mod MOD1) mod 5 = 3
        //   ((3) mod MOD1) mod 5 = 4
        long long diff =
            c1[i] - internal::safe_mod((long long)(x), (long long)(MOD1));
        if (diff < 0) diff += MOD1;
        static constexpr unsigned long long offset[5] = {
            0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
        x -= offset[diff % 5];
        c[i] = x;
    }

    return c;
}

}  // namespace atcoder

using namespace atcoder;

using mint=modint998244353;
//using mint=modint1000000007;

template<int mod>
struct nCr{
    vector<static_modint<mod>> fac,inv,ifac;
    void calc(int n){
        fac.resize(n+1),inv.resize(n+1),ifac.resize(n+1);
        fac[0]=inv[1]=ifac[0]=1;
        for(int i=1; i<=n; ++i) fac[i]=fac[i-1]*static_modint<mod>::raw(i);
        for(int i=2; i<=n; ++i) inv[i]=inv[mod%i]*static_modint<mod>::raw(mod-mod/i);
        for(int i=1; i<=n; ++i) ifac[i]=ifac[i-1]*inv[i];
    }
    static_modint<mod> C(int n, int m){
        if(m<0||m>n) return 0;
        return fac[n]*ifac[m]*ifac[n-m];
    }
};

nCr<998244353> de;

void ahcorz(){
    // (a_i - j)! / (a_i - i)! (a_i = a_j)
    // (a_i - j - 1)! / (a_i - i)! * (i - j) (a_i != a_j)
    int n; cin >> n;
    de.calc(n+1);
    vi a; a.pb(0);
    rep(n){
        int x; cin >> x;
        a.pb(max(a.back(),x));
    }
    vc<mint> dp(n+1),aux(n+1);
    auto solve=[&](auto &self, int l, int r) -> void{
        if(l+1==r){
            if(l==0) dp[l]=-1;
            else dp[l]+=aux[l]*l;
            dp[l]*=de.ifac[a[l]-l];
            return;
        }
        int mid=l+r>>1;
        self(self,l,mid);
        if(a[mid]==a[mid-1]){
            int x=mid-1,y=mid;
            while(x-1>=l&&a[x-1]==a[mid]) x--;
            while(y+1<r&&a[y+1]==a[mid]) y++;
            mint tot,tot1,tot2;
            rep(i,x,mid) tot+=dp[i]*de.fac[a[mid]-i],tot1+=dp[i]*de.fac[a[mid]-i-1],tot2+=dp[i]*de.fac[a[mid]-i-1]*i;
            rep(i,mid,y+1) dp[i]-=tot-(tot1*i-tot2);
        }
        vc<mint> vec;
        rep(i,a[mid]-mid,a[r-1]-(l+1)+1) vec.pb(de.fac[i]);
        vc<mint> vec1,vec2;
        rep(i,l,mid) vec1.pb(dp[i]),vec2.pb(dp[i]*i);
        auto res1=convolution(vec,vec1),res2=convolution(vec,vec2);
        int base=a[mid]-mid+l+1;
        rep(i,mid,r) if(a[i]-base>=0&&a[i]-base<sz(res1)) aux[i]-=res1[a[i]-base],dp[i]+=res2[a[i]-base];
        self(self,mid,r);
    };
    solve(solve,0,n+1);
    print(dp[n].val());
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cout << fixed << setprecision(20);
    int t=1;
    cin >> t;
    while(t--) ahcorz();
}

For a given center coordinate $$$(x,y)$$$, we can model the objective function $$$r=f(x,y)$$$ to maximize as follows.

Formally, this can be modeled as follows:

This is a second order cone program. Generally, this is not as simple to solve as linear or quadratic programs. There are multiple solvers out there, but all of them are either commercial or simply unfit for use on Codeforces. And even if we use general approaches to second order cone programming, their time complexity is at least $$$\mathcal{O}(n^{3.5})$$$, so they cannot work. Almost all general approaches to convex programming do not help very much for this task also, because of the following reasons.

• Gradient Descent cannot work in this task. The objective function is not smooth.

• Coordinate Descent also cannot work in this task for the same reason, and it is not hard to find a countercase.

• Subgradient methods can solve this task, but they take $$$\mathcal{O}(1/\epsilon^2)$$$ iterations to converge. This is a very big dependency on the precision, so they take too much time.

• We do not expect anyone to write Adaptive Coordinate Descent during contest time, but we still tested the PRAXIS algorithm and checked that it does not pass.

• Using nested ternary searches does not help very much. The time complexity will be $$$\mathcal{O}(n \log^2 (1/\epsilon))$$$, but the constants are large due to multiple function calls and floating point operations.

• Heuristics such as the Nelder-Mead method are not proven to converge. In many cases we found it not converging successfully.

In the editorial, we will explain a solution of expected $$$\mathcal{O}(n)$$$ time complexity, with constants depending on the number of dimensions (which is $$$2$$$ in our case).

First, we observe that any answer can be described as a "basis" of at most $$$3$$$ selected circles. For $$$k=0,1,2,3$$$, the basis is as follows.

• Case 1: $$$k=0$$$

This is the case of no circles, which can be regarded as an "identity element" of bases. Some very huge circle that will enclose any given circle, for example the circle with $$$10^{18}$$$ as radius and $$$(0,0)$$$ as center, can represent this case.

• Case 2: $$$k=1$$$

This is the case of a single circle. The circle that represents this case is the one selected circle.

• Case 3: $$$k=2$$$

This is the case of two circles, for which the basis is the largest circle in the intersection of two circles. We can find this by choosing the center as the midpoint of the two points $$$A$$$ and $$$B$$$, where $$$A$$$ and $$$B$$$ are the points where the line segment between circle centers and the circle itself intersect.

• Case 4: $$$k=3$$$

This is the case of three circles, and the most tricky of all four cases. It can be found as one solution to the following system of quadratic equations:

This can be solved algebraically. If you are used to solving geometry problems in Olympiads, you may know the ''Problem of Apollonius''. This is one special case of the problem, which is not very often mentioned because often the three circles do not intersect with each other (thus most of the time one solution for $$$r$$$ must be negative). Or if one does not know the problem, they can find that the locus of the circle center that meets with two circle edges (as in Case 3) is a conic section, precisely one side of a pair of hyperbola. By finding the intersections of two hyperbola, one can find the center of this circle. Thus, this circle can be found in $$$\mathcal{O}(1)$$$ time, with constants based on number of dimensions.

By the system of quadratic equations stated above, we see that there are at most $$$2$$$ solutions. It is sufficient to take the one that happens to be inside the intersection. (If there are two such solutions, take the larger one. For the current version of the data this check is not necessary, but it does not hurt to try.) Thus, for some $$$n>3$$$, the bases can be represented with some $$$k \le 3$$$ circles.

Do note that, already, we have an $$$\mathcal{O}(n^3)$$$ solution based on this. We enumerate all possible bases, and find the smallest one out of them (since that one will be the one that satisfies the conditions).

Now, for some basis circle $$$(x,y,r)$$$, we can check whether some given circle $$$(x_i,y_i,r_i)$$$ is "violated" by this basis (i.e. this basis is not inside this circle) in $$$\mathcal{O}(1)$$$ by comparing the distance. We take an incremental approach. We add circles to the basis one by one, up to $$$3$$$ circles. We choose to change the basis if only the next added circle is violated by the current basis. Of course, still this takes $$$\mathcal{O}(n^3)$$$ time, and sorting the circles based on any argument will not help anyways.

However, adding the circles in random order will make it only take expected $$$\mathcal{O}(n)$$$ time. This can be analyzed by the probability that a new basis will be added. The precise analysis for the time complexity is left as a practice for the reader.

If you have seen the minimum enclosing circle problem, the Welzl's algorithm to solve that precise problem will seem very similar to this. In fact, the suggested algorithm itself is not very different from Welzl's algorithm. If you want, though, you may take an iterative approach instead of modifying Welzl's algorithm. Using three nested loops will do.

There is only two issues left. The first is the issue of numerical instability. Sometimes, due to numerical instability, the algorithm will return a NaN value. It is not that hard to solve, we can simply shuffle again and rerun the algorithm. The given time limit will be sufficient for doing this unless the constant is too big. The second is more tricky, and it is about hacks.

If you use a fixed seed for randomization (or time-based seeds to some extent), someone may hack you by adding an adversarial test case which makes the time complexity explode back to $$$\mathcal{O}(n^3)$$$. This is very bad. How do we solve this? To intervent this, we will make the algorithm halt when the number of iterations exceed a certain limit. Formally, let us choose a constant $$$c$$$, and the algorithm will halt and rerun when the number of iterations exceeds $$$c \cdot n$$$. Then, if the probability of the algorithm successfully running in this number of iterations is $$$p$$$, the expected number of reruns needed is $$$\mathcal{O}(1/p)$$$, and hacking is much harder. The algorithm will successfully find the solution in $$$\mathcal{O}((c/p) \cdot n)$$$ time. Of course, the probability $$$p$$$ depends on $$$c$$$, and you must tune the value as needed. Empirically $$$c=30$$$ runs very well, almost always taking no longer than $$$0.4$$$ seconds under proper optimizations, and $$$1.5$$$ seconds without.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
using lf=long double;
using pt=pair<lf,lf>;
lf& real(pt& p){return p.first;}
lf& imag(pt& p){return p.second;}
pt midp(pt a,pt b){return pt{(real(a)+real(b))/2,(imag(a)+imag(b))/2};}
pt addi(pt a,pt b){return pt{(real(a)+real(b)),(imag(a)+imag(b))};}
pt subt(pt a,pt b){return pt{(real(a)-real(b)),(imag(a)-imag(b))};}
pt mult(pt a,lf b){return pt{real(a)*b,imag(a)*b};}
lf abs(pt a){return sqrtl(powl(real(a),2)+powl(imag(a),2));}
lf dist(pt a,pt b){return sqrtl(powl(real(a)-real(b),2)+powl(imag(a)-imag(b),2));}
 
struct circ{pt p;lf r;};
const lf inf=1e18;
 
circ basis0(){return {pt{0,0},inf};}
 
circ basis1(circ a){return a;}
 
circ basis2(circ a,circ b)
{
    pt aa=a.p,bb=b.p;
    pt ab=subt(bb,aa),ba=subt(aa,bb);
    lf aab=abs(ab),aba=abs(ba);
    real(ab)/=aab;
    imag(ab)/=aab;
    real(ba)/=aba;
    imag(ba)/=aba;
    pt ar=addi(aa,mult(ab,a.r)),br=addi(bb,mult(ba,b.r));
    
    return {midp(ar,br),dist(ar,br)/2.0L};
}
 
circ basis3(circ a,circ b,circ c)
{
    lf x1=real(a.p),y1=imag(a.p),r1=a.r;
    lf x2=real(b.p),y2=imag(b.p),r2=b.r;
    lf x3=real(c.p),y3=imag(c.p),r3=c.r;
    lf a2=x1-x2,a3=x1-x3,b2=y1-y2,b3=y1-y3,c2=r2-r1,c3=r3-r1;
    lf d1=x1*x1+y1*y1-r1*r1,d2=d1-x2*x2-y2*y2+r2*r2,d3=d1-x3*x3-y3*y3+r3*r3;
    lf ab=a3*b2-a2*b3;
    lf xa=(b2*d3-b3*d2)/(ab*2)-x1;
    lf xb=(b3*c2-b2*c3)/ab;
    lf ya=(a3*d2-a2*d3)/(ab*2)-y1;
    lf yb=(a2*c3-a3*c2)/ab;
    lf A=xb*xb+yb*yb-1;
    lf B=2*(r1+xa*xb+ya*yb);
    lf C=xa*xa+ya*ya-r1*r1;
    lf r=-(A?(B-sqrtl(B*B-4*A*C))/(2*A):C/B);
    return {pt{x1+xa+xb*r,y1+ya+yb*r},r};
}
 
bool viol(circ p,circ a)
{
    return a.r<p.r+dist(a.p,p.p);
}
 
circ solve(vector<circ>&v)
{
    lf _nan=nan("aaa");
    mt19937_64 mt(1999999);
    //shuffle(begin(v),end(v),mt);
    vector<circ>basis;
    auto trivial=[&]()
    {
        if(size(basis)==0)return basis0();
        if(size(basis)==1)return basis[0];
        if(size(basis)==2)return basis2(basis[0],basis[1]);
        return basis3(basis[0],basis[1],basis[2]);
    };
 
    int counter=0;
    
    auto rec=[&](auto rec,int n)->circ
    {
        if(n==0||size(basis)==3)return trivial();
        counter++;
        if(counter>30*size(v))return {pt{0,0},_nan};
        auto c=rec(rec,n-1);
        auto p=v[n-1];
        if(!viol(c,p)||isnan(c.r))return c;
        basis.push_back(p);
        c=rec(rec,n-1);
        basis.pop_back();
        return c;
    };
    auto c=rec(rec,size(v));
    while(isnan(c.r))
    {
        counter=0;
        shuffle(begin(v),end(v),mt);
        c=rec(rec,size(v));
    }
    return c;
}
 
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;cin>>n;
    vector<circ>v(n);
    for(auto&[p,r]:v)
    {
        ll x,y,rr;cin>>x>>y>>rr;
        p={x,y};r=rr;
    }
    auto ans=solve(v);
    cout<<setprecision(16)<<fixed<<real(ans.p)<<" "<<imag(ans.p)<<" "<<ans.r<<"\n";
}