Problem A: Minimum Function Summation

Given the function f(x) = min_{i∈ℕ⁺}, compute the sum Σ_{i=1}^{n} f(i) modulo 10^9+7 across multiple test cases.

Constraints: n ≤ 10^16, T ≤ 10^4.

Solution Approach:

Analyze the frequency of each value in the sequence f(i). For a particular value x, we need to count integers i satisfying:

• i mod x ≠ 0
• i mod y = 0 for some y ∈ [2, x)

The second condition implies divisibility by lcm(2, 3, ..., x-1). Let t = lcm(2, ..., x-1). The count of numbers satisfying both conditions equals:

⌊n/t⌋ - ⌊n/lcm(t, x)⌋

Implementation:

#include <bits/stdc++.h>
using ll = long long;
const int MOD = 1000000007;

ll solve(ll n) {
    ll result = 0;
    for (ll i = 2, curLcm = 1, newLcm; curLcm <= n; ++i) {
        newLcm = curLcm / std::gcd(curLcm, i) * i;
        result = (result + ((n / curLcm - n / newLcm) % MOD) * i) % MOD;
        curLcm = newLcm;
    }
    return result;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T;
    std::cin >> T;
    while (T--) {
        ll n;
        std::cin >> n;
        std::cout << solve(n) << '\n';
    }
    return 0;
}

Problem B: DZY Loves Modification

Rating: 2000

Given an n×m matrix. Perform k operations where each operation selects either a row or column, adds its sum to the total score, and subtracts p from every cell in that row or column. Maximize the final score.

Constraints: n, m, a_{i,j} ≤ 10^3, k ≤ 10^6, 1 ≤ p ≤ 100.

Solution Approach:

The order of operations doesn't affect optimality. If we select i rows and (k-i) columns, the penalty deducted equals i·(k-i)·p.

Precompute initial row sums and column sums. Use two max-heaps to simulate repeatedly taking the maximum row/column sum, with each extraction reducing future values by p times the opposite dimension.

Implementation:

#include <bits/stdc++.h>
using ll = long long;

int main() {
    int n, m, k;
    ll p;
    std::cin >> n >> m >> k >> p;
    
    std::vector<ll> rowSum(n + 1, 0), colSum(m + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int x;
            std::cin >> x;
            rowSum[i] += x;
            colSum[j] += x;
        }
    }
    
    std::priority_queue<ll> rowPQ, colPQ;
    for (int i = 1; i <= n; ++i) rowPQ.push(rowSum[i]);
    for (int j = 1; j <= m; ++j) colPQ.push(colSum[j]);
    
    std::vector<ll> rowDP(k + 1, 0), colDP(k + 1, 0);
    for (int i = 1; i <= k; ++i) {
        ll cur = rowPQ.top(); rowPQ.pop();
        rowDP[i] = rowDP[i - 1] + cur;
        rowPQ.push(cur - p * m);
    }
    
    for (int i = 1; i <= k; ++i) {
        ll cur = colPQ.top(); colPQ.pop();
        colDP[i] = colDP[i - 1] + cur;
        colPQ.push(cur - p * n);
    }
    
    ll answer = LLONG_MIN;
    for (int i = 0; i <= k; ++i) {
        ll total = rowDP[i] + colDP[k - i] - 1LL * i * (k - i) * p;
        answer = std::max(answer, total);
    }
    
    std::cout << answer << '\n';
    return 0;
}

Problem C: RBS

Rating: 2400

Given n bracket strings, concatenate them in any order to maximize the number of valid bracket sequence prefixes in the final string.

Constraints: n ≤ 20, Σ|s| ≤ 4×10^5.

Solution Approach:

For a string s, define:

• balance[i]: cumulative balance after position i
• minBal[i]: minimum balance over prefix [0, i]

When concatenating string s with current balance b, s is valid if minBal[i] + b ≥ 0 for all i. The number of valid prefixes equals count of positions where balance[i] ≥ -b.

Use segment trees for range queries and DP over subsets with state (mask, lastBalance). Complexity: O(n · 2^n · log n).

Implementation:

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

struct PersistentSegTree {
    struct Node {
        int left, right, cnt;
    };
    vector<Node> tree;
    
    void init(int sz) {
        tree.resize(sz * 6);
    }
    
    void update(int& idx, int prev, int l, int r, int pos) {
        idx = ++tree[0].cnt;
        tree[idx] = tree[prev];
        if (l == r) {
            tree[idx].cnt++;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(tree[idx].left, tree[prev].left, l, mid, pos);
        else update(tree[idx].right, tree[prev].right, mid + 1, r, pos);
        tree[idx].cnt = tree[tree[idx].left].cnt + tree[tree[idx].right].cnt;
    }
    
    int query(int idx, int l, int r, int pos) {
        if (!idx) return 0;
        if (l == r) return tree[idx].cnt;
        int mid = (l + r) >> 1;
        return pos <= mid ? query(tree[idx].left, l, mid, pos) 
                          : query(tree[idx].right, mid + 1, r, pos);
    }
};

struct BracketString {
    int len, offset;
    vector<int> pref, minPref;
    vector<int> roots;
    PersistentSegTree seg;
    
    void build(const string& s) {
        len = s.length();
        pref.resize(len);
        minPref.resize(len);
        roots.resize(len);
        seg.init(len);
        seg.tree[0].cnt = 0;
        seg.tree[0].left = seg.tree[0].right = 0;
        
        int cur = 0;
        for (int i = 0; i < len; ++i) {
            cur += (s[i] == '(' ? 1 : -1);
            pref[i] = cur;
        }
        
        cur = 0;
        for (int i = len - 1; i >= 0; --i) {
            cur = min(cur, pref[i]);
            minPref[i] = cur;
        }
        offset = len;
        
        for (int i = 0; i < len; ++i) {
            seg.update(roots[i], i ? roots[i - 1] : 0, 0, len + len, pref[i] + offset);
        }
    }
    
    int findLastValid(int balance) {
        int target = -balance;
        int lo = 0, hi = len - 1, pos = -1;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (minPref[mid] >= target) {
                pos = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return pos;
    }
    
    int countValidPrefix(int lastPos, int balance) {
        if (lastPos < 0 || balance + offset < 0) return 0;
        return seg.query(lastPos >= 0 ? roots[lastPos] : 0, 0, len + len, balance + offset);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<BracketString> S(n);
    
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        S[i].build(s);
    }
    
    const int LIM = 1 << n;
    vector<int> dp(LIM, INT_MIN), finalBal(LIM, 0);
    dp[0] = 0;
    int answer = 0;
    
    for (int mask = 1; mask < LIM; ++mask) {
        for (int j = 0; j < n; ++j) {
            if (mask & (1 << j)) {
                finalBal[mask] = finalBal[mask ^ (1 << j)] + S[j].pref.back();
                break;
            }
        }
        
        for (int j = 0; j < n; ++j) {
            if (!(mask & (1 << j))) continue;
            
            int prevMask = mask ^ (1 << j);
            int lastPos = S[j].findLastValid(finalBal[prevMask]);
            int validCount = dp[prevMask] + S[j].countValidPrefix(lastPos, finalBal[prevMask]);
            
            answer = max(answer, validCount);
            
            if (lastPos == S[j].len - 1) {
                dp[mask] = max(dp[mask], validCount);
            }
        }
        answer = max(answer, dp[mask]);
    }
    
    cout << answer << '\n';
    return 0;
}

Problem D: DAG Path Construction

Construct a directed acyclic graph (DAG) with vertices numbered 1 to 114 such that:

• The number of distinct paths from vertex 1 to vertex 114 equals n + 1
• Each integer in [0, n] appears exactly once as the total edge weight sum of some path

Constraints: edge weights are non-negative integers, n ≤ 32500. A solution exists with at most 18 vertices and 45 edges, with maximum edge weight ≤ n.

Solution Approach:

This constructive problem can be solved using combinatorial number system representation. The key insight is that any integer in [0, n] can be uniquely represented as a sum of binomial coefficients:

x = C(a₁, 1) + C(a₂, 2) + ... + C(a_k, k), where a₁ < a₂ < ... < a_k

This representation ensures exactly one path for each weight value. Construct vertices representing positions in this combinatorial expansion, with edges weighted according to binomial coefficients.

Implementation:

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> binom;
    for (int i = 1; i <= n + 5; ++i) {
        long long val = 1;
        for (int j = 1; j <= i && val <= n; ++j) {
            val = val * (n + i) / j;
            if (val > n) break;
        }
        if (val <= n) binom.push_back(val);
    }
    
    cout << 18 << ' ' << 44 << '\n';
    
    for (int i = 2; i <= 17; ++i) {
        cout << 1 << ' ' << i << ' ' << (i == 2 ? 0 : binom[i - 3]) << '\n';
    }
    
    for (int i = 2; i <= 17; ++i) {
        for (int j = i + 1; j <= 17; ++j) {
            if (j - i == 1) {
                cout << i << ' ' << j << ' ' << 0 << '\n';
            }
        }
    }
    
    cout << 18 << ' ' << 114 << ' ' << 0 << '\n';
    
    return 0;
}

The construction leverages the uniqueness of combinatorial number system representation to ensure each weight from 0 to n appears exactly once across all paths from source to destination.