greedy

Each operation removes one '1' and one '0' where the '1' is to the left of the '0'. So, every '1' needs a '0' somewhere to its right to be removed.

Think from the end of the string — the rightmost '1' can only be removed if there is at least one '0' after it.

Try scanning from the end while counting '0's. If at any moment the number of '1's exceeds the number of '0's to their right, it’s impossible to remove all '1's.

We iterate from the end of the string toward the beginning. Let’s maintain how many '0's are available to remove '1's. When we see '0', it becomes available for pairing — we can think of it as “adding one removable slot”.

When we see '1', it must pair with a '0' to its right. If a '0' is available, we consume one of them. If not, this '1' can never be removed — so the answer is NO.

If we finish scanning the string without violating this condition, then every '1' can be paired with some '0' to its right, and we can remove all '1's → YES.

Essentially, the check is: While going from right to left, the number of '1's should never exceed the number of '0's seen so far. If it ever does, removal becomes impossible.

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

int main(){
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        int tt; cin >> tt;
        while( tt-- ){
		int n , c = 0; cin >> n;
		bool ans = 1;
		string s; cin >> s;
		for( int i = n-1 ; i >= 0 ; i-- ){ 
			c += ( s[i] == '1' );
			ans &= ( ( n - i - c ) >= c );
		}
		cout << ( ( ans )? "YES" : "NO" ) << '\n';
        }
}

Implementation

The problem's nested, self-similar structure ("evaluate from the inside out") is a strong indicator that recursion is a good approach.

To recursively evaluate a sub-list [...], you need to know where it ends. A stack can be used in a pre-processing step to find and store the index of every matching ] for each [.

1 . Bracket Matching Preprocessing

• Use a stack to record the position of '['.
• When encountering a ']', pop from stack and store v[opening_index] = closing_index.
• This allows constant-time access to where each list ends.

2 . Recursive Evaluation Function f(l, r)

• Extract the operator (SUM, MAX, or MIN) starting at index l.
• Iterate through the substring s[l+4 ... r] : If we find digits → build a number , If we find ' [ ' → recursively evaluate the sublist , On encountering ' , ' or ' ] ' → apply the operator to current value

Complexity Analysis

Each character is processed once → O(N) per test. Sum of N ≤ 10⁶ → efficient for given constraints.

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

#define ll long long 

ll f(ll l,ll r,string &s,vector<ll>&v){

    // cout<<l<<" "<<r<<endl;
    
    string t=s.substr(l,3);

    ll op;
    if(t=="SUM") op=0;
    else if(t=="MAX") op=1;
    else op=2;

    ll ans=0; if(op==2) ans=2*1e10;
    ll num=0;

    for(ll j=l+4;j<=r;j++){
        if(s[j]==',' || s[j]==']'){
            
            if(op==0) ans+=num;
            else if(op==1) ans=max(ans,num);
            else ans=min(ans,num);
            
            num=0;
        }else if('0'<=s[j] && s[j]<='9'){
            num*=10;
            num+=s[j]-'0';
        }else{
            ll idx=v[j];

            num=f(j+1,idx,s,v);
            j=idx;
        }
    }

    return ans;
}

void solve(){
    ll n;cin>>n;
    string s;cin>>s;

    vector<ll>v(n);

    stack<int>st;
    for(ll i=0;i<n;i++){
        if(s[i]=='[') st.push(i);
        else if(s[i]==']'){
            v[st.top()]=i;
            st.pop();
        }
    }

    ll ans=f(1,n-1,s,v);
    cout<<ans<<endl;;
    
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    ll t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

maths , number-theory

For any two numbers a and b, their greatest common divisor g = gcd(a, b) divides both of them. Hence, a and b are multiples of g. So, to maximize the GCD, we need to find the largest integer g such that at least two numbers in the array are divisible by g.

Key Observation

If we know how many numbers in the array are divisible by each possible value g, then:

• If at least two numbers are divisible by g, → there exists a pair whose GCD is at least g.
• Therefore, the maximum such g is our answer.

Approach

1. Compute the frequency (cnt[x]) of each number in the array.
2. For each possible divisor g (from 1 to the maximum value in the array):

• Count how many numbers in the array are divisible by g. This can be done by summing cnt[g] + cnt[2g] + cnt[3g] + ...
• If this count ≥ 2, it means at least two elements share g as a common divisor.

The largest g satisfying this condition is the maximum possible GCD.

why this approach works because $$$n + \frac{n}{2} + \frac{n}{3} + \cdots + 1 \approx n \log n$$$.

Complexity Analysis

• Each number g checks its multiples up to the maximum array value (10^6).
• The total work is roughly O(maxA * log(maxA)), which is efficient enough for maxA = 10^6 .
• Memory usage is O(maxA) for the frequency array.

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

int main(){
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        int tt; cin >> tt;
        while( tt-- ){
		int n , c = 0; cin >> n;
		bool ans = 1;
		string s; cin >> s;
		for( int i = n-1 ; i >= 0 ; i-- ){ 
			c += ( s[i] == '1' );
			ans &= ( ( n - i - c ) >= c );
		}
		cout << ( ( ans )? "YES" : "NO" ) << '\n';
        }
}

Graphs , DSU

Think of Offline Queries.

Analog the problem with a Graph

Instead of deleting edges in the given order, think of it as adding the edges in reverse order

We can use a Disjoint Set for improving the Complexity.

Think of each Establishment as an edge between two dealers. So, when the Establishments are being sealed in the given order, we can interpret it as the deletion of edges from the graph. The vulnerability of each group (connected component) is defined as the maximum vulnerability among all the dealers present in that group.

If we use the brute-force approach, i.e., delete the edges one by one and perform BFS or DFS on the updated graph each time, the time complexity will be of the order O(n×(n+m)), where nnn is the number of dealers and mmm is the number of establishments. Hence, this approach will not pass all the test cases for larger inputs.

Instead of deleting the edges, we can add them in the reverse order and use a Disjoint Set Union (DSU) to track the changes in the vulnerability of each chain (component). Here, we need to use a modified DSU that stores and updates the maximum vulnerability within each connected component after every union operation.

We store the vulnerabilities and process the edges in reverse order so that, once completed, we can derive the vulnerability of the chain after each edge deletion in the original order. Once this is done, we can answer each query in constant time.

The time complexity of this optimized approach is O((n+m)×α(n) + Q), where α(n) is the inverse Ackermann function, which is very small in usual cases.

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mk make_pair
#define ff first
#define ss second
#define pll pair<ll, ll>
#define vl vector<ll>
using namespace std;
// code starts here
class DisjointSet
{
    ll N;
    vl V, rank, parent, maxc;

public:
    DisjointSet(vl &val)
    {
        V = val;
        N = val.size();
        rank.assign(N + 1, 0);
        parent.resize(N + 1);
        maxc.resize(N + 1);
        for (ll i = 1; i <= N; i++)
        {
            parent[i] = i;
            maxc[i] = val[i - 1];
        }
    }

    ll findupr(ll u)
    {
        if (parent[u] == u)
            return u;
        return parent[u] = findupr(parent[u]);
    }

    void union_by_rank(ll u, ll v, ll &sum)
    {
        ll upu = findupr(u), upv = findupr(v);
        if (upu == upv)
            return;

        ll nval = max(maxc[upu], maxc[upv]);
        sum -= (maxc[upu] + maxc[upv]);//remove the vulnerability of individual components of u and v
        sum += nval;// Add the vulnerability of the new component
        maxc[upv]=nval;//update the vulnerabilities
        maxc[upu]=nval;//update the vulnerabilities
        if (rank[upu] < rank[upv])
        {
            parent[upu] = upv;
        }
        else if (rank[upu] > rank[upv])
        {
            parent[upv] = upu;
        }
        else
        {
            parent[upv] = upu;
            ++rank[upu];
        }
    }
};

void solve()
{
    ll n, E, m;
    cin >> n >> E >> m;//take input 
    vl val(n);
    for (ll i = 0; i < n; i++)
        cin >> val[i];
    vector<vl> adj(n+1);//Store the graph in adjaceny list
    vector<pll>edges;//store the edges
    for (ll i = 0; i < E; i++)
    {
        ll a, b;
        cin >> a >> b;
        adj[a].pb(b);
        edges.pb(mk(a,b));
    }

    //store the order of deletion of edges
    vl  odr(m);
    for(ll i=0;i<m;i++)
        cin>>odr[i];

    //inpu tnumber of querries
    ll q;
    cin>>q;

    //make the base grpah that is after deleting all the edges given in odr, so that
    //we can start rebuilding the graph in reverse order.

    set<pll> del;
    vector<pll> delOrdr;
    for (ll i = 0; i < m; i++)
    {
        pll tmp=edges[odr[i]-1];
        ll a=tmp.ff,b=tmp.ss;
        del.insert(mk(a, b));
        del.insert(mk(b, a));
        delOrdr.pb(mk(a, b));
    }
    reverse(delOrdr.begin(), delOrdr.end());
    DisjointSet g(val);
    ll sum=0;
    for(auto it:val)
    sum+=it;
    for (ll i = 1; i <=n; i++)
    {
        for (auto ad : adj[i])
        {
            ll U = i, V = ad;
            if(del.find(mk(U,V))!=del.end())
            continue;
            g.union_by_rank(U,V,sum);
        }
    }

    //add the edges and stor the vulnerabilities in the array ans
    vl ans;
    ans.pb(sum);
    for(ll i=0;i<m;i++)
    {
        ll U=delOrdr[i].ff,V=delOrdr[i].ss;
        g.union_by_rank(U,V,sum);
        ans.pb(sum);   
    }
    reverse(ans.begin(),ans.end());//reverse the an array as we added the edges in reverse order

    while(q--)
    {
        ll Q;
        cin>>Q;
        cout<<ans[Q]-ans[Q-1]<<" ";//answer each querry in constant time
    }
    cout<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t;
    cin >> t;//number of test cases.
    while (t--)
        solve();
    return 0;
}

trees , two-pointers , binary-search

Is there a way to check whether node u is under subtree of node v or not ?

To determine whether one node lies within the subtree of another, we can use the Euler Tour (Depth-First Search) technique. During the DFS traversal, we record two timestamps for every node — in-time (when we first enter the node) and out-time (when we finish exploring all its children). A node u lies in the subtree of node v if and only if

in[v] <= in[u] <= out[v]

To find how many nodes from a given set lie inside the subtree of a particular node, we can use the concept of in-time and out-time obtained through a Depth-First Search (DFS) traversal. During the DFS, we record the time when we first enter a node (called its in-time) and the time when we finish visiting all its children (called its out-time). Using these two values, we know that all nodes in the subtree of a node u will have their in-time values between in[u] and out[u].

After computing these times for all nodes, we take all nodes that belong to the given set and store their in-times in a separate vector S. We then sort this vector according to the in-time, as it will help us quickly find how many of these nodes fall within the range [in[u], out[u]]. For any node u, the number of nodes from the set that lie in its subtree is simply the count of in-time values within this range. This can be easily calculated using binary search functions like lower_bound and upper_bound in C++.

cnt = upper_bound(S.begin(), S.end(), out[u]) — lower_bound(S.begin(), S.end(), in[u]) — 1

Now if this cnt is greater than or equal to k for any given node in set S than and is yes otherwise no

( We can also use two pointer technique )

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

#define ll long long

const ll mod = 1e9 + 7;

void dfs(ll idx,ll &t,vector<vector<ll>>&g,vector<ll>&vis,vector<ll>&in,vector<ll>&out){
    vis[idx]=1;
    
    in[idx]=t++;

    for(auto &ii:g[idx]){
        if(!vis[ii]){
            dfs(ii,t,g,vis,in,out);
        }
    }

    out[idx]=t++;
}

void solve(){
    ll n;cin>>n;
    vector<vector<ll>>g(n+1);

    for(ll i=1;i<n;i++){
        ll u,v;cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<ll>vis(n+1,0);
    
    // Vectors for storing in and out time
    vector<ll>in(n+1,0);
    vector<ll>out(n+1,0);

    ll t=1;
    dfs(1,t,g,vis,in,out);

    ll q;cin>>q;
    while(q--){
        ll k;cin>>k;
        ll m;cin>>m;

        // Storing in and out time of given node in vector temp
        vector<vector<ll>>temp;
        for(ll i=0;i<k;i++){
            ll a;cin>>a;

            temp.push_back({in[a],out[a]});
        }

        sort(temp.begin(),temp.end());


        // Using Two pointer technique 
        ll idx=0;
        ll mx=0;
        for(ll i=0;i<k;i++){
            while(idx<k && temp[idx][0]<=temp[i][1]) idx++;

            mx=max(mx,idx-i-1);
        }
    
        if(mx>=m) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }

}

//*****************
// Main function
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    ll t;
    cin >> t;

    while(t--){
        solve();
    }

    return 0;
}