This is hint 1.

This is hint 2.

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		vector<int> a(n);
		for (int i = 0; i < n; ++i)
			cin >> a[i];
		int num_odd = 0;
		for (auto x : a)
			if (x & 1)
				num_odd++;
		cout << min(num_odd, n - num_odd) << endl;
	}
	return 0;
}

This is hint 1.

This is hint 2.

#include <bits/stdc++.h>

using namespace std;

#define ll long long
typedef vector<ll> vll;
#define io                            \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)

int main()
{
    io;
    ll tc;
    cin >> tc;
    while (tc--)
    {
        ll n;
        cin >> n;
        vll s(n), p(n);
        for (ll i = 0; i < n; ++i)
            cin >> s[i];

        ll l = 0, r = 0;
        bool ans = true;
        for (ll i = 0; i < n; ++i)
            p[i] = i + 1;

        while (r < n)
        {
            while (r < n - 1 and s[r] == s[r + 1]) // get range [l,r] with equal values
                ++r;
            if (l == r)
                ans = false;
            else
                rotate(p.begin() + l, p.begin() + r, p.begin() + r + 1); // rotate right in range [l,r]
            l = r + 1;
            ++r;
        }
        if (ans)
        {
            for (auto &x : p)
                cout << x << " ";
            cout << endl;
        }
        else
            cout << -1 << endl;
    }
    return 0;
}

This is hint 1.

This is hint 2.

#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, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int ones = 0, p1_first = n, p1_last = -1;
    for (int p = 0; p < n; p++) {
      if (s[p] != '1')
        continue;
      ones += 1;
      if (p1_first == n)
        p1_first = p;
      p1_last = p;
    }
    int add = 0;
    // moving the last one to last position
    if (ones > 0 and (n - 1 - p1_last) <= k) {
      k -= (n - 1 - p1_last);
      add += 1;
      ones -= 1;
    }
    // moving the first one to first position
    if (ones > 0 and p1_first <= k) {
      k -= (p1_first);
      add += 10;
      ones -= 1;
    }
    cout << 11 * ones + add << "\n";
  }
  return 0;
}

This is hint 1.

This is hint 2.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
const ll ninf = -1e15;
 
vector<int> nextGreater(vector<ll>& arr, int n) {
	stack<int> s;	
        vector<int> result(n, n);
	for (int i = 0; i < n; i++) {
		while (!s.empty() && arr[s.top()] < arr[i]) {
			result[s.top()] = i;	
			s.pop();
		}
		s.push(i);
	}
        return result;
}
 
vector<int> prevGreater(vector<ll>& arr, int n) {
	stack<int> s;	
        vector<int> result(n, -1);
	for (int i = n - 1; i >= 0; i--) {
		while (!s.empty() && arr[s.top()] < arr[i]) {
			result[s.top()] = i;	
			s.pop();
		}
		s.push(i);
	}
        return result;
}
 
ll query(vector<ll> &tree, int node, int ns, int ne, int qs, int qe) {
    if (qe < ns || qs > ne) return ninf;
    if (qs <= ns && ne <= qe) return tree[node];
 
    int mid = ns + (ne - ns) / 2;
    ll leftQuery = query(tree, 2 * node, ns, mid, qs, qe);
    ll rightQuery = query(tree, 2 * node + 1, mid + 1, ne, qs, qe);
    return max(leftQuery, rightQuery);
}
 
int main() {
   int t; 
   cin >> t;
   while (t--) {
        int n, _n;
        cin >> n;
        vector<ll> arr(n, 0);
        for (auto& a : arr)
            cin >> a;
        
        // Round off n to next power of 2
        _n = n;
        while (__builtin_popcount(_n) != 1) _n++;
 
 
        // Prefix sums
        vector<ll> prefixSum(n, 0), suffixSum(n, 0);
        prefixSum[0] = arr[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        }
        suffixSum[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffixSum[i] = suffixSum[i + 1] + arr[i];
        }
        
        // Two max-segtress, one on the prefix sums, one on the suffix sums
        vector<ll> prefixTree(2 * _n, ninf), suffixTree(2 * _n, ninf);
 
        for (int i = 0; i < n; i++) {
            prefixTree[_n + i] = prefixSum[i];
            suffixTree[_n + i] = suffixSum[i];
        }
 
        for (int i = _n - 1; i >= 1; i--) {
            prefixTree[i] = max(prefixTree[2 * i], prefixTree[2 * i + 1]);
            suffixTree[i] = max(suffixTree[2 * i], suffixTree[2 * i + 1]);
        }        
        vector<int> ng = nextGreater(arr, n); 
        vector<int> pg = prevGreater(arr, n); 
        bool flag = true;
 
        for (int i = 0; i < n; i++) {
            ll rightMax = query(prefixTree, 1, 0, _n - 1, i + 1, ng[i] - 1) - prefixSum[i];
            ll leftMax = query(suffixTree, 1, 0, _n - 1, pg[i] + 1, i - 1) - suffixSum[i];
            if (max(leftMax, rightMax) > 0) {
                flag = false;
                break;
            }
        }
        if (flag) 
            cout << "YES\n";
        else 
            cout << "NO\n";
   }
}

This is hint 1.

This is hint 2.

#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; 
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define MOD 1000000007
typedef long long ll;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(x) (int)(x).size()
#define fastio cin.tie(0) -> sync_with_stdio(0)
 
struct DSU{
    vi dsu, szx;
 
    DSU() = default;
    DSU(int n) : dsu(n), szx(n, 1) { 
        for(int i=0; i<n; i++) dsu[i] = i;
    }
    
    int parent(int i){
        if(dsu[i]==i) return i;
        else return dsu[i] = parent(dsu[i]);
    }
 
    int size(int i) { return szx[parent(i)]; }
    int operator[](int i){ return parent(i); }
    int num_comps(){
        int ct = 0;
        for(int i=0; i<sz(dsu); i++) if(dsu[i] == i) ct++;
        return ct;
    }
 
    void unify(int a, int b){
        a = parent(a);
        b = parent(b);
        if(szx[a] < szx[b]) swap(a, b);
        if(a!=b) dsu[b] = a, szx[a] += szx[b];
    }
};
 
struct Point{
    int t, p, pc, id;
    bool close;
    bool operator<(Point &other){
        if(p == other.p) return close < other.close;
        return p < other.p;
    }
};
 
void solve(){
 
    int n; cin>>n;
    vector<Point> points;
    for(int i=0; i<n; i++){
        int t, l, r; cin>>t>>l>>r;
        points.pb({t, l, r, i, false});
        points.pb({t, r, l, i, true});
    }
    sort(all(points));
 
    DSU dsu(n);
    vector<set<pii>> open(2); // {r, id}
    for(auto &p:points){
        if(p.close) open[p.t].erase({p.p, p.id});
        else{
            open[p.t].insert({p.pc, p.id});
            while(sz(open[p.t ^ 1]) > 1){
                auto [r, id] = *open[p.t ^ 1].begin();
                dsu.unify(p.id, id);
                open[p.t ^ 1].erase({r, id});
            }
            if(sz(open[p.t ^ 1]) == 1) dsu.unify(p.id, open[p.t ^ 1].begin()->second);
        }
    }
 
    cout<<dsu.num_comps()<<endl;
}
 
int main(){
    fastio;
	int t;
	cin >> t;
	while (t--) solve();   
}

print("Hello World!")

This is hint 1.

This is hint 2.

#include <iostream>
#include <vector>
 
using namespace std;
using ll = long long;
 
const ll MOD = 1e9 + 7;
 
struct Comb {
    vector<ll> fac;
    vector<ll> invfac;
    ll n;
 
    Comb(ll n)
    {
        this->n = n;
        fac.resize(n + 1, 0);
        invfac.resize(n + 1, 0);
 
        fac[0] = 1;
        for (ll i = 1; i <= n; i++)
            fac[i] = (fac[i - 1] * i) % MOD;
        invfac[n] = power(fac[n], MOD - 2);
        for (ll i = n - 1; i >= 0; i--)
            invfac[i] = (invfac[i + 1] * (i + 1)) % MOD;
    }
 
    static ll power(ll x, ll y)
    {
        ll ret = 1;
        while (y) {
            if (y & 1)
                ret = (ret * x) % MOD;
            y >>= 1;
            x = (x * x) % MOD;
        }
        return ret;
    }
 
    ll nCr(ll n, ll r)
    {
        if (n < 0 or r < 0 or n < r)
            return 0;
        ll ans = (fac[n] * ((invfac[r] * invfac[n - r]) % MOD)) % MOD;
        return ans;
    }
};
 
vector<vector<int> > adj;
vector<int> sz;
vector<ll> cnt;
vector<ll> cntsz;
 
Comb C(2e5 + 5);
 
ll cur_ans = 0;
ll ans = 0;
 
void dfs1(int v, int p, int k)
{
    sz[v] = 1;
    ll sub = 0;
 
    for (int u : adj[v]) {
        if (u != p) {
            dfs1(u, v, k);
            sz[v] += sz[u];
            sub = (sub + C.nCr(sz[u], k)) % MOD;
        }
    }
 
    cnt[v] = (C.nCr(sz[v], k) - sub + MOD) % MOD;
    cntsz[v] = (cnt[v] * sz[v]) % MOD;
    cur_ans = (cur_ans + cntsz[v]) % MOD;
}
 
void dfs2(int v, int p, int k)
{
    ans = (ans + cur_ans) % MOD;
    for (int u : adj[v]) {
        if (u != p) {
            // store
            int store_v_sz = sz[v];
            ll store_v_cnt = cnt[v];
            ll store_v_cntsz = cntsz[v];
            int store_u_sz = sz[u];
            ll store_u_cnt = cnt[u];
            ll store_u_cntsz = cntsz[u];
            ll store_cur_ans = cur_ans;
 
            // recalculate size[v], size[u]
            sz[v] -= sz[u];
            sz[u] = sz.size();
 
            // recalculate cnt[v]
            cnt[v] = (cnt[v] - C.nCr(store_v_sz, k) + MOD) % MOD;
            cnt[v] = (cnt[v] + C.nCr(sz[v], k)) % MOD;
            cnt[v] = (cnt[v] + C.nCr(store_u_sz, k)) % MOD;
 
            // recalculate cnt[u]
            cnt[u] = (cnt[u] - C.nCr(store_u_sz, k) + MOD) % MOD;
            cnt[u] = (cnt[u] + C.nCr(sz[u], k)) % MOD;
            cnt[u] = (cnt[u] - C.nCr(sz[v], k) + MOD) % MOD;
 
            // recalculate cntsz
            cntsz[v] = (cnt[v] * sz[v]) % MOD;
            cntsz[u] = (cnt[u] * sz[u]) % MOD;
 
            // recalculate cur_ans
            cur_ans = (cur_ans - store_v_cntsz - store_u_cntsz + MOD + MOD) % MOD;
            cur_ans = (cur_ans + cntsz[v] + cntsz[u]) % MOD;
 
            dfs2(u, v, k);
 
            // restore
            sz[v] = store_v_sz;
            cnt[v] = store_v_cnt;
            cntsz[v] = store_v_cntsz;
            sz[u] = store_u_sz;
            cnt[u] = store_u_cnt;
            cntsz[u] = store_u_cntsz;
            cur_ans = store_cur_ans;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n, k;
    cin >> n >> k;
 
    adj.resize(n);
    sz.resize(n);
    cnt.resize(n);
    cntsz.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);
    }
 
    dfs1(0, 0, k);
    dfs2(0, 0, k);
 
    cout << ans << endl;
    return 0;
}