Problem Description

Since the constraints are small, you only need to simulate this process.

You are tasked with finding the minimum number of bandages required to defeat a dragon using a sword. The sword deals:

• 1 damage if the i-th attack is not divisible by 3.
• 2 damage if the i-th attack is divisible by 3.

If your health will becomes less than $$$0$$$ when the dragon attack you (in other words, your hp is less than $$$k$$$) , you must use a bandage.

void solve(){
    int h,k,n;cin>>h>>k>>n;
    int ans = 0, l = k, r = 1;
    while(h > 1){
        r++;
        k -= n;
        if(k <= 0){
            k = l - n;
            ans++;
        }
        if(r % 3 == 0){
            h-=2;
        }else{
            h--;
        }
    }
    cout<<ans<<endl;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Problem Statement

OwlBear is attacking a village. The village has n cannons, each dealing a_i damage. At the k-th second, the OwlBear is protected from the cannon at index (*k*-1) mod n. Given q queries, each with a damage threshold h, find the minimum number of seconds required to deal at least h damage.

Analysis

The key idea is to precompute the prefix sums of the damage dealt in each second, excluding the blocked cannon. Let sum be the total damage all cannons can deal in one second. Then, the damage dealt in the i-th second is sum - a[i % n]. We can create a prefix sum array p where p[i] stores the total damage dealt from second 1 to second i.

To answer a query with damage h, we can first calculate how many full cycles of n seconds are needed. This can be done by ans = h / p[n-1]. The remaining damage is h -= (ans * p[n-1]). Then, we multiply ans by n to get the number of seconds in full cycles. If there is still remaining damage (h > 0), we use binary search (specifically lower_bound) on the prefix sum array p to find the minimum number of additional seconds needed.

Solution

1. Read n and the damage array a.
2. Calculate the total damage sum and create the prefix sum array p where p[i] = sum - a[i] and accumulate the prefix sums.
3. For each query h:
   • Calculate the number of full cycles: ans = h / p[n-1].
   • Update the remaining damage: h -= (ans * p[n-1]).
   • Multiply ans by n.
   • If h > 0, use lower_bound on p to find the index of the first value greater than or equal to h. Add this index + 1 to ans to get the final answer.

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tc;
    cin >> tc;
    while (tc--) {
        int n;
        cin >> n;
        vector<ll> a(n), p(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        ll sum = 0;
        for (int i = 0; i < n; i++) sum += a[i];
        for (int i = 0; i < n; i++) p[i] = sum - a[i];
        for (int i = 1; i < n; i++) p[i] += p[i - 1];
        int q;
        cin >> q;
        while (q--) {
            ll h;
            cin >> h;
            ll ans = h / p[n - 1];
            h -= (ans * p[n - 1]);
            ans *= n;
            if (h) ans += lower_bound(p.begin(), p.end(), h) - p.begin()+1;
            cout << ans << '\n';
        }
    }
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

We can set $$$a_{i,j} = a_{j,i} = i + j$$$ for $$$i \neq j$$$, and set $$$a_{i,i} = 2$$$ for all $$$1 \le i \le n$$$.

Now, if $$$n$$$ is even, all conditions are met.

If $$$n$$$ is odd, the XOR of all elements is $$$2$$$. To balance out that $$$2$$$, we can add $$$2$$$ to $$$a_{3,1}$$$.

We set $$$a_{i,j}$$$ as the minimum prime factor of (i+j).

Now, if $$$n$$$ is even, all conditions are met.

If $$$n$$$ is odd, the XOR of all elements is $$$2$$$. There are $$$2$$$ cases:

• $$$n \le 17$$$. In this case we change $$$a_{1,1}$$$ to $$$4$$$ and $$$a_{2,2}$$$ to $$$6$$$.

• $$$n > 17$$$. In this case we change $$$a_{17,18}$$$ from $$$5$$$ to $$$7$$$.

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

int main(){

	ios_base::sync_with_stdio(false); cin.tie(NULL);

	int t;
	cin>>t;

	while(t--){

		int n;
		cin>>n;

		vector<vector<int>> a(n+1,vector<int>(n+1,0));

		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j) a[i][j] = 2;
				else a[i][j] = i+j;
			}
		}

		if(n&1){
			a[3][1] = 6;
		}

		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++) cout << a[i][j] << ' ';
			cout << endl;
		}

	}
	
	return 0;
}

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define mod  1000000007
#define mod2 998244353
#define ll long long
#define bl __int128_t
#define pb push_back
#define all(v) v.begin(),v.end()
#define bs binary_search
#define rall(v) v.rbegin(),v.rend()
#define lb lower_bound
#define ub upper_bound
#define pl pair<ll,ll>
#define f(i,n) for(ll i=0;i<n;i++)
#define inp(a,n) vector<ll> a(n); f(i,n) cin>>a[i]
#define pyes cout<<"YES\n"
#define pno cout<<"NO\n"
using Mat = array<array<ll,2>,2>;
 
#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("popcnt")
 
ll power(ll x,ll y,ll z=LLONG_MAX){
	ll res=1;
	while(y>0){
		if(y%2) res=(res*x)%z;
		y/=2;
		if(y) x=(x*x)%z;
	}return res%z;
}
 
ll gcd(ll a,ll b,ll& x,ll& y){
	x=1,y=0;
	ll x1=0,y1=1,a1=a,b1=b;
	while(b1){
		ll q=a1/b1;
		tie(x,x1)=make_tuple(x1,x-q*x1);
		tie(y,y1)=make_tuple(y1,y-q*y1);
		tie(a1,b1)=make_tuple(b1,a1-q*b1);
	}return a1;
}
 
#define MX 1e4
vector<ll> spf(MX+2,1);
vector<ll> gpf(MX+2,0);
void sieve(){
	spf[0]=0;
	for(ll i=2;i<3;i++){
		if(spf[i]==1){
			for(ll j=i;j<MX+1;j+=i) if(spf[j]==1) spf[j]=i;
		}
	}for(ll i=3;i<MX+1;i+=2){
		if(spf[i]==1){
			for(ll j=i;j<MX+1;j+=i) if(spf[j]==1) spf[j]=i;
		}
	}for(ll i=2;i<=MX;i++) if(gpf[i]==0) for(ll j=i;j<=MX;j+=i) gpf[j]=i;
	return; 
}
 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll t=1,i,j,n,m,z=1e9+7,z2=998244353,k,x,y,q;
	sieve(); // for SPF
	cin>>t;
	ll tt=t;
	string s,s2;
	while(tt--){
		cin>>n;
		assert(n!=1ll);
		vector<vector<ll>> a(n+1ll,vector<ll>(n+1ll,0ll));
		f(i,n) f(j,n) a[i+1][j+1] = spf[i+j+2ll];
		if(n%2ll == 1ll){
			if(n>18){
				a[17][18] = 7;
			}
			else{
				a[2][2] = 4ll;
				a[3][3] = 6ll;
			}
		}
		f(i,n){
			f(j,n) cout<<a[i+1][j+1]<<' ';
			cout<<'\n';
		}
	}
	return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

There are only $$$n$$$ possible different shifts.Let's calculate cost for each of them in O(1).

Assume one-based indexing for array.
Let cost[i] represent the cost of the array after i shifts.

Initial cost:
cost[0] = 1*a1 + 2*a2 + ... + n*an

cost after first shift:

Rewriting cost[1] in terms of cost[0]

cost after second shift:

Rewriting cost[2] in terms of cost[1]

The generalized formula cost[i] from cost[i-1] terms :

Why the generalized formula is correct?

Using this formula, we can compute the cost for all shifts in O(1) per shift and take minimum among all, resulting in an overall complexity of O(n).

Let's take

$$$ cost_0 = 1 * a_1 + 2 * a_2 + ... + n * a_n $$$

$$$ sum = a_1 + a_2 + ... + a_n $$$

for now let's assume no updates on array ( i.e NO query 1 ( static array ) ). In easy version, we know for i>=1

$$$ cost_i = cost_{i-1} - sum + n * a_i $$$

$$$cost_i$$$ in terms of $$$cost_{i-2}$$$ :

If we continue this, we can express the cost at the i-th shift in terms of the 0-th shift:

Now, if there are updates in the array, the formula for the cost is modified. When an update occurs at inddex $$$ind$$$ , we modify the initial cost as follows:

let's say,

prev = $$$a_{ind}$$$ before update

curr = $$$a_{ind}$$$ after update

we modify the initial cost as follows:

The sum also changes:

To efficiently manage the updates and calculate the prefix sum, we can use Fenwick tree or segment tree (You can learn more about it https://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/ ).

Thus, the final formula after k shifts, considering updates, is:

Time Complexity: $$$ O((n+q)*logn) $$$

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

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    long long t;
    cin>>t;
 
    while(t--)
    {
        long long n;
        cin>>n;
        long long a[n];
        long long sum=0;
        long long ans=0;
        for(long long i=0;i<n;i++)
        {
            cin>>a[i];
            sum+=a[i];
            ans+=((i+1)*a[i]);
        }
 
        long long cost=ans;
        for(long long i=0;i<n;i++) 
        {
            cost=cost-sum+n*a[i];
            ans=min(ans,cost);
        }
        cout<<ans<<"\n";
    }
 
    return 0;
}

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

long long BIT[200000]={0}, a[200000]={0}, n;
void update(long long x, long long delta)
{
      for(; x <= n; x += x&-x)
        BIT[x] += delta;
}
long long query(long long x)
{
     long long sum = 0;
     for(; x > 0; x -= x&-x)
        sum += BIT[x];
     return sum;
}

int main() {

    long long t;
    cin>>t;
    while(t--) 
    {
        cin>>n;
        long long cost=0;
        long long sum=0;
        for(long long i=0;i<n;i++)
        {
            cin>>a[i];
            update(i+1,a[i]);
            cost+=((i+1)*a[i]);
            sum+=a[i];
        }

        long long q;
        cin>>q;

        while(q--)
        {
            long long ty;
            cin>>ty;
            if(ty==1)
            {
                long long ind,x;
                cin>>ind>>x;
                cost-=((ind)*(a[ind-1]));
                sum+=(x-a[ind-1]);
                update(ind,x-a[ind-1]);
                a[ind-1]=x;
                cost+=((ind)*(a[ind-1]));
            }
            else
            {
                long long k;
                cin>>k;
                k%=n;
                cout<<cost-(k)*(sum)+n*(query(k))<<"\n";
            }
        }

        for(int i = 0; i < n; i++) update(i + 1, -a[i]);
    }

    return 0;
}

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define mod  1000000007
#define mod2 998244353
#define ll long long
#define bl __int128_t
#define pb push_back
#define all(v) v.begin(),v.end()
#define bs binary_search
#define rall(v) v.rbegin(),v.rend()
#define lb lower_bound
#define ub upper_bound
#define pl pair<ll,ll>
#define f(i,n) for(ll i=0;i<n;i++)
#define inp(a,n) vector<ll> a(n); f(i,n) cin>>a[i]
#define pyes cout<<"YES\n"
#define pno cout<<"NO\n"
using Mat = array<array<ll,2>,2>;
 
#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("popcnt")
 
ll power(ll x,ll y,ll z=LLONG_MAX){
    ll res=1;
    while(y>0){
        if(y%2) res=(res*x)%z;
        y/=2;
        if(y) x=(x*x)%z;
    }return res%z;
}
 
ll gcd(ll a,ll b,ll& x,ll& y){
    x=1,y=0;
    ll x1=0,y1=1,a1=a,b1=b;
    while(b1){
        ll q=a1/b1;
        tie(x,x1)=make_tuple(x1,x-q*x1);
        tie(y,y1)=make_tuple(y1,y-q*y1);
        tie(a1,b1)=make_tuple(b1,a1-q*b1);
    }return a1;
}
 
template<class T, class U>
// T -> node, U->update.
struct Lsegtree{
    vector<T>st;
    vector<U>lazy;
    ll n;
    T identity_element; // related to query
    U identity_update;  // related to update
    Lsegtree(ll n, T identity_element, U identity_update)
    {
        this->n = n;
        this->identity_element = identity_element;
        this->identity_update = identity_update;
        st.assign(4*n,identity_element);
        lazy.assign(4*n, identity_update);
    }
    T combine(T l, T r)
    {
        // change this function as required.
        // related to query
        T ans = l + r;
        return ans;
    }
    void buildUtil(ll v, ll tl, ll tr, vector<T>&a)
    {
        if(tl == tr)
        {
            st[v]=a[tl];
            return;
        }
        ll tm = (tl + tr)/2;
        buildUtil(2*v + 1, tl, tm,a);
        buildUtil(2*v + 2,tm+1,tr,a);
        st[v] = combine(st[2*v + 1], st[2*v + 2]);
    }
    // change the following 2 functions, and you're more or less done.
    T apply(T curr, U upd, ll tl, ll tr)
    {   
        // related to update and query
        T ans = (upd)*(tr-tl+1);
        return ans;
    }
    U combineUpdate(U old_upd, U new_upd, ll tl, ll tr)
    {   
        // related to update
        U ans = old_upd;
        ans=(new_upd);
        return ans;
    }  
    void push_down(ll v, ll tl, ll tr)
    {
        if(lazy[v] == identity_update)return;
        st[v] = apply(st[v], lazy[v], tl, tr);
        if(2*v + 2 < 4*n)
        {
            ll tm = (tl + tr)>>1;
            lazy[2*v + 1] = combineUpdate(lazy[2*v+1], lazy[v], tl, tm);
            lazy[2*v + 2] = combineUpdate(lazy[2*v+2], lazy[v], tm+1,tr);            
        }
        lazy[v] = identity_update;
    }
    T queryUtil(ll v, ll tl, ll tr, ll l, ll r)
    {
        push_down(v,tl,tr);
        if(l > r)return identity_element;
        if(tr < l or tl > r)
        {
            return identity_element;
        }
        if(l <= tl and r >= tr)
        {
            return st[v];
        }
        ll tm = (tl + tr)>>1;
        return combine(queryUtil(2*v+1,tl,tm,l,r), queryUtil(2*v+2,tm+1,tr,l,r));
    }
    void updateUtil(ll v, ll tl, ll tr, ll l, ll r, U upd)
    {
        push_down(v,tl,tr); 
        if(tr < l or tl > r)return;
        if(tl >=l and tr <=r)
        {
            lazy[v] = combineUpdate(lazy[v],upd,tl,tr);
            push_down(v,tl,tr);
        }
        else
        {
            ll tm = (tl + tr)/2;
            updateUtil(2*v+1,tl,tm,l,r,upd);
            updateUtil(2*v+2,tm+1,tr,l,r,upd);
            st[v] = combine(st[2*v + 1], st[2*v+2]);
        }
    }
    void build(vector<T>a)
    {
        assert(a.size() == n);
        buildUtil(0,0,n-1,a);
    }
    T query(ll l, ll r)
    {
        return queryUtil(0,0,n-1,l,r);
    }
    void update(ll l,ll r, U upd)
    {
        updateUtil(0,0,n-1,l,r,upd);
    }
    ll find_ind(ll v,ll tl,ll tr,ll x){
        // have to store maximums for this to work
        if(st[v]>x) return 0;
        if(tl==tr) return tl;
        ll tm=(tl+tr)/2;
        if(st[v+v+1]<=x) return find_ind(v+v+1,tl,tm,x);
        else return find_ind(v+v+2,tm+1,tr,x-st[v+v+1]);
    }
};
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll t=1,i,j,n,m,z=1e9+7,z2=998244353,k,x,y,q;
    // sieve(); // for SPF
    cin>>t;
    ll tt=t;
    string s,s2;
    while(tt--){
        ll n;
        cin>>n;
        inp(a,n);
        ll sum = accumulate(all(a),0ll);
        ll val = 0ll;
        f(i,n) val += ((i+1)*a[i]);
        Lsegtree<ll,ll> sega(n,0ll,LLONG_MIN);
        sega.build(a);
 
        ll q;
        cin>>q; 
        while(q--){
            ll x;
            cin>>x;
            if(x==1ll){
                ll ind,p;
                cin>>ind>>p;
                ind--;
                sega.update(ind,ind,p);
                sum += (p-a[ind]);
                val += ((ind+1)*(p-a[ind]));
                a[ind] = p;
            }
            else{
                ll k;
                cin>>k;
                k %= n;
                ll ans = val;
                if(k>0ll){
                    ans += (n*sega.query(0ll,k-1ll));
                    ans -= (k*sum);
                }
                cout<<ans<<'\n';
            }
        }
    }
    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Solution 1:

This algorithm is a randomized algorithm.

We randomly select two fixed points $$$x$$$ and $$$y$$$, then for all $$$z \neq x, y$$$, query "? $$$x$$$ $$$y$$$ $$$z$$$". If the result is 0, it means $$$z$$$ and $$$x$$$ are on the same side of $$$y$$$; otherwise, $$$z$$$ and $$$x$$$ are on different sides of $$$y$$$.

Thus, we use $$$y$$$ as the pivot and partition the elements into the left and right halves. To determine which side is the actual left half, we need to perform type $$$1$$$ operation once, (this is only required in the first partitioning step. After determining the correct position of $$$y$$$, no more operations of this type are needed).

Once we know the correct position of $$$y$$$, we can recursively solve the left and right halves.

You might have already noticed that this is essentially the process of quick sort. Therefore, the complexity proof is identical to that of quicksort.

Solution 2:

This algorithm is a deterministic algorithm.

If we can determine the value of $$$p[1]$$$, then we can perform a comparison "? $$$p[1]$$$ $$$x$$$ $$$y$$$", where we compare two numbers.

The method to determine $$$p[1]$$$ is given by the following code:

int u = 1, v = 2;
for (int i = 3; i <= n; i++) {
    int res = ask(u, i, v);
    if (!res) {
        res = ask(u, v, i);
        if (res) v = i;
        else u = i;
    }
}
cout << "1 " << u << ' ' << v << endl;
int res;
cin >> res;
if (!res) swap(u, v);

After determining $$$p[1]$$$, you can solve the problem using any $$$O(n \log n)$$$ sorting algorithm.

#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=0;
const ll  INF=2147483647;
int T,n,keypos;
int p[N];
/*
 // 创建随机数生成器
std::random_device rd; // 获得随机种子
std::mt19937 g(rd());  // 使用Mersenne Twister引擎
*/

void init()
{
    srand(time(0));
    cin>>n;
    keypos=0;
}

int ask1(int x,int y)
{
    int t;
    cout<<"1 "<<x<<" "<<y<<"\n";
    cout.flush();
    cin>>t;
    return t;
}

int ask2(int x,int y,int z)
{
    int t;
    cout<<"2 "<<x<<" "<<y<<" "<<z<<"\n";
    cout.flush();
    cin>>t;
    return t;
}

void work(int L,int R,vector<int> &v)
{
    if(L>R) return ;
    if(L==R)
    {
        p[L]=v[0];
        return ;
    }
    if(L==R-1)
    {
        if(R<keypos)
        {
            if(!ask2(v[0],v[1],p[keypos])) swap(v[0],v[1]);
        }
        else
        {
            if(!ask2(v[1],v[0],p[keypos])) swap(v[0],v[1]);
        }
        p[L]=v[0];
        p[R]=v[1];
        return ;
    }
    // 使用std::shuffle打乱vector
    int midpos;
    vector<int> lhalf,rhalf;

    //shuffle(v.begin(), v.end(), g);
    random_shuffle(v.begin(), v.end());
    lhalf.push_back(v[0]);
    /*
    cout<<"L="<<L<<" R="<<R<<"\n shuffled v[]=";
    for(int i=0;i<v.size();i++) cout<<v[i]<<' ';
    cout<<"\n";
    //
    //
    cout<<"lhalf[]=";
    for(int i=0;i<lhalf.size();i++) cout<<lhalf[i]<<' ';
    cout<<"\n";
    */
    for(int i=2;i<v.size();i++)
    {
        if(ask2(v[0],v[1],v[i])) rhalf.push_back(v[i]);
        else lhalf.push_back(v[i]);

        /*
        cout<<"lhalf[]=";
        for(int i=0;i<lhalf.size();i++) cout<<lhalf[i]<<' ';
        cout<<"\n";
        */
    }
    if(!keypos)
    {
        if(!ask1(v[0],v[1])) swap(lhalf,rhalf);
        midpos=lhalf.size()+1;
        p[midpos]=v[1];
        keypos=midpos;
        //
        //printf("keypos=%d\n",keypos);
        //
    }
    else
    {
        if(R<keypos)
        {
            if(!ask2(v[0],v[1],p[keypos])) swap(lhalf,rhalf);
        }
        else
        {
            if(!ask2(v[1],v[0],p[keypos])) swap(lhalf,rhalf);
        }
        midpos=lhalf.size()+L;
        p[midpos]=v[1];
    }
    /*
    cout<<"lhalf[]=";
    for(int i=0;i<lhalf.size();i++) cout<<lhalf[i]<<' ';
    cout<<"\n";
    cout<<"rhalf[]=";
    for(int i=0;i<rhalf.size();i++) cout<<rhalf[i]<<' ';
    cout<<"\n";
    */
    work(L,midpos-1,lhalf);
    work(midpos+1,R,rhalf);
}

void solve()
{
    vector<int> v;
    for(int i=1;i<=n;i++) v.push_back(i);
    work(1,n,v);
    cout<<"! ";
    for(int i=1;i<=n;i++) cout<<p[i]<<(i==n?'\n':' ');
    cout.flush();
}

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

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

int bruteforce()
{
    return 0;
}

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

int 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;
}

// Problem: G. Interactive is Fun
// Contest: Codeforces - TheForces Round #39 (DIV4-Forces)
// URL: https://codeforces.me/gym/105651/problem/G
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n; cin >> n;
	vector<int> p(n + 1);
	for (int i = 1; i <= n; i++) p[i] = i;
	auto ask = [&](int x, int y, int z) -> bool {
		cout << "2 " << x << ' ' << y << ' ' << z << endl;
		int res; cin >> res;
		return res;
	};
	int u = 1, v = 2;
	for (int i = 3; i <= n; i++) {
		int res = ask(u, i, v);
		if (!res) {
			res = ask(u, v, i);
			if (res) v = i;
			else u = i;
		}
	}
	cout << "1 " << u << ' ' << v << endl;
	int res; cin >> res;
	if (!res) swap(u, v);
	stable_sort(p.begin() + 1, p.end(), [&](int i, int j) {
		return ask(u, i, j);
	});
	cout << "! ";
	for (int i = 1; i <= n; i++) cout << p[i] << " ";
	cout << endl;
	return;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		solve();
	}
}

Amazing problem: Good problem: Average problem: Bad problem: Didn't solve:

Note that performing an operation is always optimal as it won't decrease the answer.

At first, lets find the number of good subarrays before applying the operation. For this, the condition is $$$a_l + a_{l+1} ... + a_r >= k*(r-l+1)$$$ which is $$$pre[r] - k*r >= pre[l-1] - k*(l-1)$$$. So we can make a new array $$$b$$$ where $$$b_i = pre[i] - k*i$$$ and the initial number of good subarrays is equal to the number of inversions in the array $$$b$$$.

Now, lets say we increment $$$a_i$$$ by $$$1$$$ for some $$$i$$$, then the additional good subarrays formed should have their left boundary to the left of $$$i$$$ or equal to $$$i$$$ and their right boundary to the right of $$$i$$$ or equal to $$$i$$$ $$$(i.e., l \le i \le r)$$$ and $$$b_r = b_{l-1} - 1$$$. If we have the number of additional good subarrays when the operation is performed at $$$i^{th}$$$ position, we can easily find the number of additional good subarrays when the operation is performed at $$$(i+1)^{th}$$$ position using a map.

Finally we take maximum over all positions and add it to the initial answer.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long

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

    int t;
    cin >> t;

    while (t--) {
        ll n, k;
        cin >> n >> k;

        vector<ll> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        vector<ll> b(n + 1, 0ll);
        for (int i = 0; i < n; i++) {
            b[i + 1] = b[i] + (a[i] - k);
        }

        ll ans = 0;

        oms<ll> inv;
        inv.insert(0);

        for (int i = 0; i < n; i++) {
            ans += inv.order_of_key(b[i + 1] + 1);
            inv.insert(b[i + 1]);
        }

        ll mx = 0;
        map<ll, ll> left, right;

        for (int i = 0; i < n; i++) {
            right[b[i + 1]]++;
        }

        left[0]++;
        ll val = 0;

        for (int i = 0; i < n; i++) {
            if (b[i + 1] == -1) {
                val++;
            }
        }

        mx = val;

        for (int i = 2; i <= n; i++) {
            val += right[b[i - 1] - 1];
            val -= left[b[i - 1] + 1];

            left[b[i - 1]]++;
            right[b[i - 1]]--;

            mx = max(mx, val);
        }

        ans += mx;
        cout << ans << '\n';
    }
    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Assume that the number of colors $$$c$$$ is fixed. Let $$$mx[i][j]$$$ represent the length of the continuous path ending at node $$$i$$$ with color $$$j$$$. How do we construct $$$mx$$$?

Let's try some approaches. For the connected component formed by the first $$$k$$$ nodes, we can use color 1 for all of them. In this case, the $$$i$$$-th node's $$$mx$$$ array (for $$$1 \le i \le k$$$) would be:
$$$mx[i] = [ i-1 ,0, \dots, 0]$$$.

For the $$$(k+1)$$$-th node, we can use color 2 to connect the connected component formed by the first $$$k-1$$$ nodes. Thus, the $$$(k+1)$$$-th node's $$$mx$$$ array would be:
$$$mx[k+1] = [0, 1, 0, \dots, 0]$$$.

For the $$$(k+2)$$$-th node, we can use color 2 to connect the connected component formed by the first $$$k-1$$$ nodes and color 1 to connect node $$$k$$$. In this case, the $$$(k+2)$$$-th node's $$$mx$$$ array would be:
$$$mx[k+2] = [1, 1,0, \dots, 0]$$$.

At this point, you might realize: The $$$i$$$-th node's $$$mx$$$ array is exactly the $$$(i-1)$$$ in base $$$k$$$ as a mask!

Claim $$$1$$$: for two indices $$$i$$$ and $$$j(i<j)$$$, $$$mx[i] \neq mx[j]$$$.

Proof $$$1$$$: if we use color $$$k$$$ to connect node $$$i$$$ and $$$j$$$, $$$mx[i][k]+1=mx[j][k]$$$ must hold.

So we can assign values to each node's $$$mx$$$ array using a $$$k$$$-base mask from $$$0$$$ to $$$n-1$$$, which gives us a lower bound on the answer.

Claim $$$2$$$: we can always reach this lower bound.

Proof $$$2$$$: for two indices $$$i$$$ and $$$j(i<j)$$$, find $$$k$$$ such that $$$mx[i][k]<mx[j][k]$$$, then use color $$$k$$$ to connect node $$$i$$$ and $$$j$$$.

277722333

• $$$a[1][2]=a[2][1]=a[n-1][m]=a[n][m-1]='.'$$$ must hold.

• We can simply find the shortest path using BFS.

• Robot B can follow behind Robot A. That is, Return to $$$(1,1)$$$ in two steps, then "track" A. So the lower bound of our answer is the shortest path length+2.

• The only remaining problem is: how to find two disjoint shortest paths?

To to find two disjoint shortest paths, we have a classic idea: only walk along the edge of the shortest path tree.

That is, note $$$dis[x]$$$ as the distance from $$$s$$$ to $$$x$$$, we only remain edges $$$u \rightarrow v$$$ such that $$$dis[u]+1=dis[v]$$$.

Official editorial said:

Once all cells on the shortest path are known, sort them by their distance to $$$(1, 1)$$$, i.e., $$$d_1(x, y)$$$ values. Now, if there’s any “level” of the shortest path that contains exactly one cell, every shortest path much pass through this cell and two disjoint paths cannot exist. Otherwise, a valid pair of paths will always exist.

I am confused about how to prove this. After thinking, I came up with a rigorous proof using the maximum flow minimum cut theorem.

Since each node can be visited at most once, we need to split node $$$x$$$ into $$$x$$$ -> $$$x'$$$ when constructing the flow graph. Let's say $$$dis[x]=dis[x']$$$.

What I want to prove is that if the number of nodes at all "levels" is greater than $$$1$$$ (except for $$$s$$$ and $$$t$$$), then for all cuts, the number of cut edges is always greater than $$$1$$$.

Let $$$D[i]$$$ be the set of all nodes $$$x$$$ such that $$$dis[x] = i$$$.

Assume we can find a $$$D[i]$$$ satisfying there are two nodes $$$u,v∈D[i]$$$, such that $$$u∈S$$$ and $$$v∈T$$$ (let's call it "impure"). According to our assumption, there are at least two pairs of $$$x$$$->$$$x'$$$ in $$$D[i]$$$. We will discuss three cases.

• Case $$$1$$$: $$$x$$$ and $$$x'$$$ are from different $$$S/T$$$ sets. In this case, $$$x$$$->$$$x'$$$ is already a cut edge.

• Case $$$2$$$: $$$x$$$ and $$$x'$$$ are both from $$$S$$$. In this case, by following the successors of $$$x'$$$, we can always find a cut edge.

• Case $$$3$$$: $$$x$$$ and $$$x'$$$ are both from $$$T$$$. In this case, by following the predecessors of $$$x$$$, we can always find a cut edge.

In this way, we can always find at least two different cutting edges. Q.E.D.

If we can't find "impure" $$$D[i]$$$, this case is easier — we can find two cutting edges between some $$$D[i]$$$ and $$$D[i+1]$$$. The proof are left to you :)

Note $$$|D[i]|$$$ as the number of nodes of $$$D[i]$$$($$$s$$$ and $$$t$$$ are excluded). If $$$min(D[i])=k$$$, can we find $$$k$$$ disjoint shortest path for any $$$k$$$?

No. It only holds when $$$k=2$$$.

The following is the counter case for $$$k=3$$$:

After retaining only the edges on the shortest path tree, we can run a maximum flow algorithm to check if the maximum flow is $$$2$$$. Due to the special nature of the graph, the time complexity is equivalent to performing two BFS traversals on the graph.

We construct the Cartesian tree of the array, where $$$maxa$$$ is the root.

We can think of the process of merging numbers as one slime eating another slime.

If you are at slime $$$a[x]$$$, what would you do? First, you can definitely eat the subtree you are in. After that, you try to eat your parent. If you can do so ($$$subtreesum[x] \ge a[fa[x]]$$$), it is equivalent to being in the position of slime $$$fa[x]$$$. Otherwise, mark the edge $$$(x, fa[x])$$$ as a "blocking edge." We use DSU to link all non-blocking edges, and the size of the set containing the root is the answer.

Maintain the Tree with Data Structures.

We first construct the Cartesian tree for $$$a[1...n]$$$, using a segment tree to maintain its Euler sequence. Some arrays and DSU also needed. Afterward, we "clear" it—set all values in the segment tree to 0, and disconnect every point in the DSU. Then, we add the nodes one by one.

We can also use arrays $$$fa$$$, $$$lc$$$, and $$$rc$$$ to maintain the current parent-child relationships in the tree. When adding $$$a[i]$$$, we set the value at position $$$i$$$ in the segment tree to $$$a[i]$$$ and check whether the edge between $$$i$$$ and its child(at most two children) is a "blocking edge". If it is not, we use DSU to merge $$$i$$$ and $$$a[i]$$$. This step is not hard.

Additionally, all edges on the path from $$$a[i]$$$ to the root may change from being "blocking edges" to "non-blocking edges" (but "non-blocking edges" will never become "blocking edges"—think about why). We check all edges on the path from $$$a[i]$$$ to the root and update them using DSU.

In DSU, for the nodes in the same set, we can maintain the point with the smallest depth in that set. This allows us to quickly skip over many consecutive "non-blocking edges".

For a "blocking edge", it may be checked many times. If there are many "blocking edges" on a path to the root, and after checking they do not change, could we check $$$O(n^2)$$$ times?

No. For a path to the root, there can be at most $$$O(\log n)$$$ "blocking edges."

Why? Let's review: a "blocking edge" $$$(x, fa[x])$$$ is an edge that satisfies $$$subtreesum[x] < a[fa[x]]$$$. Each time we pass through a "blocking edge", the subtree sum at least doubles. Therefore, there can be at most $$$O(\log n)$$$ "blocking edges."

291785878

Consider a fixed interval $$$[l, r]$$$.

We find that if $$$a[r]$$$ is neither the maximum nor the minimum value, then performing $$$r--$$$ will increase the answer by $$$1$$$.

Thus, $$$a[r]$$$ must either be the maximum value or the minimum value; similarly, the same holds for $$$a[l]$$$.

We only need to calculate the answers where $$$a[r]$$$ is the maximum value and $$$a[l]$$$ is the minimum value. Afterward, we reverse the array $$$a$$$ and calculate again.

Consider a fixed $$$r$$$. We can separate the terms related to $$$r$$$ and those related to $$$l$$$, obtaining the following answer:

Maintaining "$$$a[l]$$$ is the minimum value in $$$a[l...r]$$$" seems difficult. Can we change it to "$$$1 \leq l \leq r$$$"? Yes, we can. Although this will count some "invalid" answers, these answers will never be the maximum value (think why).

Consider using a segment tree. If we have information for $$$[L, M]$$$ and $$$[M+1, R]$$$, how can we merge this information to obtain the information for $$$[L, R]$$$?

To find the answer that spans two intervals:

$$$\max_{r \in [M+1, R]} (a[r] - r) - \min_{l \in [L, M]} (a[l] - l)$$$

This can be maintained on a segment tree.

299719227

Since $$$m$$$ is small, we can enumerate $$$2^m$$$ cases and record their AND values.

Thus, we can easily obtain an array $$$mn[i][j]$$$: the minimum value of $$$a[i]$$$ after $$$j$$$ operations.

DP seems hard. How to solve this?

We observe that for a fixed $$$i$$$, $$$mn[i][j]$$$ is a convex function. In other words, $$$mn[i][j] - mn[i][j+1]$$$ is monotonically decreasing.

Thus, the problem is equivalent to a classic problem: choosing the top $$$k$$$ largest values from $$$n$$$ monotonically decreasing sequences. This part is the same as an old problem https://codeforces.me/contest/1428/problem/E.

We only need to focus on the highest changing bit. It is easy to see that, as $$$j$$$ increases, the highest changing bit decreases.

Formally, define

as the highest differing bit between x and y. We have:

Consider a proof by contradiction. Suppose:

Let

, and we can find an $x[k]$ such that the $$$b$$$-th bit of $$$x[k]$$$ is $$$0$$$.

We insert this $$$x[k]$$$ into the first $$$(j+1)$$$ operations, and the result will be strictly smaller than the current $$$mn[i][j+1]$$$. This contradicts the minimality of $$$mn[i][j+1]$$$.

302098411

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

In other exciting news:

• We've just launched our official Telegram channel! We invite you to join us there as well, so we can expand our community and conquer Telegram alongside Codeforces and Discord! 💪

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 $$$1$$$ tree problem.

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