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_max and suffix_max. Then we will traverse the array from $$$2$$$ to $$$n-1$$$ and our answer will be max(answer, (pref_max[j-1] $$$-$$$ A[j]) $$$\times$$$ suffix_max[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;
}