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

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

• A:
• B:
• C1:
• C2:
• D:
• E:
• F:
• G:

• A:
• B:
• C1:
• C2:
• D:
• E:
• F:
• G:

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    string a, b, c;
    int n, m;
    cin >> n >> a;
    cin >> m >> b >> c;
    string add_left = "";
    for (int i = 0; i < m; ++i) {
        if (c[i] == 'V') {
            add_left += b[i];
        } else {
            a += b[i];
        }
    }
    reverse(add_left.begin(), add_left.end());
    cout << add_left + a << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

If Vadim appends $$$k$$$ zeros to the number $$$x$$$, what will be the ratio between $$$n$$$ and $$$x$$$?

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        long long r;
        cin >> r;
        
        long long d = 11;
        vector <long long> ans;
        while (r >= d) {
            if (r % d == 0)
                ans.push_back(r / d);
            d = (d - 1) * 10 + 1;
        }
        
        cout << (int)ans.size() << '\n';
        for (int i = (int)ans.size() - 1; i >= 0; --i)
            cout << ans[i] << ' ';
        cout << '\n';
    }
    
    return 0;
}

Does it make sense to use the same type of deal more than 2 times?

The solution with the minimum number of deals is unique.

Ternary numeral system.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    vector <long long> cost;
    long long c = 3;
    long long cnt = 1;
    for (int i = 0; i < 21; ++i) {
        cost.push_back(c);
        c = 3 * c + cnt;
        cnt *= 3;
    }

    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        long long min_k = 0;
        long long min_cost = 0;
        int sz = 0;
        while (n) {
            min_k += n % 3;
            min_cost += (n % 3) * cost[sz];
            n /= 3;
            sz++;
        }
        cout << min_cost << '\n';
    }
    
    return 0;
}

What is more profitable: 3 deals for $$$3^x$$$ watermelons each, or 1 deal for $$$3^{x+1}$$$ watermelons?

Recall the solution to problem C1.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    vector <long long> cost;
    long long c = 3;
    long long cnt = 1;
    for (int i = 0; i < 21; ++i) {
        cost.push_back(c);
        c = 3 * c + cnt;
        cnt *= 3;
    }

    int t;
    cin >> t;
    while (t--) {
        long long n, k;
        cin >> n >> k;
        vector <long long> tr;
        long long min_k = 0;
        while (n) {
            tr.push_back(n % 3);
            min_k += n % 3;
            n /= 3;
        }
        if (min_k > k) {
            cout << -1 << '\n';
            continue;
        }
        k -= min_k;
        k /= 2;
        for (int i = (int)tr.size() - 1; i >= 1; --i) {
            if (tr[i] <= k) {
                tr[i - 1] += 3 * tr[i];
                k -= tr[i];
                tr[i] = 0;
            } else {
                tr[i - 1] += k * 3;
                tr[i] -= k;
                break;
            }
        }
        ll an = 0;
        for (int i = (int)tr.size() - 1; i >= 0; --i)
            an += cost[i] * tr[i];
        cout << an << '\n';
    }
    
    return 0;
}

Find out which number the $$$k$$$-th digit belongs to in the infinite sequence. Let this number be $$$n$$$. Instead of analyzing the sequence, we can calculate the sum of the sums of the digits of all integers from $$$0$$$ to $$$n - 1$$$ and add to this the sum of the required digits of the number $$$n$$$.

Mentally add leading zeros to all numbers from $$$0$$$ to $$$n - 1$$$ so that their lengths become the same. The sum of the sums of the digits will not change, but it will be more convenient to determine the formulas in this case.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        long long k;
        cin >> k;
        long long cur = 9, len = 1;
        while (k - cur * len > 0) {
            k -= cur * len;
            cur *= 10;
            len++;
        }
        string s = to_string(cur / 9 + (k - 1) / len);
        long long ans = 0;
        for (int i = 0; i < (k - 1) % len + 1; i++)
            ans += s[i] - '0';
        long long pr_s = 0;
        for (int i = 0; i < s.length(); i++) {
            int curd = s[i] - '0';
            if (curd)
                ans += curd * (len - 1) * cur / 2 + curd * (2 * pr_s + curd - 1) / 2 * cur / 9;
            cur /= 10, len--;
            pr_s += curd;
        }
        cout << ans << '\n';
    }
    
    return 0;
}

If we know how many specific cards Vadim should take, and how many should take Kostya (for example when $$$x + y = z$$$). How can we then obtain the maximum possible sum?

We need to quickly compute the sum of the $$$x$$$ maximum elements in array $$$a$$$ and the sum of the $$$y$$$ maximum elements in array $$$b$$$. What should we do to be able to compute this for arbitrary $$$x$$$ and $$$y$$$ in $$$O(1)$$$?

How can we solve this problem if $$$x = n$$$ and $$$y = m$$$ — that is, each person can choose any number of cards, as long as their total is $$$z$$$?

If $$$x = n$$$ and $$$y = m$$$, then the optimal set of $$$z$$$ cards consists of $$$x'$$$ maximum cards from Vadim and $$$y'$$$ maximum cards from Kostya (where $$$x' + y' = z$$$). How should we adjust this optimal answer if the optimal number for Vadim or Kostya exceeds their limits (that is, if $$$x \lt x'$$$ or $$$y \lt y'$$$)?

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector <int> a(n), b(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());

    vector <long long> pa(n + 1), pb(m + 1);
    for (int i = 0; i < n; i++)
        pa[i + 1] = pa[i] + a[i];
    for (int i = 0; i < m; i++)
        pb[i + 1] = pb[i] + b[i];

    vector <pair <int, int>> ans(n + m + 1);
    int l = 0, r = 0;
    for (int i = 1; i < ans.size(); i++) {
        if (l < n && r < m) {
            if (a[l] < b[r])
                r++;
            else
                l++;
        }
        else if (l == n)
            r++;
        else if (r == m)
            l++;
        ans[i] = { l, r };
    }

    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        l = ans[z].first, r = ans[z].second;
        if (l > x)
            cout << pa[x] + pb[z - x] << '\n';
        else if (r > y)
            cout << pa[z - y] + pb[y] << '\n';
        else
            cout << pa[l] + pb[r] << '\n';
    }
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector <int> a(n), b(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());
 
    vector <long long> pa(n + 1), pb(m + 1);
    for (int i = 0; i < n; i++)
        pa[i + 1] = pa[i] + a[i];
    for (int i = 0; i < m; i++)
        pb[i + 1] = pb[i] + b[i];
 
    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
 
        int l = max(0, z - y);
        int r = min(z, x);
        while (l + 2 < r) {
            int m1 = (l + l + r) / 3;
            int m2 = (l + r + r) / 3;
            if (pa[m1] + pb[z - m1] > pa[m2] + pb[z - m2]) {
                r = m2;
            } else {
                l = m1;
            }
        }
 
        long long s = 0;
        for (int i = l; i <= r; i++)
            s = max(s, pa[i] + pb[z - i]);
 
        cout << s << '\n';
    }
}
 
int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

Recall or learn what bridges are and understand how this is related to the lanes that lie on all paths from $$$1$$$ to $$$n$$$.

How to find all the bridges that lie on every path from $$$1$$$ to $$$n$$$?

Solve the problem for the case where $$$n = q$$$ and $$$c_i = i$$$.

How to find the nearest vertex from a given set of vertices $$$S$$$ for each vertex?

#include <bits/stdc++.h>
 
using namespace std;
 
vector <vector <int>> g;
vector <bool> used;
vector <int> d, h;
vector <pair <int, int>> edges;
vector <int> cut, path;
int mark = 1;

void dfs(int v, int p, int n) {
    used[v] = true;
    d[v] = h[v] = (p == -1 ? 0 : d[p] + 1);
    if (v == n) mark = 0;
    for (auto e : g[v]) {
        int to = edges[e].first + edges[e].second - v;
        if (to == p) continue;
        if (used[to])
            h[v] = min(h[v], d[to]);
        else {
            path[e] ^= mark;
            dfs(to, v, n);
            path[e] ^= mark;
            h[v] = min(h[v], h[to]);
            if (h[to] > d[v]) cut[e] = 1;
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        
        g.assign(n + 1, {});
        used.assign(n + 1, false);
        d.assign(n + 1, 0);
        h.assign(n + 1, 0);
        edges = {};
        cut.assign(m, false);
        path.assign(m, false);
        mark = 1;
        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            edges.push_back({a, b});
            g[a].push_back(i);
            g[b].push_back(i);
        }
        
        dfs(1, -1, n);
        
        vector <int> ans(n + 1, n + m);
        vector <int> dist(n + 1, n + m);
        queue <int> q;
        for (int i = 0; i < m; ++i) {
            if (cut[i] && path[i]) {
                ans[edges[i].first] = min(ans[edges[i].first], i + 1);
                ans[edges[i].second] = min(ans[edges[i].second], i + 1);
                if (dist[edges[i].first]) {
                    dist[edges[i].first] = 0;
                    q.push(edges[i].first);
                }
                if (dist[edges[i].second]) {
                    dist[edges[i].second] = 0;
                    q.push(edges[i].second);
                }
            }
        }
        
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto e : g[v]) {
                int to = edges[e].first + edges[e].second - v;
                if (dist[to] > dist[v] + 1) {
                    dist[to] = dist[v] + 1;
                    ans[to] = ans[v];
                    q.push(to);
                }
                else if (dist[to] == dist[v] + 1)
                    ans[to] = min(ans[to], ans[v]);
            }
        }
        
        int Q;
        cin >> Q;
        while (Q--) {
            int v;
            cin >> v;
            if (ans[v] == n + m) cout << -1;
            else cout << ans[v];
            if (t || Q) cout << '\n';
        }
    }
    
    return 0;
}

There is no point in adding new symbols both above and below the original table simultaneously. Similarly, there is no point in adding symbols both to the left and to the right of the table at the same time.

The center of the optimal answer table lies within the original one.

We do not need to construct the answer; it is sufficient to check that an answer exists for the current center. Think about how to do this.

An answer exists for the current center if the subtable, which is the intersection of the original table and the one rotated around the center by $$$180^{\circ}$$$, becomes identical to the original when rotated by $$$180^{\circ}$$$. This subtable must contain at least one of the corners of the original table.

The checking of centers can be replaced by the checking of subtables that contain at least one of the corners of the original table.

To check the subtables to see if they become identical to the original when rotated by $$$180^{\circ}$$$, we can use hashing.

#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
const int P[2] = { 107, 61 };
int BP[2];

long long bin_pow(long long a, int n) {
    long long ret = 1;
    while (n) {
        if (n & 1) ret = (ret * a) % MOD;
        a = (a * a) % MOD;
        n >>= 1;
    }
    return ret;
}

inline int add(int a, int b) {
    int res = a + b;
    if (res >= MOD) return res - MOD;
    return res;
}

inline int sub(int a, int b) {
    int res = a - b;
    if (res < 0) return res + MOD;
    return res;
}

inline int mult(int a, int b) {
    long long res = (long long)a * b;
    if (res >= MOD) return res % MOD;
    return res;
}

int main() {
    int t;
    cin >> t;
    
    BP[0] = bin_pow(P[0], MOD - 2);
    BP[1] = bin_pow(P[1], MOD - 2);
    vector <int> pows[2];
    vector <int> bpows[2];
    for (int j = 0; j < 2; j++) {
        pows[j].resize(1e6, 1);
        bpows[j].resize(1e6, 1);
        for (int i = 1; i < 1e6; i++) {
            pows[j][i] = mult(pows[j][i - 1], P[j]);
            bpows[j][i] = mult(bpows[j][i - 1], BP[j]);
        }
    }
    
    while (t--) {
        int n, m;
        cin >> n >> m;
        
        vector <string> f(n);
        for (int i = 0; i < n; i++)
            cin >> f[i];
        
        vector <vector <int>> hash(n + 2, vector <int> (m + 2, 0));
        vector <vector <int>> bhash(n + 2, vector <int> (m + 2, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int cur = mult((f[i - 1][j - 1] - 'a' + 1), mult(pows[0][i - 1], pows[1][j - 1]));
                hash[i][j] = add(sub(add(hash[i - 1][j], hash[i][j - 1]), hash[i - 1][j - 1]), cur);
            }
        }
        for (int i = n; i >= 1; i--) {
            for (int j = m; j >= 1; j--) {
                int cur = mult((f[i - 1][j - 1] - 'a' + 1), mult(pows[0][n - i], pows[1][m - j]));
                bhash[i][j] = add(sub(add(bhash[i + 1][j], bhash[i][j + 1]), bhash[i + 1][j + 1]), cur);
            }
        }
        
        auto isp = [&](int x1, int y1, int x2, int y2) {
            int hsh = add(sub(sub(hash[x2][y2], hash[x1-1][y2]), hash[x2][y1-1]), hash[x1-1][y1-1]);
            int bhsh = add(sub(sub(bhash[x1][y1], bhash[x2+1][y1]), bhash[x1][y2+1]), bhash[x2+1][y2+1]);
            hsh = mult(hsh, mult(bpows[0][x1 - 1], bpows[1][y1 - 1]));
            bhsh = mult(bhsh, mult(bpows[0][n - x2], bpows[1][m - y2]));
            return hsh == bhsh;
        };
        
        int mn = n * m * 4;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (isp(1, 1, i, j)) mn = min(mn, (2 * n - i) * (2 * m - j));
                if (isp(1, j, i, m)) mn = min(mn, (2 * n - i) * (m + j - 1));
                if (isp(i, 1, n, j)) mn = min(mn, (n + i - 1) * (2 * m - j));
                if (isp(i, j, n, m)) mn = min(mn, (n + i - 1) * (m + j - 1));
            }
        }
        
        cout << mn - m * n << '\n';
    }
    
    return 0;
}

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

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

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

Prove that the number $$$2$$$ is not an ideal generator. What other numbers are not ideal generators for the same reason?

Prove that the number $$$3$$$ is an ideal generator. What is the difference from the previous case?

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

What is the minimum cost that can be achieved?

How many non-zero digits should be in the remaining number for the cost to be minimal?

How can we ensure that the number has as many leading zeros as possible?

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int n = s.size();
        bool met_positive = false;
        int cnt_zero = 0;
        
        for (auto i = n - 1; i >= 0; --i) {
            if (s[i] != '0') {
                met_positive = true;
            } else if (met_positive) {
                cnt_zero++;
            }
        }
        
        cout << n - (cnt_zero + 1) << '\n';
    }
    return 0;
}

$$$y$$$ is always divisible by $$$x$$$.

What happens if $$$k \geq 2$$$?

If $$$k \geq 2$$$ and $$$x \geq 2$$$, then $$$y$$$ will never be prime. Are there any edge cases with $$$k = 1$$$ or $$$x = 1$$$?

#include <bits/stdc++.h>
 
using namespace std;
 
bool is_prime(int x) {
    if (x <= 1) {
        return false;
    }
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}
 
void solve() {
    int x, k;
    cin >> x >> k;
    if (k > 1 && x > 1) {
        cout << "NO";
    } else if (k == 1) {
        cout << (is_prime(x) ? "YES" : "NO");
    } else {
        cout << ((k == 2) ? "YES" : "NO");
    }
}
 
int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        solve();
        cout << '\n';
    }
}

How does the answer change when $$$n$$$ is decreased?

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n, q;
        cin >> n >> q;
        
        while (q--) {
            string type;
            cin >> type;
            
            if (type == "->") {
                int x, y;
                cin >> x >> y;
                x--, y--;
                
                long long num = 0;
                for (int i = n - 1; i >= 0; --i) {
                    int cur = 1 << i;
                    if (!(x & cur) && !(y & cur))
                        num ^= 0ll << (2 * i);
                    if ((x & cur) && (y & cur))
                        num ^= 1ll << (2 * i);
                    if ((x & cur) && !(y & cur))
                        num ^= 2ll << (2 * i);
                    if (!(x & cur) && (y & cur))
                        num ^= 3ll << (2 * i);
                }
                cout << num + 1 << '\n';
            }
            else {
                long long num;
                cin >> num;
                num--;
                
                int x = 0, y = 0;
                for (int i = n - 1; i >= 0; --i) {
                    long long cur = 3ll << (2 * i);
                    if ((num & cur) >> (2 * i) == 0)
                        x ^= 0 << i, y ^= 0 << i;
                    if ((num & cur) >> (2 * i) == 1)
                        x ^= 1 << i, y ^= 1 << i;
                    if ((num & cur) >> (2 * i) == 2)
                        x ^= 1 << i, y ^= 0 << i;
                    if ((num & cur) >> (2 * i) == 3)
                        x ^= 0 << i, y ^= 1 << i;
                }
                cout << x + 1 << ' ' << y + 1 << '\n';
            }
        }
    }
    
    return 0;
}

How to check if a solution exists for a fixed $$$x$$$?

We can use binary search.

#include <bits/stdc++.h>

using namespace std;

vector<int> nums(2e5 + 5, 0);

bool check(vector<int>& v, int k, int m)
{
    int cnt = 0;
    int cur_mex = 0;
    for (int i = 0; i < v.size(); i++) {
        if (v[i] <= v.size() + 1) {
            nums[v[i]] = 1;
        }
        while (nums[cur_mex]) {
            cur_mex++;
        }
        if (cur_mex >= m) {
            cnt++;
            for (int j = 0; j < min(m + 1, (int)v.size() + 2); j++) {
                nums[j] = 0;
            }
            cur_mex = 0;
        }
    }
    for (int j = 0; j < v.size() + 2; j++) {
        nums[j] = 0;
    }
    return cnt >= k;
}

void solve()
{
    int n, k;
    cin >> n >> k;

    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    int l = 0;
    int r = 1e9;
    while (r - l > 1) {
        int m = (r + l) / 2;
        if (check(v, k, m)) {
            l = m;
        } else {
            r = m;
        }
    }

    cout << l << '\n';
}

signed main()
{
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
    return 0;
}

We need to ensure that we construct the array $$$a$$$. Therefore, when interacting with the neural network, we should consider the worst-case scenario.

Read the previous hint. How many operations of the first type applied to the $$$i$$$-th neural network do we need to obtain at least one correct word (i.e., one such that $$$b_{i, j} = a_j$$$)?

Read the previous hint and its answer. Which neural network is optimal to start with? How many blanks will there be in the array $$$c$$$ after interacting with this neural network?

There are currently no blanks in the array $$$c$$$, but there are incorrect words in some positions. How many operations are needed to replace one incorrect word with a correct one?

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (auto &i: a) {
        cin >> i;
    }
    vector<vector<string>> b(m, vector<string>(n));
    for (auto &ar: b) {
        for (auto &s: ar) {
            cin >> s;
        }
    }
    vector<bool> exists(n);
    int x = 0;
    for (int i = 0; i < m; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if (a[j] == b[i][j]) {
                cnt++;
                exists[j] = true;
            }
        }
        x = max(x, cnt);
    }
    if (all_of(exists.begin(), exists.end(), identity())) {
        cout << n + 2 * (n - x) << "\n";
    } else {
        cout << "-1\n";
    }
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Let the shortest segment have boundaries $$$l$$$ and $$$r$$$. What can be said about the indices $$$i$$$ and $$$j$$$ for which the maximum value of the expression $$$a_i \oplus a_j$$$ is achieved?

The operation $$$x \oplus y$$$ on int32 numbers can be represented as the XOR of two binary strings of length $$$32$$$. What can be said about the comparison of numbers? In what case does the expression $$$x \oplus y = z$$$ hold? And $$$x \oplus y \gt z$$$?

How can we use a trie on binary strings to find the nearest index $$$j$$$ such that $$$a_i \oplus a_j = k$$$?

#include <bits/stdc++.h>
 
using namespace std;
 
const int LOG_X = 29;
 
struct node {
    int children[2] { -1, -1 };
    int last = -1;
};
 
int find(const vector<node>& trie, int value, int border) {
    int res = -1;
    int current = 0;
    bool ok = true;
    for (int position = LOG_X; ok && position >= 0; position--) {
        int x_bit = (value >> position) & 1;
        int k_bit = (border >> position) & 1;
        auto& children = trie[current].children;
        if (k_bit == 1) {
            if (children[x_bit ^ 1] != -1) {
                current = children[x_bit ^ 1];
            } else {
                ok = false;
            }
        } else {
            if (children[x_bit ^ 1] != -1) {
                res = max(res, trie[children[x_bit ^ 1]].last);
            }
            if (children[x_bit] != -1) {
                current = children[x_bit];
            } else {
                ok = false;
            }
        }
    }
    if (ok) {
        res = max(res, trie[current].last);
    }
    return res;
}
 
void add(vector<node>& trie, int value, int index) {
    int current = 0;
    trie[current].last = max(trie[current].last, index);
    for (int position = LOG_X; position >= 0; position--) {
        int x_bit = (value >> position) & 1;
        if (trie[current].children[x_bit] == -1) {
            trie[current].children[x_bit] = trie.size();
            trie.push_back(node());
        }
        current = trie[current].children[x_bit];
        trie[current].last = max(trie[current].last, index);
    }
}
 
void solve() {
    int n, k;
    cin >> n >> k;
 
    int ans = n + 1;
    vector<node> trie(1);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        add(trie, x, i);
        int y = find(trie, x, k);
        if (y != -1) {
            ans = min(ans, i - y + 1);
        }
    }
 
    if (ans == n + 1) {
        cout << "-1\n";
    } else {
        cout << ans << '\n';
    }
}
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        solve();
    }
 
    return 0;
}