For all the balls to pass through the pipe, we can be sure that if the ball with the maximum radius can pass through the pipe then others will easily pass through it. So, we find the maximum radius among the balls and check whether it is possible to make a cut through the cylinder to allow that ball to pass, So the radius of the cylinder must be strictly less than the maximum radius of a ball.

#include <bits/stdc++.h>
using namespace std;
#define speed ios::sync_with_stdio(false);cin.tie(0);
using i64 = long long;
#define ull  long long
#define pb push_back
#define all(x) (x).begin(), (x).end()

void solve()
{
    int n,r;
    cin>>n>>r;
    int m=0;
    for(int i=0;i<n;i++)
    {
        int x;cin>>x;m=max(m,x);
    }
    cout<<((m<r)?m:-1)<<endl;
}

signed main() {
   speed
   int t=1;
   cin>>t;
   while(t--)
   {
      solve();
   }
   return 0;
}

We have to find the number of anti-palindromic substrings of length $$$4$$$. So, we will simply consider all substring starting from indexes $$$[0,3]$$$ upto $$$[n-4,n-1]$$$. If the length of the substring will be less than $$$4$$$, then the answer will automatically turn out to be zero.

#include <bits/stdc++.h>
using namespace std;
#define speed ios::sync_with_stdio(false);cin.tie(0);
#define ull  long long

void solve()
{
    string s;
    cin>>s;
    int n=s.length();
    int cnt=0;
    for(int i=0;i<n-3;i++)
    {
        if(s[i]!=s[i+3]&& s[i+1]!=s[i+2])cnt++;
    }
    cout<<cnt<<endl;
}

signed main() {
   speed
   int t=1;
   cin>>t;
   while(t--)
   {
      solve();
   }
   return 0;
}

We have to maximize $$$ \left( {A_i - A_j} \right) \times A_k $$$. So for every index $$$j$$$ from $$$2$$$ to $$$n-1$$$, we have to find the maximum element $$$A_i$$$ from the left side $$$(1 \le i \lt j)$$$ and the maximum element $$$A_k$$$ $$$(j \lt k \le n)$$$ from the right side. Which can be done using prefix maximum and suffix maximum. Then we will traverse the array from $$$2$$$ to $$$n-1$$$ and our answer will be $$$max(answer, (pref[j-1] - A[j]) \times suffix[j+1])$$$.

If final answer is negative, then we will output $$$0$$$.

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

typedef long long ll;
#define f(i, x, n) for (ll i = x; i < n; i++)
#define rf(i, x, n) for (ll i = x; i >= n; i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
const ll p = 1e9 + 7;
const ll inf = 1e18;
const ll N = 1e4+5;

void solve() {
    ll n;
    cin>>n;
    vector<ll> a(n);
    f(i,0,n) cin>>a[i];
    vector<ll> pref(n), suf(n);
    f(i,0,n) {
        pref[i]=max(i==0?a[0]:pref[i-1],a[i]);
    }
    rf(i,n-1,0) {
        suf[i]=max(i==n-1?a[i]:suf[i+1],a[i]);
    }
    ll ans=-inf;
    f(i,1,n-1) {
        ans=max(ans,(pref[i-1]-a[i])*suf[i+1]);
    }
    if(ans<0) ans=0;
    cout<<ans<<'\n';
}   

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t = 1;
    cin >> t;
    for (ll T = 1; T <= t; T++) {
        // cout << "Case " << T << ": ";
        solve();
    }  
    return 0;
}

Lets take a sequence $$$...U_1OU_2...$$$, where $$$U_1$$$,$$$U_2$$$ are segments of unowned lands and $$$O$$$ is segment of owned lands. Then you can give $$$O$$$ and take whole segment $$$U_1OU_2$$$, here you can see overall you have taken $$$U_1$$$ and $$$U_2$$$. So you can take any two consecutive segments of unowned lands and we can maximize it in $$$O(N)$$$ by just brute forcing on string.

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

int main(){
    int n;
    cin>>n;
    string str;
    cin>>str;
    vector<int> lenOfZeroSeg;
    int ans=0;
    for(int i=0;i<n;){
        if(str[i]=='1'){ans++;i++;continue;}
        int cnt=0;
        while(i<n && str[i]=='0'){
            i++;
            cnt++;
        }
        if(cnt!=0)lenOfZeroSeg.push_back(cnt);
    }
    // cout<<lenOfZeroSeg.size()<<endl;
    int mx=0;
    for(int i=0;i<((int)lenOfZeroSeg.size())-1;i++){
        mx=max(mx,lenOfZeroSeg[i]+lenOfZeroSeg[i+1]);
    }
    ans+=mx;
    cout<<ans<<endl;
    return 0;
}

We have to find the number of demons slain by warrior, so we will traverse the tree through dfs and at every non-leaf node we will insert that number of equipment into the set and at the leaf node if we have all the $$$1$$$ to $$$k$$$ equipment (means the size of the set will be equal to $$$k$$$) then we increase the answer by $$$1$$$ and while returning from the leaf node we will erase each non-leaf node's equipment number from the set.

You can see the code for a better understanding.

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

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e18;
const ll N = 2e5+5;

ll n,k,ans;
set<ll> s;
vector<ll> hsh,a;
vector<vector<ll>> g;

void dfs(ll node, ll par) {
    if(node!=1) {
        hsh[a[node]]++;
        s.insert(a[node]);
    }
    for(auto &x : g[node]) {
        if(x!=par) {
            dfs(x,node);
        }
    }
    if(g[node].size()==1) {
        if(s.size()==k) ans++;
    }
    if(hsh[a[node]]==1) s.erase(s.find(a[node]));
    hsh[a[node]]--;
}
    
void solve(){
    cin>>n>>k;
    a.assign(n+1,0);
    hsh.assign(k+1,0);
    g.assign(n+1,{});
    for(ll i=1; i<=n; i++) cin>>a[i];
    for(ll i=1; i<n; i++) {
        ll x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,-1);
    cout<<ans<<'\n';
}
    
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t = 1;
    // cin >> t;
    for (ll T = 1; T <= t; T++) {
        // cout << "case " << T << ": ";
        solve();
    }
    return 0;
}

Here durability simply means number of edges between any nodes, and it breaks on traveling. And we will solve this question for all its component individually, because it anyways takes $$$1$$$ air-travel to move between connected components.

For any connected component, we have two types of nodes: even degree nodes and odd degree nodes.

EVEN DEGREE: When we will air-travel on even degree and break all edges connected to it, we will end up on that node only, so we have to use air travel to go on any other node.

ODD DEGREE: When we will air travel on odd degree and break all edges connected to it, we will end up in some other node than this, and if that is even degree node then by coming in that edge it becomes odd degree(because we have broke one edge and came on that) and this is again case of ODD DEGREE. If we go to any odd degree then it will become even and as we have seen upward we will end up on that node only after breaking all edge, so we have to use air-travel to go to other nodes.

So optimal strategy is to go from one odd degree node to another odd degree node and take all other even degree node on the way. So this will require air-travel equal to half the number of odd degree vertices. If all edges are even we can see, any even degree node as two odd degree nodes and make $$$1$$$ air travel and remove all edges in that component. If any component don't have any edge then no need to air-travel on it.

If you have understood logic then implementation is very easy.

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

const int N=2e5+1;
vector<int> edge[N];
bool vis[N];
int deg[N];
int cnt=0;
int dfs(int ind){
    cnt++;
    int ans=(deg[ind]%2);
    vis[ind]=1;
    for(auto child:edge[ind]){
        if(!vis[child])ans+=dfs(child);
    }
    return ans;
}

int main(){
    int tc;
    cin>>tc;
    while(tc--){
        int n,m;
        cin>>n>>m;
        for(int i=0;i<n;i++){
            vis[i]=0;
            deg[i]=0;
            edge[i].clear();
        }
        for(int i=0;i<m;i++){
            int u,v,w;
            cin>>u>>v>>w;
            edge[u-1].push_back(v-1);
            edge[v-1].push_back(u-1);
            deg[u-1]+=(w%2);
            deg[v-1]+=(w%2);
        }
        int ans=0;
        for(int i=0;i<n;i++){
            if(!vis[i]){
                cnt=0;
                int curans=dfs(i);
                if(curans==0 && cnt!=1)ans++;
                else ans+=(curans/2);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

In this question, first thing to observe is for all continuous three stones $$$i,j$$$ and $$$k$$$, $$$dist(j,k) \gt x-dist(i,j)$$$ and $$$dist(j,k) \le x$$$.

So here we have some constrains on putting stones, i.e we have to put at least $$$1$$$ real stone in following $$$y(y \le x)$$$ stones. Now we can think of DP solution here, having 2-D dp, $$$dp_{i,j}$$$ denoting number of ways to put real stones in total $$$i$$$ stones and with the initial constrain as $$$j$$$. Here constrain $$$j$$$ denotes that first $$$j$$$ stones after $$$1_{st}$$$ stones can't be real.

So for computing $$$dp_{i,j}$$$ our formula will be:

Now because you are reading editorial of this question, it should be easy task to implement it.

#include <bits/stdc++.h>
using namespace std;
 
long long int MOD=1e9+7;
const int N=1e3+1;
int n,x;
long long int dp[N][N];
int func(int stn,int con){
    if(con>=x)return 0;
    if(stn<0){
        return 1;
    }
    if(dp[stn][con]!=-1)return dp[stn][con];
    dp[stn][con]=0;
 
 
    //In O(N^3) loop runs from con to x for all con, but to get it in we will use dp[stn][con+1] and add remaining thing.
    //This is for O(N^2).
    dp[stn][con]=func(stn,con+1);
    if(stn-con-1>=0 || con==x-1)dp[stn][con]+=func(stn-con-1,x-con-1);
    dp[stn][con]%=MOD;
    
    //This is for O(N^3).
    // for(int i=con;i<x;i++){
    //     dp[stn][con]+=func(stn-i-1,x-i-1);
    //     if(stn-i-1<0)break;
    // }
    return dp[stn][con];
}
 
 
int main(){
    cin>>n;
    cin>>x;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            dp[i][j]=-1;
        }
    }
    cout<<func(n-1,0)<<endl;
    return 0;
}

In this question, there are only $$$2$$$ types of chess boards possible, starting with white and starting with black. So we can check this $$$2$$$ cases manually. Another approach is to check that now to adjacent cells have same color.

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    string str[8];
    for(int i=0;i<8;i++){
        cin>>str[i];
    }
    int check1=1,check2=1;
    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            if(((str[i][j]-'0'))!=((i%2)^(j%2))){
                check1=0;
            }
        }
    }
    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            if((str[i][j]-'0')!=((i%2)^(j%2)^1)){
                check2=0;
            }
        }
    }
    if(check1 || check2){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}

For, calculating the population remaining in B1 part, as we know that every person is standing on an integral coordinate, so the number of people remaining will simply be the number of points in the circle, we will simply use the brute force method, i.e., for every possible point with $$$x$$$ ranging from $$$-a$$$ to $$$a$$$ and $$$y$$$ ranging from $$$-a$$$ to $$$a$$$, we will check it whether it is inside the circle (if $$$ x^2 + y^2 \le a^2$$$, then the point is inside the circle). And we will count the number of such points.

#include <iostream>
#include <algorithm>
#include <iterator>
#include <bits/stdc++.h>
using namespace std;
#define speed ios::sync_with_stdio(false);cin.tie(0);
using i64 = long long;
#define ull  long long int

void solve()
{
    int a;
    cin>>a;
    ull count=0;
    for(int i=-a;i<=a;i++)
    {
        for(int j=-a;j<=a;j++)
        {
            if(i*i+j*j<=a*a)count++;
        }
    }
    cout<<count<<endl;
}
int main() {
   speed
   int t=1;
   cin>>t;
   while(t--)
   {
      solve();
   }
   return 0;
}

For this version of the problem, the constraints differ from the previous version and hence the maximum time complexity that the code must have should be less than $$$O(nlogn)$$$, there are two optimized versions of this part, one with time complexity of $$$O(n)$$$ and the other with $$$O(nlogn)$$$. Firstly lets have a look on $$$O(nlogn)$$$ variant, we will divide the problem into $$$4$$$ quarters as each one will have same number of points, finding only for the $$$1^{st}$$$ quarter: We traverse the $$$y$$$ axis from $$$1$$$ to a(adding origin at the end because it should be counted only once) and for $$$x$$$ coordinates, we apply binary search from $$$0$$$ to a finding the last point between $$$0$$$ to a that will be the part of the circle.

Now, taking a look on the $$$O(n)$$$ version: By observing pattern and using math operations, we will get the number of points for any $$$y=i$$$ as $$$\sqrt{n^2-i^2}$$$, so we will sum them up in $$$O(n)$$$ and find the desired answer.

#include <iostream>
#include <algorithm>
#include <iterator>
#include <bits/stdc++.h>
using namespace std;
#define speed ios::sync_with_stdio(false);cin.tie(0);
using i64 = long long;
#define ull  long long int

void solve()
{
    ull a;
    cin>>a;
    ull count=0;
    for(ull i=1;i<=a;i++)
    {
        ull st=0,en=a;
        ull node=-1;
        while(st<en)
        {
            ull mid=(st+en)/2;
            if(mid*mid+i*i<=a*a)
            {
                node=mid;
                st=mid+1;
            }
            else en=mid;   
        }
        count+=node;
    }
    count+=a;
    count*=4;count++;
    cout<<count<<endl;
}
int main() {
   speed
   int t=1;
   cin>>t;
   while(t--)
   {
      solve();
   }
   return 0;
}

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

#define ll long long int

void solve(){
    ll n;   cin>>n;
    ll ans = 0;
    for(ll i=1;i<n;i++){
        ll mx = n*n - i*i;
        ans+=sqrt(mx);
    }
    ans*=4;
    ans+=4*n;
    cout<<ans+1<<endl;
}


int main()
{
    int t; cin>>t;
    while(t--) solve();
    return 0;
}

Firstly we should notice that limits of numbers in array is $$$10^5$$$, so we can calculate and store it.

For calculating any number $$$x$$$, we will calculate by the following formula:

Now we have number of steps for all numbers, now we can calculate answer in $$$O(n)$$$ by iterating over given values.

#include <bits/stdc++.h>
using namespace std;
 
const int N=1e5+1;
bool isp[N];
 
int main(){
    for(int i=0;i<N;i++)isp[i]=1;
    isp[0]=0,isp[1]=0;
    for(long long int i=2;i<N;i++)
    {
        if(isp[i]==0)continue;
        for (long long int j=i*i;j<N;j+=i)isp[j]=0;
    }
    int n;
    cin>>n;
    int a[n],b[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    int val[(int)1e5+1];
    val[0]=0;
    val[1]=0;
    for(int i=2;i<1e5+1;i++){
        val[i]=INT_MAX;
        for(long long int j=1;j*j<=i;j++){
            if(i%j==0 && isp[j]==1)val[i]=min(val[i],val[i-j]+1);
            if(i%j==0 && isp[i/j]==1)val[i]=min(val[i],val[i-(i/j)]+1);
        }
    }
    int valdiff=0;
    for(int i=0;i<n;i++){
        valdiff+=val[a[i]];
        valdiff-=val[b[i]];
    }
    if(valdiff<=0){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}

We can observe that right rotate operation is same as you select any element with index $$$j$$$, remove it and insert it in $$$i^{th}$$$ index. That's why we will select smallest element and place it in sorted position and if there are multiple elements then we will select element which came at last.

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int tc;
    cin>>tc;
    while(tc--){
        int n,k;
        cin>>n>>k;
        string str;
        cin>>str;
        string str2=str;
        vector<int> freq(26,0);
        for(int i=0;i<n;i++){
            freq[str[i]-'a']++;
        }
        sort(str2.begin(),str2.end());
        // cout<<str<<endl;
        // cout<<str2<<endl;
        int j=0;
        for(int i=0;i<n;i++){
            if(k==0){
                break;
            }
            cout<<str2[i];
            freq[str2[i]-'a']--;
            if(str2[i]!=str[j]){
                k--;
            }
            else{
                j++;
                while(j<n && str[j]<str2[i]){
                    j++;
                }
            }
        }
        for(int i=j;i<n;i++){
            if(freq[str[i]-'a']!=0){
                cout<<str[i];
                freq[str[i]-'a']--;
                
            }
        }
        cout<<endl;
    }
}

Let's first calculate that for any node $$$u$$$, $$$size[u]$$$ of is number of nodes between $$$u(real)$$$ and $$$u(image)$$$. We can find this with the help of depth-first-search in $$$O(n)$$$ time complexity.

We can observe that number of topological sorts between $$$u(real)$$$ and $$$u(image)$$$, denoted as $$$ans[u]$$$ is equal to:

We can solve this with recursive coding with the termination condition at leaf node of given tree for which answer is $1$.

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

#define ll long long int
ll modpower(ll n,ll a,ll p){ ll res=1; while(a){ if(a%2) res= ((res*n)%p) ,a--; else n=((n*n)%p),a/=2;} return res;}
const ll N=2e5;
const ll MOD=1e9+7;
vector<int> edge[N];
int sz[N];
ll ans=1;
ll fact[N];
ll ifact[N];

void dfs(int ind,int par){
    sz[ind]=0;
    for(auto z:edge[ind]){
        if(par==z)continue;
        dfs(z,ind);
        sz[ind]+=sz[z];
    }
    ans*=(fact[sz[ind]]);
    ans%=MOD;
    for(auto z:edge[ind]){
        if(z==par)continue;
        ans*=(ifact[sz[z]]);
        ans%=MOD;
    }
    if(sz[ind]==0)sz[ind]++;
    else sz[ind]+=2;
}
 
 
int main(){
    long long i;
    fact[0]=1;
    fact[1]=1;
    for(i=2;i<N;i++){
        fact[i]=fact[i-1]*i;
        fact[i]%=MOD;
    }
    ifact[N-1]=modpower(fact[N-1],MOD-2,MOD);
    for(i=(N-2);i>=0;i--){
        ifact[i]=ifact[i+1]*(i+1);
        ifact[i]%=MOD;
    }
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        edge[u-1].push_back(v-1);
        edge[v-1].push_back(u-1);
    }
    dfs(0,-1);
    cout<<ans<<endl;
    return 0;
}

This problem is purely implementation based. First, we will make two matrices: height and width.

If there are consecutive numbers in a column of the height matrix starting from the index $$$(i,j)$$$ to $$$(i+x,j)$$$ where $$$i+x \le n$$$, then the elements starting from $$$A[i][j]$$$ to $$$A[i+x][j]$$$ will be there in matrix $$$B$$$ probably starting from the different index but they will be arranged vertically and also they will be in the same order as they were in $$$A$$$.

If there are consecutive numbers in a row of the width matrix starting from the index $$$(i,j)$$$ to $$$(i,j+x)$$$ where $$$j+x \le m$$$, then the elements starting from $$$A[i][j]$$$ to $$$A[i][j+x]$$$ will be there in matrix $$$B$$$ probably starting from the different index but they will be arranged horizontally and also they will be in the same order as they were in $$$A$$$.

Now, using these two matrices, we will calculate the maximum area of the largest common sub-matrix using tricky implementation.

You can see the code for a better understanding.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 5;

pair<ll,ll> position[N];

void solve(){
    ll n,m;
    cin>>n>>m;
    ll a[n+5][m+5],b[n+5][m+5];
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            cin>>b[i][j];
            position[b[i][j]]={i,j};
        }
    }
    ll ans=1;
    ll height[n+1][m+1],width[n+1][m+1];
    memset(height,0,sizeof(height));
    memset(width,0,sizeof(width));
    auto up = [&](ll x,ll y){
        return (position[x].first+1==position[y].first && position[x].second==position[y].second);
    };
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            if(i==1) height[i][j]=1;
            else{
                if(up(a[i-1][j],a[i][j])){
                    height[i][j]=height[i-1][j]+1;
                }
                else height[i][j]=1;
            }
        }
    }
    auto right = [&](ll x,ll y){
        return (position[x].first==position[y].first && position[x].second==position[y].second+1);
    };
    for(ll i=1;i<=n;i++){
        for(ll j=m;j>=1;j--){
            if(j==m) width[i][j]=1;
            else{
                if(right(a[i][j+1],a[i][j])){
                    width[i][j]=width[i][j+1]+1;
                }
                else width[i][j]=1;
            }
        }
    }
    vector<ll> L(1005), R(1005);
    for(ll i=1;i<=n;i++){
        ll column=1;
        while(column<=m){
            stack<ll> st;
            ll l=column,r=column+width[i][column]-1;
            for(ll j=l;j<=r;j++){
                while(!st.empty() && height[i][st.top()]>=height[i][j]) {
                    st.pop();
                }
                if(st.empty()) L[j]=l;
                else L[j]=st.top()+1;
                st.push(j);
            }
            while(!st.empty()) st.pop();
            for(ll j=r;j>=l;j--){
                while(!st.empty() && height[i][st.top()]>=height[i][j]) {
                    st.pop();
                }
                if(st.empty()) R[j]=r;
                else R[j]=st.top()-1;
                st.push(j);
            }
            for(ll j=l;j<=r;j++){
                ans=max(ans,height[i][j]*(R[j]-L[j]+1));
            }
            column+=width[i][column];
        }
    }
    cout<<ans<<'\n';
}   

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}