Editorial — Codeguerra

Hint 1

Hint 2

Solution

Code

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

typedef long long ll;

ll fac[25];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    fac[0] = 1;
    for(int i = 1; i < 25; ++i){
        fac[i] = fac[i - 1] * i;
    }

    ll tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;

        // nth element always stable
        // so rest has to be unstable
        // total ways = n!

        if(n >= 22){
            cout << 0 << '\n';
        } else {
            cout << fac[n] << '\n';
        }
    }

    return 0;
}

Solution

Core Logic: Chicken McNugget Theorem
By the Chicken McNugget Theorem (Frobenius Coin Problem), for any equation $$$ax+by=c$$$ with coprime $$$a, b$$$, the largest integer that cannot be expressed using non-negative integers $$$x, y$$$ is $$$ab - a - b$$$.
Intuitively, this logic extends to any pair $$$(a, b)$$$ with $$$\gcd(a, b) = g$$$, where the pattern becomes regular (periodic) for multiples of $$$g$$$ after the limit $$$\frac{ab}{g} - a - b$$$.

Approach:

Brute Force (The "Irregular" Head): Since we know the reachability becomes predictable after $$$Limit = \frac{ab}{g} - a - b$$$, we can simply brute-force (using a boolean array or DP) for all values up to this limit.
- Why this works: The problem guarantees $$$\sum a_i b_i \le 5 \cdot 10^6$$$. Since the limit is strictly less than $$$ab$$$, the total operations for this brute-force step across all test cases will never exceed the time limit.
Prefix Sum (The "Periodic" Tail): Once we pass the calculated limit, the jammer will reinforce every multiple of $$$g$$$. We store the starting point ($$$Start \gt Limit$$$) for each jammer grouped by their $$$g$$$. To calculate the total jammers for these large values efficiently, we use a harmonic sweep:
- For each GCD value $$$g$$$, let count be an array tracking active jammers.
- Initialize count[start]++ for every jammer starting at start.
- Apply a stride-based prefix sum: Iterate $$$j$$$ from $$$g$$$ to $$$N$$$ with step $$$g$$$, updating count[j+g] += count[j].
- This propagates the number of active jammers through all subsequent multiples of $$$g$$$.

Time Complexity:

Part 1 (DP): $$$O(\sum a_i b_i)$$$. Given the constraint $$$\sum a_i b_i \le 5 \cdot 10^6$$$, this is extremely fast (~0.05 seconds).
Part 2 (Harmonic Sweep): We iterate through multiples for each $$$g$$$. This follows the harmonic series $$$N/1 + N/2 + \dots + N/N$$$, which sums to $$$O(N \log N)$$$. With $$$N=2 \cdot 10^5$$$, this is roughly $$$3 \cdot 10^6$$$ operations. Total Complexity: $$$O(\sum a_i b_i + N \log N)$$$.

Code

#include <bits/stdc++.h>
using namespace std;
void run(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
 
#define ll long long
#define pb push_back
 
ll gcd(ll a, ll b) {while (b) {ll temp = b;b = a % b;a = temp;}return a;}
ll lcm(ll a, ll b) {if(a==0||b==0)return 0; return (a/gcd(a,b))*b;}
 
void fun(){
    ll n, k;
    cin >> n >> k;
 
    vector<ll> ans1(n+1, 0), ans(n+1, 0);
    vector<vector<ll>> vals(n+1);
 
    for(int i=1; i<=k; i++){
        ll a, b; cin >> a >> b;
        ll g = gcd(a, b);
 
        // Calculate limit safely
        ll limit_val = (a*b)/g - a - b;
        ll limit = min(n, limit_val);
 
        vector<bool> dp(max(0LL, limit) + 1, 0);
        dp[0] = 1;
 
        for(int j=0; j<=limit; j++){
            if(dp[j]) {
                if(j > 0) ans1[j]++; // Update Head count
                if(j+a <= limit) dp[j+a] = 1;
                if(j+b <= limit) dp[j+b] = 1;
            }
        }
 
        // Calculate Tail start
        // Ensure start is at least g (index 1-based, multiples of g)
        ll start = max(g, (limit/g)*g + g);
 
        if(start <= n) vals[g].pb(start);
    }
 
    // Merge Head counts
    for(int i=1; i<=n; i++) ans[i] += ans1[i];
 
    // Harmonic Sweep for Tail
    vector<ll> curr(n+1, 0);
    for(int i=1; i<=n; i++){
        if(vals[i].empty()) continue;
 
        for(auto it : vals[i]) curr[it]++;
 
        for(int j=i; j<=n; j+=i){
            if(curr[j] > 0) ans[j] += curr[j];
            if(j+i <= n) curr[j+i] += curr[j];
        }
        // Cleanup
        for(int j=i; j<=n; j+=i) curr[j] = 0LL;
    }
 
    for(int i=1; i<=n; i++) cout << ans[i] << (i==n ? "" : " ");
    cout << "\n";
}
 
int main(){
    run();
    ll t; cin >> t;
    while(t--) fun();
}

Hint 1

Hint 2

Solution

Code

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

typedef long long ll;

/* read vector */
void readVector(vector<ll>& v){
    for(size_t i = 0; i < v.size(); ++i){
        cin >> v[i];
    }
}

/* prefix sum: pref[i] = sum of first i elements (1-indexed logic) */
vector<ll> prefix(const vector<ll>& v){
    int n = v.size();
    vector<ll> pref(n + 1, 0);
    for(int i = 1; i <= n; ++i){
        pref[i] = pref[i - 1] + v[i - 1];
    }
    return pref;
}

/* sum of vector */
ll sumV(const vector<ll>& v){
    ll s = 0;
    for(ll x : v) s += x;
    return s;
}

void resolve2(ll tc){
    int n;
    cin >> n;

    vector<ll> a(n);
    readVector(a);

    vector<ll> b(n);
    readVector(b);

    /*
        max(pref[r2]-pref[l2-1]-(pref[r]-pref[l-1]))
        l <= l2 <= r2 <= r
        transformed DP:
        max(-pref[r] + pref[r2] + pref[l-1] - pref[l2-1])
    */

    vector<ll> pref = prefix(a);
    vector<ll> prefb = prefix(b);

    vector<ll> dp1(n + 1, 0); // max pref[l-1]
    vector<ll> dp2(n + 1, 0); // max -prefb[i] + dp1[i]
    vector<ll> dp3(n + 1, 0); // max dp2[j] + prefb[j]
    vector<ll> dp4(n + 1, 0); // max dp3[j] - pref[j]

    for(int i = 1; i <= n; ++i){
        dp1[i] = max(dp1[i - 1], pref[i]);
    }

    for(int i = 1; i <= n; ++i){
        dp2[i] = max(dp2[i - 1], -prefb[i] + dp1[i]);
    }

    for(int i = 1; i <= n; ++i){
        dp3[i] = max(dp3[i - 1], dp2[i] + prefb[i]);
    }

    for(int i = 1; i <= n; ++i){
        dp4[i] = max(dp4[i - 1], dp3[i] - pref[i]);
    }

    ll totSum = sumV(a);
    cout << totSum + dp4[n] << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    ll tc;
    cin >> tc;
    while(tc--){
        resolve2(tc);
    }
    return 0;
}

Hint 1

Hint 2

Hint 3

Solution

Code

#include <bits/stdc++.h>
using namespace std;
 
// Disjoint Set Union structure for maintaining connected components
struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n), sz(n,1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x){
        return p[x] == x ? x : p[x] = find(p[x]); // path compression
    }
    bool unite(int a, int b){
        a = find(a);
        b = find(b);
        if(a == b) return false; // already connected
        if(sz[a] < sz[b]) swap(a,b); // union by size
        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    while(T--){
        int N;
        cin >> N;
 
        const int MAXV = 200000;
        vector<vector<int>> pos(MAXV + 1); // pos[x] = list of chambers containing value x
 
        // Read chambers and store positions for each value
        for(int i = 0; i < N; i++){
            int k;
            cin >> k;
            while(k--){
                int x;
                cin >> x;
                pos[x].push_back(i);
            }
        }
 
        DSU dsu(N);
        long long ans = 0;
 
        vector<int> nodes;
        // Process all possible gcd values from largest to smallest
        for(int g = MAXV; g >= 1; g--){
            nodes.clear();
            // Gather all chambers containing multiples of g
            for(int m = g; m <= MAXV; m += g){
                for(int v : pos[m]){
                    nodes.push_back(v);
                }
            }
            if(nodes.empty()) continue;
 
            // Connect all gathered chambers with edges of weight g
            int root = nodes[0];
            for(int i = 1; i < (int)nodes.size(); i++){
                if(dsu.unite(root, nodes[i])){
                    ans += g; // add edge weight to total
                }
            }
        }
 
        cout << ans << "\n";
    }
 
    return 0;
}

Hint 1

Hint 2

Hint 3

Solution

Code

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define vi vector<int>
#define graph vector<vector<int>>
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
// solve returns the best focus point bonus (restored branch) found in the subtree
int solve(int parent, int node, int& ans, graph& adj, vi& a, vi& b, int k) {
    if (adj[node].size() == 1 && parent != -1) {
        a[node] = 1;
        return 0;
    }
 
    int sum = 0;
    int mini = LLONG_MAX;
    int add = 0;
 
    for (auto child : adj[node]) {
        if (child != parent) {
            add = max(add, solve(node, child, ans, adj, a, b, k));
            sum += a[child];
            mini = min(mini, a[child]);
        }
    }
 
    if (adj[node].size() < k) {
        a[node] = sum + 1;
        return add;
    }
 
    // Node currently has degree k.
    // Calculate size if this node is chosen to be the Focus Point.
    int size_if_focus = sum + 1;
    ans = max(ans, size_if_focus + add);
 
    // To keep the subtree "clean" for the parent, we prune the smallest branch.
    a[node] = sum - mini + 1;
    b[node] = mini;
 
    // Return the best focus point candidate: either one from below or this node's pruned branch.
    return max(add, mini);
}
 
void solve_test_case() {
    int n, k;
    if (!(cin >> n >> k)) return;
    graph adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
 
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (adj[i].size() == k) count++;
    }
 
    // If only one or zero focus points exist, no chambers need to be destroyed.
    if (count <= 1) {
        cout << 0 << endl;
        return;
    }
 
    vi a(n + 1, 0), b(n + 1, 0);
    int ans = 0;
 
    // Start DFS from node 1.
    for (auto child : adj[1]) {
        solve(1, child, ans, adj, a, b, k);
    }
 
    int sum = 0;
    int mini = LLONG_MAX;
    for (auto child : adj[1]) {
        sum += a[child];
        mini = min(mini, a[child]);
    }
 
    a[1] = sum + 1;
    if (adj[1].size() == k) {
        a[1] -= mini;
        b[1] = mini;
    }
 
    ans = max(ans, a[1]);
 
    // Final check: what if node i is the restored Focus Point in node 1's component?
    for (int i = 1; i <= n; i++) {
        ans = max(ans, a[1] + b[i]);
    }
 
    cout << n - ans << endl;
}
 
int32_t main() {
    fastio;
    int t;
    cin >> t;
    while (t--) {
        solve_test_case();
    }
    return 0;
}

Hint1

Hint2

Hint3

Hint4

Solution

Code

#include <bits/stdc++.h> 
using namespace std;
 
#define ll long long
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL)
 
//covers all automatic and a manual before (and equal to) time t
void update(ll t, ll x, ll k, ll &last, ll &ans){
    ll prev = last/x; //previous count of automatic triggers completed
    ll curr = t/x;//new count of automatic triggers completed
 
    ll cnt = 0;
 
    //covers all automatic before and equal to t
    if(curr-prev > 0){
        //minimum gap of automatic triggers required to start a new interval without overlap.
        ll step = 1 + (k/x);
 
        cnt += (curr-prev+step-1)/step;
 
        ll lastcomplete = curr - (curr-prev-1)%step;
        last = lastcomplete*x + k;
    }
 
    //if the last automatic does not cover the t then handle it separately
    if(last < t){
        last = t + k;
        cnt++;
    }
 
    ans += cnt;
}
 
int main() {
    fastio();
 
    int t = 1;
    // cin>>t;
    while(t--){
        ll n,m,x,k;
        cin >> n >> x >> k >> m;
 
        vector<long long> v(m);
        for(auto &val: v) cin >> val;
 
        sort(v.begin(), v.end());
 
        ll last = 0, ans = 0;
 
        for(int i=0; i<m; i++){
            update(v[i], x, k, last, ans);
        }
 
        //handle remaining automatics
        update(n*x, x, k, last, ans);
 
        cout << (ans*k) << endl;
    }
    return 0;
}

Hint 1

Hint 2

Solution

Code

#include <iostream>
#include <vector>
#include <queue>
#include <array>

using namespace std;

const int MAXN = 51;
const int MAXK = 32;

int n, m, k;
vector<int> adj[MAXN];
int child_node[MAXN]; // -1 if no child, else 0..k-1
int outcome[MAXN][MAXN][MAXK][2]; // 0: DRAW, 1: MAX, 2: VECNA
int degree[MAXN][MAXN][MAXK][2];

struct State {
    int m_pos, v_pos, mask, turn;
};

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

    if (!(cin >> n >> m)) return 0;
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    cin >> k;
    for (int i = 1; i <= n; ++i) child_node[i] = -1;
    for (int i = 1; i <= n; ++i) {
        int c; cin >> c;
        if (c != -1) child_node[i] = c;
    }

    queue<State> q;

    // 1. Initialize Degrees and Win/Loss States
    for (int mp = 1; mp <= n; ++mp) {
        for (int vp = 2; vp <= n; ++vp) { // Vecna never at 1
            for (int mask = 0; mask < (1 << k); ++mask) {
                // Max's Turn (0)
                degree[mp][vp][mask][0] = adj[mp].size();
                
                // Vecna's Turn (1)
                for (int next_v : adj[vp]) {
                    if (next_v != 1) degree[mp][vp][mask][1]++;
                }

                // Terminal Condition: Vecna catches Max
                // This happens if Vecna moves to Max, or Max moves to Vecna.
                if (mp == vp) {
                    if (!outcome[mp][vp][mask][0]) { outcome[mp][vp][mask][0] = 2; q.push({mp, vp, mask, 0}); }
                    if (!outcome[mp][vp][mask][1]) { outcome[mp][vp][mask][1] = 2; q.push({mp, vp, mask, 1}); }
                }
                // Terminal Condition: Max reaches cave with all children
                else if (mp == 1 && mask == (1 << k) - 1) {
                    if (!outcome[mp][vp][mask][0]) { outcome[mp][vp][mask][0] = 1; q.push({mp, vp, mask, 0}); }
                    if (!outcome[mp][vp][mask][1]) { outcome[mp][vp][mask][1] = 1; q.push({mp, vp, mask, 1}); }
                }
            }
        }
    }

    // 2. Retrograde Propagation
    while (!q.empty()) {
        State curr = q.front();
        q.pop();
        int res = outcome[curr.m_pos][curr.v_pos][curr.mask][curr.turn];

        if (curr.turn == 1) { // Current is Vecna, Predecessor was Max
            for (int prev_m : adj[curr.m_pos]) {
                // To reach 'curr.mask' at 'curr.m_pos', Max must have had 'prev_mask'
                // at 'prev_m'. 
                for (int prev_mask = 0; prev_mask < (1 << k); ++prev_mask) {
                    int next_mask = prev_mask;
                    if (child_node[curr.m_pos] != -1) next_mask |= (1 << child_node[curr.m_pos]);
                    
                    if (next_mask == curr.mask) {
                        if (outcome[prev_m][curr.v_pos][prev_mask][0]) continue;

                        if (res == 1) { // Max found a move to win
                            outcome[prev_m][curr.v_pos][prev_mask][0] = 1;
                            q.push({prev_m, curr.v_pos, prev_mask, 0});
                        } else if (--degree[prev_m][curr.v_pos][prev_mask][0] == 0) {
                            outcome[prev_m][curr.v_pos][prev_mask][0] = 2;
                            q.push({prev_m, curr.v_pos, prev_mask, 0});
                        }
                    }
                }
            }
        } else { // Current is Max, Predecessor was Vecna
            for (int prev_v : adj[curr.v_pos]) {
                if (prev_v == 1) continue;
                if (outcome[curr.m_pos][prev_v][curr.mask][1]) continue;

                if (res == 2) { // Vecna found a move to win
                    outcome[curr.m_pos][prev_v][curr.mask][1] = 2;
                    q.push({curr.m_pos, prev_v, curr.mask, 1});
                } else if (--degree[curr.m_pos][prev_v][curr.mask][1] == 0) {
                    outcome[curr.m_pos][prev_v][curr.mask][1] = 1;
                    q.push({curr.m_pos, prev_v, curr.mask, 1});
                }
            }
        }
    }

    // 3. Result
    int start_mask = 0;
    if (child_node[2] != -1) start_mask |= (1 << child_node[2]);
    cout << outcome[2][3][start_mask][0] << endl;

    return 0;
}

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

№	Пользователь	Вклад
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	142
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

Блог пользователя vishwas_16.0

Editorial — Codeguerra

CodeGuerra

Approach Overview

Detailed Solution