• Excellent:
• Good:
• Average:
• Bad:
• Terrible:

• A:
• B:
• C:
• D:
• E:
• F:
• G:

• A:
• B:
• C:
• D:
• E:
• F:
• G:

How many people can be in one civilization?

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        if (n == 2) cout << "2\n";
        if (n == 3) cout << "3\n";
        if (n >= 4) cout << n % 2 << '\n';
    }
    
    return 0;
}

How many minutes of sand will remain in the upper half of the hourglass immediately after the second flip?

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int s, k, m;
        cin >> s >> k >> m;
        
        if (s <= k) cout << max(0, s - m % k) << '\n';
	else cout << (((m % (2 * k)) < k) ? s - m % k : k - m % k) << '\n';
    }
    
    return 0;
}

Why is brute force ineffective? How can it be improved?

How many distinct values can be obtained starting from the number $$$n$$$?

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n, k;
        cin >> n >> k;
        
        int l = n, r = n;
        int cnt = 0;
        while (r != 1) {
            if (l <= k && k <= r) break;
            l = l / 2;
            r = r / 2 + r % 2;
            cnt++;
        }
        if (l <= k && k <= r) cout << cnt << '\n';
        else cout << -1 << '\n';
    }
    
    return 0;
}

Alice's winning strategy is related to bits.

Alice's optimal number of moves depends only on the most significant bit and the number of set bits.

The number $$$n$$$ is a power of two, which means if you subtract $$$1$$$, any subset of bits of $$$n-1$$$ will not exceed $$$n-1$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
int c_n_k[31][31];

int main() {
    for (int i = 0; i < 30; ++i) {
        for (int j = 0; j < 30; ++j) {
            if (i < j) c_n_k[i][j] = 0;
            else if (j == 0) c_n_k[i][j] = 1;
            else c_n_k[i][j] = c_n_k[i - 1][j] + c_n_k[i - 1][j - 1];
        }
    }

    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;

        int d = 0;
        while (n % 2 == 0) {
            n /= 2;
            ++d;
        }

        int ans = 0;
        for (int max_bit = 0; max_bit < d; ++max_bit) {
            for (int cnt_bit = 1; cnt_bit <= max_bit + 1; ++cnt_bit) {
                if (max_bit + cnt_bit <= k) continue;
                ans += c_n_k[max_bit][cnt_bit - 1];
            }
        }

        if (d + 1 > k) ++ans;
        cout << ans << "\n";
    }

    return 0;
}

Solve the problem when $$$n$$$ is any integer from $$$1$$$ to $$$10^9$$$, not necessarily a power of two.

If some array is $$$k$$$-exquisite, then any of its subsegments of length at least $$$2$$$ is also $$$k$$$-exquisite.

If $$$k_1 \gt k_2$$$ and some array is $$$k_1$$$-exquisite, then it is also $$$k_2$$$-exquisite.

If some array of length $$$m$$$ is $$$k$$$-exquisite, how many $$$k$$$-exquisite subsegments does it have?

For a fixed $$$k$$$, come up with a way to divide the entire original permutation into segments, each of which is either $$$k$$$-exquisite or of length $$$1$$$, so that you can use the formula from the previous hint.

How to transition from the segmentation for $$$k+1$$$ to the segmentation for $$$k$$$?

Determine how the answer changes with each merging of two segments.

#include <bits/stdc++.h>

using namespace std;

vector <int> parent;
vector <int> rnk;
vector <int> sz;

void make_set(int v) {
    parent[v] = v;
    rnk[v] = 0;
    sz[v] = 1;
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rnk[a] < rnk[b])
            swap (a, b);
        parent[b] = a;
        if (rnk[a] == rnk[b])
            ++rnk[a];
        sz[a] += sz[b];
    }
}

long long cnt(int x) {
    x = find_set(x);
    return (long long)sz[x] * (sz[x] - 1) / 2;
}

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        map <int, vector <int>> m;
        int pr;
        for (int i = 0; i < n; i++) {
            int a;
            cin >> a;
            if (i > 0)
                m[abs(a - pr)].push_back(i);
            pr = a;
        }
        
        parent.resize(n);
        rnk.resize(n);
        sz.resize(n);
        for (int i = 0; i < n; i++) make_set(i);
        
        vector <long long> ans;
        long long cur = 0;
        for (int i = n - 1; i > 0; i--) {
            for (auto y : m[i]) {
                cur -= cnt(y);
                cur -= cnt(y - 1);
                union_sets(y, y - 1);
                cur += cnt(y);
            }
            ans.push_back(cur);
        }
        
        reverse(ans.begin(), ans.end());
        for (auto x : ans) cout << x << ' ';
        cout << '\n';
        
        parent.clear();
        rnk.clear();
        sz.clear();
    }

    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 200001;

int n;
vector <int> graph[MAXN];
vector <bool> dp[MAXN];

void merge_dp(vector <bool>& lhs, vector <bool>& rhs, vector <bool>& result) {
    for (int i = 0; i < 3; ++i) {
        if (!lhs[i]) continue;
        for (int j = 0; j < 3; ++j) {
            if (!rhs[j]) continue;
            result[(i + j) % 3] = true;
        }
    }
}

void dfs(int u, int p) {
    vector <int> child;

    for (auto v : graph[u]) if (v != p) {
        dfs(v, u);
        child.push_back(v);
    }

    dp[u].resize(3);

    if (!child.empty()) {
        dp[u][0] = true;
        for (auto v : child) {
            vector <bool> result(3, false);
 
            merge_dp(dp[u], dp[v], result);
            dp[u] = result;
        }
    }

    dp[u][1] = true;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            graph[i].clear();
            dp[i].clear();
        }
        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        dfs(1, -1);

        cout << (dp[1][0] ? "YES" : "NO") << '\n';
    }

    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 200001;

int n;
vector <int> graph[MAXN];
bool ans;

int dfs(int u, int p) {
    vector <int> child;
    int cnt = 0;

    for (auto v : graph[u]) if (v != p) {
        cnt++;
        auto t = dfs(v, u);
        if (t != 0) {
            child.push_back(t);
        }
    }

    if (child.size() > 1) {
        ans = true;
        return 0;
    }

    int type = cnt == 0 ? 0 : (cnt + 2) % 3;
    vector <int> ord;
    if (type) {
        ord.push_back(type);
    }
    if (!child.empty()) {
        ord.push_back(child[0]);
    }
    if (ord.size() == 2 && ord[0] + ord[1] != 3) {
        ans = true;
        return 0;
    }
    if (ord.size() >= 1) return ord[0];
    return 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            graph[i].clear();
        }
 
        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        ans = false;
        int res = dfs(1, 1);
        if (res == 2) {
            ans = true;
        }
     
        cout << (ans ? "YES" : "NO") << '\n';
    }

    return 0;
}

Fix $$$L$$$ and $$$R$$$ and define functions of integer $$$d$$$: $$$f(d) = d$$$, $$$g(d) = \min(a_L, \dots, a_{L+d})$$$, where $$$0 \le d \le R-L$$$. What can be said about these functions?

How many times can the problem condition be satisfied if expressed through $$$f$$$ and $$$g$$$?

Since the function $$$h(d) = f(d) - g(d)$$$ is monotonic, the only candidate for the intersection point is the minimum $$$d$$$ such that $$$h(d) \ge 0$$$ (or $$$f(d) \ge g(d)$$$).

Segment tree.

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 2e5 + 7;

int a[MAXN], st[4 * MAXN];

void build(int v, int l, int r) {
    if (l + 1 == r) {
        st[v] = a[l];
        return;
    }
    int m = (r + l) / 2;
    build(v * 2 + 1, l, m);
    build(v * 2 + 2, m, r);
    st[v] = min(st[v * 2 + 1], st[v * 2 + 2]);
}

void upd(int v, int l, int r, int i, int x) {
    if (i < l || r <= i) return;
    if (l + 1 == r) {
        a[i] = x;
        st[v] = x;
        return;
    }
    int m = (r + l) / 2;
    upd(v * 2 + 1, l, m, i, x);
    upd(v * 2 + 2, m, r, i, x);
    st[v] = min(st[v * 2 + 1], st[v * 2 + 2]);
}

int getMin(int v, int l, int r, int lq, int rq) {
    if (rq <= l || r <= lq) return (int) 1e6;
    if (lq <= l && r <= rq) return st[v];
    int m = (r + l) / 2;
    return min(getMin(v * 2 + 1, l, m, lq, rq), getMin(v * 2 + 2, m, r, lq, rq));
}

int ans, currMn;

void findInter(int v, int l, int r, int lq, int rq) {
    if (rq <= l || r <= lq || ans != (int) 1e6) return;
    if (lq <= l && r <= rq && min(currMn, st[v]) > r - lq - 1) {
        currMn = min(currMn, st[v]);
        return;
    }
    if (l + 1 == r) {
        ans = l;
        return;
    }
    int m = (r + l) / 2;
    findInter(v * 2 + 1, l, m, lq, rq);
    findInter(v * 2 + 2, m, r, lq, rq);
}


int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, q;
        cin >> n >> q;
        for (int i = 0; i < n; ++i) cin >> a[i];

        build(0, 0, n);
        while (q--) {
            int idx;
            cin >> idx;

            if (idx == 1) {
                int i, x;
                cin >> i >> x;
                upd(0, 0, n, i - 1, x);
            } else {
                int l, r;
                cin >> l >> r;
                l--;

                if (getMin(0, 0, n, l, r) > r - l) {
                    cout << "0\n";
                    continue;
                }

                ans = currMn = (int) 1e6;
                findInter(0, 0, n, l, r);
                cout << (ans != (int) 1e6 && getMin(0, 0, n, l, ans + 1) == ans - l) << "\n";
            }
        }
    }

    return 0;
}