Problem A: Operations with Inversions

Greedy solution. Skipped for brevity.

Problem B: Optimal Shifts

Greedy solution. Skipped for brevity.

Problem C: Odd Process

Problem Statement: You have n numbers, each with a value a_i. You need to perform k rounds of operations where you can place a number into a bag (each number can only be placed once). When the sum of numbers in the bag becomes even, the bag clears. Find the maximum possible sum in the bag for each k from 1 to n.

Solution: Case analysis reveals the following:

When the bag is empty, you can only place an odd number; placing an even number would immediately clear the bag. When the bag contains numbers, the sum must be odd (otherwise it would have cleared), so you can only place even numbers.

Therefore, if the bag has numbers, it contains exactly one odd number plus several even numbers.

Case 1: k ≤ 1 + number_of_even_numbers The answer is the largest odd number plus the largest (k-1) even numbers. Handle the special case when no odd numbers exist.

Case 2: k > 1 + number_of_even_numbers After placing the largest odd number and all even numbers, we need c additional numbers where c = k - (even_count + 1).

• If c is even: Place c odd numbers first (clearing the bag), then place the largest odd and all evens. Answer is their sum.
• If c is odd: Try to swap one even with one odd to make c even. If possible, apply the same logic. Otherwise (all odds used, meaning we have an even number of odds), the bag will definitely be cleared, and the answer is 0.

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

using int64 = long long;
const int MAXN = 200005;
const int64 MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int64> values(n + 1);
        for (int i = 1; i <= n; i++) cin >> values[i];
        
        vector<int64> odds{0}, evens{0};
        int oddCnt = 0, evenCnt = 0;
        
        for (int i = 1; i <= n; i++) {
            if (values[i] % 2 == 0) {
                evens.push_back(values[i]);
                evenCnt++;
            } else {
                odds.push_back(values[i]);
                oddCnt++;
            }
        }
        
        sort(evens.begin() + 1, evens.end(), greater<int64>());
        sort(odds.begin() + 1, odds.end(), greater<int64>());
        
        vector<int64> prefOdd(oddCnt + 1, 0), prefEven(evenCnt + 1, 0);
        for (int i = 1; i <= oddCnt; i++) prefOdd[i] = prefOdd[i-1] + odds[i];
        for (int i = 1; i <= evenCnt; i++) prefEven[i] = prefEven[i-1] + evens[i];
        
        for (int k = 1; k <= n; k++) {
            if (oddCnt == 0) {
                cout << 0 << " ";
                continue;
            }
            if (evenCnt == 0) {
                cout << (k % 2 == 1 ? odds[1] : 0) << " ";
                continue;
            }
            
            if (k <= evenCnt + 1) {
                cout << odds[1] + prefEven[k-1] << " ";
            } else {
                int remaining = k - (evenCnt + 1);
                if (remaining % 2 == 0) {
                    cout << odds[1] + prefEven[evenCnt] << " ";
                } else {
                    if (remaining + 1 == oddCnt) {
                        cout << 0 << " ";
                    } else {
                        cout << odds[1] + prefEven[evenCnt - 1] << " ";
                    }
                }
            }
        }
        cout << "\n";
    }
    return 0;
}

Problem D: Fibonacci Paths

Problem Statement: Given a directed graph with n vertices and m edges, each vertex has a weight a_i. Count the number of paths that form a generalized Fibonacci sequence. A sequence is a generalized Fibonacci if for all i ≥ 2, a_i = a_{i-1} + a_{i-2}. The answer is computed modulo 998244353.

Solution: Key observation: For a generalized Fibonacci sequence with length ≥ 2, we have a_i > a_{i-1} for all i ≥ 2.

Sort all vertices by weight. Process in order of increasing weight. For each vertex, use an unordered_map to track the number of ways to reach it with a specific next value.

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

using int64 = long long;
const int MAXN = 200005;
const int64 MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        
        vector<pair<int64, int>> vertices(n + 1);
        vector<int64> weight(n + 1);
        
        for (int i = 1; i <= n; i++) {
            cin >> vertices[i].first;
            weight[i] = vertices[i].first;
            vertices[i].second = i;
        }
        
        vector<vector<int>> adj(n + 1);
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
        }
        
        vector<unordered_map<int64, int64>> dp_state(n + 1);
        for (int i = 1; i <= n; i++) {
            for (int v : adj[i]) {
                int64 target = weight[i] + weight[v];
                dp_state[v][target] = (dp_state[v][target] + 1) % MOD;
            }
        }
        
        sort(vertices.begin() + 1, vertices.end());
        int64 answer = 0;
        
        for (int idx = 1; idx <= n; idx++) {
            int u = vertices[idx].second;
            int64 currentWeight = vertices[idx].first;
            
            for (int v : adj[u]) {
                int64 neighborWeight = weight[v];
                if (neighborWeight == currentWeight) continue;
                
                int64 count = dp_state[u][neighborWeight];
                int64 newTarget = currentWeight + neighborWeight;
                dp_state[v][newTarget] = (dp_state[v][newTarget] + count) % MOD;
            }
        }
        
        for (int i = 1; i <= n; i++) {
            for (auto& entry : dp_state[i]) {
                answer = (answer + entry.second) % MOD;
            }
        }
        
        cout << answer << "\n";
    }
    return 0;
}

Problem E: Remove at the Lowest Cost

Problem Statement: Given a sequence of n elements, each with two values a_i and c_i. Perform n-1 operations: select two adjacent elements, remove the one with smaller a_i (ties broken arbitrarily), and pay the smaller c_i as cost. After n-1 operations, the minimum total cost is the sum of all optimal removal costs minus the maximum one.

Additionally, there is a permutation p. As we process p_1, p_2, ..., p_n, we set c_{p_i} = 0 permanently. After each zeroing, report the minimum cost for the current state.

Solution: The optimal strategy is to always select the element with minimum c_i for removal (greedy works here). Each element has an optimal removal cost d_i. The answer without zeroing is sum(d_i) - max(d_i).

For the zeroing queries, we need to find the interval [l_i, r_i] that element i can remove. This uses binary search with sparse tables for range maximum queries.

Preprocessing: For each position i, find the maximum range where a_j ≤ a_i holds, using binary search with RMQ tables. Then process positions by increasing c_i to assign d values.

The final answers are maintained using a segment tree with lazy propagation for range updates (setting d_i to 0 when c_i is zeroed).

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

using int64 = long long;
const int MAXN = 200005;

struct Node {
    int l, r;
    int64 sum, maxv, lazy;
};

struct SegTree {
    vector<Node> tree;
    int n;
    
    SegTree(int n) : n(n) {
        tree.resize(4 * (n + 5));
    }
    
    void build(int idx, int l, int r, const vector<int64>& arr) {
        tree[idx].l = l;
        tree[idx].r = r;
        if (l == r) {
            tree[idx].sum = tree[idx].maxv = arr[l];
            tree[idx].lazy = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(idx << 1, l, mid, arr);
        build(idx << 1 | 1, mid + 1, r, arr);
        tree[idx].sum = tree[idx << 1].sum + tree[idx << 1 | 1].sum;
        tree[idx].maxv = max(tree[idx << 1].maxv, tree[idx << 1 | 1].maxv);
        tree[idx].lazy = 0;
    }
    
    void pushDown(int idx) {
        if (tree[idx].lazy) {
            int lc = idx << 1, rc = idx << 1 | 1;
            tree[lc].lazy = tree[rc].lazy = 1;
            tree[lc].sum = tree[rc].sum = 0;
            tree[lc].maxv = tree[rc].maxv = 0;
            tree[idx].lazy = 0;
        }
    }
    
    void updateRange(int idx, int ql, int qr) {
        if (ql > qr) return;
        if (ql <= tree[idx].l && tree[idx].r <= qr) {
            tree[idx].lazy = 1;
            tree[idx].sum = tree[idx].maxv = 0;
            return;
        }
        pushDown(idx);
        int mid = (tree[idx].l + tree[idx].r) >> 1;
        if (ql <= mid) updateRange(idx << 1, ql, qr);
        if (qr > mid) updateRange(idx << 1 | 1, ql, qr);
        tree[idx].sum = tree[idx << 1].sum + tree[idx << 1 | 1].sum;
        tree[idx].maxv = max(tree[idx << 1].maxv, tree[idx << 1 | 1].maxv);
    }
    
    int64 query() {
        return tree[1].sum - tree[1].maxv;
    }
};

int log2Table[MAXN];
int64 maxSparse[MAXN][18], minSparse[MAXN][18];
int64 a[MAXN], cost[MAXN], perm[MAXN];
int leftBound[MAXN], rightBound[MAXN], removeCost[MAXN];

int64 queryMax(int l, int r) {
    int k = log2Table[r - l + 1];
    return max(maxSparse[l][k], maxSparse[r - (1 << k) + 1][k]);
}

int64 queryMin(int l, int r) {
    int k = log2Table[r - l + 1];
    return min(minSparse[l][k], minSparse[r - (1 << k) + 1][k]);
}

int findRightBound(int pos) {
    int lo = pos, hi = MAXN - 5;
    while (lo < hi) {
        int mid = (lo + hi + 1) >> 1;
        if (queryMax(pos, mid) <= a[pos]) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

int findLeftBound(int pos) {
    int lo = 1, hi = pos;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (queryMax(mid, pos) <= a[pos]) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

void preprocess(int n) {
    for (int i = 1; i <= n; i++) {
        maxSparse[i][0] = minSparse[i][0] = a[i];
    }
    for (int j = 1; j <= 17; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            maxSparse[i][j] = max(maxSparse[i][j-1], maxSparse[i + (1 << (j-1))][j-1]);
            minSparse[i][j] = min(minSparse[i][j-1], minSparse[i + (1 << (j-1))][j-1]);
        }
    }
    
    set<int> active;
    active.insert(0);
    active.insert(n + 1);
    
    vector<pair<int64, int>> costOrder;
    for (int i = 1; i <= n; i++) {
        costOrder.push_back({cost[i], i});
        active.insert(i);
        leftBound[i] = findLeftBound(i);
        rightBound[i] = findRightBound(i);
    }
    sort(costOrder.begin(), costOrder.end());
    
    for (auto& p : costOrder) {
        int id = p.second;
        int l = leftBound[id];
        int r = rightBound[id];
        
        auto it = active.lower_bound(l);
        vector<int> toErase;
        while (it != active.end() && *it <= r) {
            removeCost[*it] = cost[id];
            toErase.push_back(*it);
            ++it;
        }
        for (int x : toErase) active.erase(x);
    }
}

void clearSparse(int n) {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= 17; j++) {
            maxSparse[i][j] = minSparse[i][j] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    log2Table[1] = 0;
    for (int i = 2; i < MAXN; i++) log2Table[i] = log2Table[i >> 1] + 1;
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> cost[i];
        for (int i = 1; i <= n; i++) cin >> perm[i];
        
        preprocess(n);
        
        SegTree st(n);
        vector<int64> initArr(n + 1);
        for (int i = 1; i <= n; i++) initArr[i] = removeCost[i];
        st.build(1, 1, n, initArr);
        
        cout << st.query() << " ";
        for (int i = 1; i <= n; i++) {
            int idx = perm[i];
            st.updateRange(1, leftBound[idx], rightBound[idx]);
            cout << st.query() << " ";
        }
        cout << "\n";
        clearSparse(n);
    }
    return 0;
}

Problem F: Omega Numbers

Problem Statement: Define ω(n) as the number of distinct prime factors of n. Given sequence a and integer k, compute: f(a,k) = Σ ω(a_i · a_j)^k for all i < j, modulo 998244353.

Solution: Since n ≤ 2·10^5, we have ω(n) ≤ 6 (because the product of first 6 primes 2·3·5·7·11·13 = 30030 > 2·10^5). Therefore ω(a_i · a_j) ≤ 12.

Key formula: ω(a_i · a_j) = ω(a_i) + ω(a_j) - ω(gcd(a_i, a_j))

We use DP with state dp[g][t] representing pairs (i,j) where ω(a_i) + ω(a_j) = t and gcd(a_i, a_j) = g.

First, compute cnt[m][w] = number of elements that are multiples of m with ω-value w. This is O(n log n) using harmonic series traversal.

Then process dp from large to small to handle inclusion-exclusion:

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

using int64 = long long;
const int MAXN = 200005;
const int64 MOD = 998244353;

int64 g[MAXN];

int64 modPow(int64 base, int64 exp) {
    int64 result = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) result = result * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

array<int64, 3> factorInfo(int64 x, int64 limit) {
    int64 product = 1;
    int64 extra = 1;
    int64 count = 0;
    
    for (int64 p = 2; p * p <= x; p++) {
        if (x % p == 0) {
            product *= p;
            count++;
            while (x % p == 0) x /= p;
        }
    }
    
    if (x != 1) {
        if (x <= limit) {
            product *= x;
            count++;
        } else {
            extra = x;
            count++;
        }
    }
    return {product, extra, count};
}

void initialize(int n) {
    for (int i = 1; i <= n; i++) {
        g[i] = factorInfo(i, n)[2];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    initialize(MAXN - 5);
    
    while (T--) {
        int n;
        int64 k;
        cin >> n >> k;
        
        vector<int64> arr(n + 1), frequency(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
            frequency[arr[i]]++;
        }
        
        vector<vector<int64>> cnt(n + 1, vector<int64>(15, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j += i) {
                cnt[i][g[j]] += frequency[j];
            }
        }
        
        vector<vector<int64>> dp(n + 1, vector<int64>(15, 0));
        
        for (int i = n; i >= 1; i--) {
            for (int x = 0; x <= 6; x++) {
                for (int y = 0; y <= 6; y++) {
                    if (x != y) {
                        dp[i][x + y] = (dp[i][x + y] + cnt[i][x] * cnt[i][y]) % MOD;
                    } else {
                        dp[i][x + y] = (dp[i][x + y] + cnt[i][x] * (cnt[i][y] - 1)) % MOD;
                    }
                }
            }
            for (int mult = i * 2; mult <= n; mult += i) {
                for (int j = 1; j < 15; j++) {
                    dp[i][j] = (dp[i][j] - dp[mult][j] + MOD) % MOD;
                }
            }
        }
        
        int64 answer = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 15; j++) {
                int64 exponent = j - g[i];
                answer = (answer + dp[i][j] * modPow(exponent, k)) % MOD;
            }
        }
        
        answer = answer * modPow(2, MOD - 2) % MOD;
        cout << answer << "\n";
    }
    return 0;
}

Time Complexity: O(n log n) for precomputation, O(n) for the DP phase. The prime factorization of numbers up to n is O(n√n) in worst case, but can be optimized.