Sum of two odd numbers is even and sum of two even numbers is also even.

If all consecutive pairs have even sum, can we generalize something about the sequence using the above hint?

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

What happens to other people when a person receives a shoe greater his size?

What happens when a person has a unique shoe size?

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

What is the contribution of each 1?

At what position would 1 contribute less?

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

If we have a list of subarrays where the element at index $$$i$$$ is the max, which subarrays should we check to be sufficient?

Checking subarrays which end or start at index $$$i$$$ is sufficient, so we can optimize our solution with this observation as the basis.

#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";
   }
}

We can iterate over the starting and ending points of all segments.

Is it necessary to connect all segments which can be connected?
Can we make observations which would reduce the number of connections we actually make?

For each group formed, it is enough to store the blue segment with maximum ending point, and red segment with maximum ending point.

#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();   
}

from sys import stdin
 
def solve_case():
    n = int(stdin.readline())
    segs = [tuple(map(int, stdin.readline().split())) + (i, ) for i in range(n)]
    segs.sort(key=lambda x: x[1])
    
    par = [-1] * n
    cnt_comp = n
    def find_set(u):
        p = u
        while par[p] >= 0:
            p = par[p]
        while u != p:
            t = par[u]
            par[u] = p
            u = t
        return p
    
    def join(u, v):
        nonlocal cnt_comp
        nonlocal par
        u = find_set(u)
        v = find_set(v)
        if u == v:
            return 
        if -par[u] < -par[v]:
            u, v = v, u
        par[u] += par[v]
        par[v] = u
        cnt_comp -= 1
    
    hp = [[], []]
    
    for col, l, r, id in segs:
        for elm in hp[1 - col]:
            if elm[0] < l:
                continue
            join(elm[1], id)
        if len(hp[1 - col]):
            hp[1 - col] = [max(hp[1 - col])]
        hp[col].append((r, id))
    return cnt_comp
 
for testcase in range(int(stdin.readline())):
    print(solve_case())

#include <bits/stdc++.h>
using namespace std;
 
#define nl "\n"
#define nf endl
#define ll int
#define pb push_back
#define _ << ' ' <<
#define tm gfewnignefgo
 
#define INF (int)1e9
#define mod 998244353
#define maxn 200010
 
ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll c[maxn], l[maxn], r[maxn], pr[maxn], sz[maxn];
ll tm, df[maxn];
vector<ll> adj[maxn];
vector<array<ll, 2>> nd;
vector<array<ll, 3>> cm;
priority_queue<array<ll, 2>> fn[2][maxn]; 
 
ll find(ll x) {
    if (x == pr[x]) return x;
    return pr[x] = find(pr[x]);
}
 
bool same(ll a, ll b) {
    return (find(a) == find(b));
}
 
void onion(ll a, ll b) {
    a = find(a); b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    pr[b] = a; sz[a] += sz[b];
}
 
void upd(ll c, ll p, ll x, ll id) {
    while (p < maxn) {
        fn[c][p].push({x, id}); p += (p & (-p));
    }
}
 
void nts(ll c, ll p, ll r, ll st) {
    ll wn = -1;
    for (; p > 0; p -= (p & (-p))) {
        while (!fn[c][p].empty()) {
            auto [rr, id] = fn[c][p].top();
            if (!df[id]) {
                fn[c][p].pop(); continue;
            }
            if (rr < r) break;
            wn = id; break;
        }
        if (wn != -1) {
            nd.pb({st, wn}); break;
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif
 
    // today I'm overkilling everything
    // tl;dr mst with boruvka and merge sort tree, O(n*log^3(n)), let's hope it gets ac
 
    cin >> t;
    while (t--) {
        cin >> n;
        for (i = 1; i <= 2 * n; i++) {
            while (!fn[0][i].empty()) fn[0][i].pop();
            while (!fn[1][i].empty()) fn[1][i].pop();
        }
        for (i = 1; i <= n; i++) {
            cin >> c[i] >> l[i] >> r[i];
            pr[i] = i; sz[i] = 1;
        }
 
        cm.clear(); cm.pb({-INF, 0, 0});
        for (i = 1; i <= n; i++) {
            cm.pb({l[i], i, 0}); cm.pb({r[i], i, 1});
        }
 
        sort(cm.begin(), cm.end());
        for (i = 1; i <= 2 * n; i++) {
            if (i == 1 || cm[i][0] != cm[i - 1][0]) k = i;
            if (cm[i][2] == 0) l[cm[i][1]] = k;
            else r[cm[i][1]] = k;
        }
 
        for (i = 1; i <= n; i++) {
            upd(c[i], l[i], r[i], i); df[i] = true;
        }
 
        while (true) { 
            nd.clear();
            for (i = 1; i <= n; i++) adj[i].clear(); 
            for (i = 1; i <= n; i++) adj[find(i)].pb(i);
            for (i = 1; i <= n; i++) {
                for (auto u : adj[i]) df[u] = false;
                for (auto u : adj[i]) nts(c[u] ^ 1, r[u], l[u], u);
                for (auto u : adj[i]) {
                    df[u] = true; upd(c[u], l[u], r[u], u);
                }
            }
 
            if (nd.empty()) break;
            for (auto [a, b] : nd) onion(a, b);
        }
 
        res = 0;
        for (i = 1; i <= n; i++) {
            if (find(i) == i) res++;
        }
        cout << res << nl;
    }
    return 0;
}

Can we root the tree and find the partial answer for a paticular root?

The counting problem for a fixed root can be solved using combinatorics.

Can we find the answer for other roots using the calculations involved in finding answer for a fixed root in Hint 1?

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