Composite Coloring with Bounded Prime Factors

Problem Specification

Given a sequence of composite integers $a$ of length $n$, assign colors such that the greatest common divisor of all numbers sharing the same color exceeds $1$. The total number of distinct colors must not exceed $11$. Constraints: $a_i \le 1000, n \le 1000$.

Algorithmic Approach

Every composite number $x \le 1000$ possesses at least one prime divisor $p \le \sqrt{1000} \approx 31.6$. There are exactly eleven primes within this range. By assigning each integer a color corresponding to its smallest prime factor, we guarantee that all elements of a specific color share a common divisor greater than one. The implementation maps these prime factors to a contiguous color index range to satisfy the output requirement.

Implementation

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

constexpr int MAX_VAL = 1005;
int min_prime_factor[MAX_VAL], color_remap[MAX_VAL];
vector<int> candidate_primes;

void precompute_factors() {
    for (int i = 2; i * i < MAX_VAL; ++i) {
        if (min_prime_factor[i] == 0) {
            for (int j = i * i; j < MAX_VAL; j += i) {
                if (min_prime_factor[j] == 0) min_prime_factor[j] = i;
            }
        }
    }
    for (int i = 2; i < MAX_VAL; ++i) {
        if (min_prime_factor[i] == 0) min_prime_factor[i] = i;
        if (min_prime_factor[i] <= 32) candidate_primes.push_back(min_prime_factor[i]);
    }
    sort(candidate_primes.begin(), candidate_primes.end());
    candidate_primes.erase(unique(candidate_primes.begin(), candidate_primes.end()), candidate_primes.end());
}

void solve_instance() {
    int n; cin >> n;
    vector<int> input_seq(n), output_colors(n);
    for (int &val : input_seq) cin >> val;
    
    vector<int> raw_colors(n);
    for (int idx = 0; idx < n; ++idx) raw_colors[idx] = min_prime_factor[input_seq[idx]];
    
    int palette_size = 0;
    memset(color_remap, 0, sizeof(color_remap));
    for (int idx = 0; idx < n; ++idx) {
        int p = raw_colors[idx];
        if (!color_remap[p]) color_remap[p] = ++palette_size;
        output_colors[idx] = color_remap[p];
    }
    
    cout << palette_size << '\n';
    for (int i = 0; i < n; ++i) cout << output_colors[i] << " \n"[i == n - 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precompute_factors();
    int cases; cin >> cases;
    while (cases--) solve_instance();
    return 0;
}

Handshake Sequence Feasibility

Problem Specification

A group of $n$ individuals enters a hall sequentially, with each person shaking hands with everyone currently present. Given a target sequence of handshake counts, determine if a valid entry/exit order exists. Constraints: $n \le 2 \times 10^5$.

Algorithmic Approach

The handshake count at any moment equals the number of people in the room. Valid transitions involve either incrementing the count by $1$ (a new person enters) or decrementing by $3$ (three people leave simultaneously). By grouping initial indices into buckets based on their handshake count, we can greedily traverse the sequence. When a required bucket is empty, we backtrack in steps of three until a valid group is found or the state drops below zero.

Implementation

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

constexpr int MAX_N = 200005;
vector<int> position_buckets[MAX_N];
int final_order[MAX_N];

void evaluate_sequence() {
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        int handshakes;
        cin >> handshakes;
        position_buckets[handshakes].push_back(i);
    }

    int current_level = 0, placed_count = 1;
    while (placed_count <= n) {
        while (current_level > 0 && position_buckets[current_level].empty()) {
            current_level -= 3;
        }
        if (position_buckets[current_level].empty()) {
            cout << "Impossible\n";
            return;
        }
        final_order[placed_count++] = position_buckets[current_level].back();
        position_buckets[current_level].pop_back();
        current_level++;
    }

    cout << "Possible\n";
    for (int i = 1; i <= n; ++i) {
        cout << final_order[i] << " \n"[i == n];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    evaluate_sequence();
    return 0;
}

Maximum Greater-Than-or-Equal Subarray Sum

Problem Specification

Determine if an array $A$ satisfies the condition that for all subarrays, the maximum element is at least the subarray sum. Constraints: $n \le 2 \times 10^5$.

Algorithmic Approach

The condition fails if any contiguous segment has a positive total sum strictly exceeding its peak value. We process the array bidirectionally using a monotonic decreasing stack. For each element acting as a segment maximum, we verify whether the accumulated prefix or suffix sums within its dominance range yield a positive value. If a violation is detected during stack compression, the array is invalid.

Implementation

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

constexpr int MAX_LEN = 200010;
int sequence[MAX_LEN], prefix_acc[MAX_LEN], suffix_acc[MAX_LEN];

void check_validity() {
    int n; cin >> n;
    prefix_acc[0] = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> sequence[i];
        prefix_acc[i] = prefix_acc[i-1] + sequence[i];
    }
    suffix_acc[n+1] = 0;
    for (int i = n; i >= 1; --i) suffix_acc[i] = suffix_acc[i+1] + sequence[i];

    struct StackFrame { int value; int index; };
    vector<StackFrame> stack_vec;
    stack_vec.reserve(n);

    auto process_left = [&]() {
        stack_vec.clear();
        for (int i = 1; i <= n; ++i) {
            int max_segment = 0;
            while (!stack_vec.empty() && stack_vec.back().value <= sequence[i]) {
                max_segment = max(max_segment, prefix_acc[i-1] - prefix_acc[stack_vec.back().index - 1]);
                stack_vec.pop_back();
            }
            if (max_segment > 0) {
                cout << "NO\n";
                return true;
            }
            stack_vec.push_back({sequence[i], i});
        }
        return false;
    };

    if (process_left()) return;

    stack_vec.clear();
    for (int i = n; i >= 1; --i) {
        int max_segment = 0;
        while (!stack_vec.empty() && stack_vec.back().value <= sequence[i]) {
            max_segment = max(max_segment, suffix_acc[i+1] - suffix_acc[stack_vec.back().index + 1]);
            stack_vec.pop_back();
        }
        if (max_segment > 0) {
            cout << "NO\n";
            return;
        }
        stack_vec.push_back({sequence[i], i});
    }
    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) check_validity();
    return 0;
}

Optimal Stack Operations Maximization

Problem Specification

Process an array sequential, choosing between pushing an element onto a stack or popping if non-empty. Maximize the final stack sum.

Algorithmic Approach

Commutativity of push-pop sequences reveals that any valid operation stream can be reduced to either accumulating the current value or discarding both the current and preceding elements. This yields the recurrence $dp[i] = \max(dp[i-1] + val_i, dp[i-2])$, solvable in linear time with constant space optimization.

Implemantation

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<int> values(n);
    for (int &x : values) cin >> x;

    if (n == 0) { cout << 0; return 0; }
    vector<int> dp(n + 1, 0);
    dp[1] = values[0];
    
    for (int i = 2; i <= n; ++i) {
        dp[i] = max(dp[i-1] + values[i-1], dp[i-2]);
    }
    
    cout << dp[n] << '\n';
    return 0;
}

Minimum Adjacent Swap Cost

Problem Specification

Sort a permutation by swapping adjacent elements. The cost of each swap equals the left element's value. Find the minimum total cost. Constraints: $n \le 2 \times 10^5$.

Algorithmic Approach

The total expense corresponds to the cumulative displacement cost of each element moving past larger values. By tracking initial positions and utilizing a Fenwick tree to count preceding larger elements, we compute the required shifts. The solution aggregates positional deltas weighted by inversion counts to derive the minimal expanse.

Implementation

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

constexpr int MAX_SZ = 200005;
int fenwick_tree[MAX_SZ], initial_pos[MAX_SZ], inv_count[MAX_SZ];
struct Element { int val; int idx; } elems[MAX_SZ];

int query_bit(int idx) {
    int res = 0;
    for (; idx > 0; idx -= idx & -idx) res += fenwick_tree[idx];
    return res;
}

void update_bit(int idx, int delta) {
    for (; idx < MAX_SZ; idx += idx & -idx) fenwick_tree[idx] += delta;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> elems[i].val;
        elems[i].idx = i;
        inv_count[i] = query_bit(MAX_SZ - 1) - query_bit(elems[i].val);
        update_bit(elems[i].val, 1);
    }

    sort(elems + 1, elems + n + 1, [](const Element &a, const Element &b) {
        return a.val < b.val;
    });

    long long total_cost = 0;
    for (int i = 1; i <= n; ++i) {
        long long displacement = elems[i].idx - inv_count[elems[i].idx];
        long long target = i;
        total_cost += (displacement - 1 + target) * abs(displacement - target) / 2;
    }
    cout << total_cost << '\n';
    return 0;
}

Optimal Binary Flip Sequences

Problem Specification

Transform binary array $A$ to match $B$ using element flips. Each operation adds a cost proportional to current $1$s wieghted by array $C$. Minimize total expense.

Algorithmic Approach

Categorize indices into three groups: forced $1 \to 0$, forced $0 \to 1$, and neutral $1 \to 1$ candidates. Sorting costs and utilizing two Fenwick trees (sum and count) allows greedy insertion of neutral flips at optimmal positions. Iteratively updating the cumulative expense while tracking the global minimum yields the solution.

Implementation

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

constexpr int MAX_DIM = 1000005;
struct Fenwick {
    int tree[MAX_DIM];
    void add(int idx, int delta) {
        for (; idx < MAX_DIM; idx += idx & -idx) tree[idx] += delta;
    }
    int sum(int idx) {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) res += tree[idx];
        return res;
    }
} val_tree, cnt_tree;

int n, src[MAX_DIM], tgt[MAX_DIM], costs[MAX_DIM];
vector<int> group_10, group_01, group_11;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> src[i];
    for (int i = 1; i <= n; ++i) cin >> tgt[i];
    for (int i = 1; i <= n; ++i) {
        cin >> costs[i];
        if (src[i] == 1 && tgt[i] == 0) group_10.push_back(costs[i]);
        else if (src[i] == 0 && tgt[i] == 1) group_01.push_back(costs[i]);
        else if (src[i] == 1 && tgt[i] == 1) group_11.push_back(costs[i]);
    }

    auto desc = [](int a, int b) { return a > b; };
    sort(group_10.begin(), group_10.end(), desc);
    sort(group_01.begin(), group_01.end());
    sort(group_11.begin(), group_11.end(), desc);

    long long base_expense = 0, suffix_sum = 0, best_res = 0;
    vector<long long> suffix_acc(group_11.size() + 1, 0);
    for (int i = group_11.size() - 1; i >= 0; --i) suffix_acc[i] = suffix_acc[i+1] + group_11[i];

    for (size_t i = 0; i < group_10.size(); ++i) base_expense += group_10[i] * i;
    for (size_t i = 0; i < group_01.size(); ++i) base_expense += group_01[i] * (group_01.size() - i);
    for (int c : group_11) base_expense += 1LL * c * (group_10.size() + group_01.size());
    best_res = base_expense;

    for (int c : group_10) { val_tree.add(c, c); cnt_tree.add(c, 1); }
    for (int c : group_01) { val_tree.add(c, c); cnt_tree.add(c, 1); }

    for (int i = 0; i < group_11.size(); ++i) {
        int cost = group_11[i];
        base_expense += val_tree.sum(cost);
        base_expense += 1LL * (group_10.size() + group_01.size() + 2*(i+1) - cnt_tree.sum(cost) - 1) * cost;
        base_expense -= 1LL * (group_10.size() + group_01.size() + 2*i) * cost;
        base_expense += suffix_acc[i+1] * 2;
        best_res = min(best_res, base_expense);
        val_tree.add(cost, cost);
        cnt_tree.add(cost, 1);
    }
    cout << best_res << '\n';
    return 0;
}

Key Management Profit Maximization

Problem Specification

Open $n$ chests sequentially. Each can be opened with fixed cost $k$ or for free (halving all subsequent rewards). Maximize net profit. $n \le 10^5$.

Algorithmic Approach

Free openings halve rewards exponentially; applying them more than $\log_2(10^9) \approx 30$ times reduces values to zero. A dynamic programming approach tracks the current chest index and the number of free operations used, capped at $30$. Transitions evaluate paying the fixed fee versus consuming a free operation, propagating the maximum achievable profit.

Implementation

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

constexpr int MAX_CHESTS = 100005;
constexpr int MAX_FREE = 32;
long long base_vals[MAX_CHESTS][MAX_FREE], dp_table[MAX_CHESTS][MAX_FREE];

void compute_max_profit() {
    int n, fee; cin >> n >> fee;
    for (int i = 1; i <= n; ++i) {
        cin >> base_vals[i][0];
        for (int j = 1; j < MAX_FREE; ++j) base_vals[i][j] = base_vals[i][j-1] / 2;
    }

    for (int i = 0; i <= n; ++i) fill(dp_table[i], dp_table[i] + MAX_FREE, -2e18);
    dp_table[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
        int limit = min(i, 30);
        for (int j = 0; j <= limit; ++j) {
            dp_table[i][j] = max(dp_table[i][j], dp_table[i-1][j] + base_vals[i][j] - fee);
            if (j > 0) dp_table[i][j] = max(dp_table[i][j], dp_table[i-1][j-1] + base_vals[i][j]);
        }
        dp_table[i][30] = max(dp_table[i][30], dp_table[i-1][30]);
    }

    long long ans = -2e18;
    for (int j = 0; j <= 30; ++j) ans = max(ans, dp_table[n][j]);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int cases; cin >> cases;
    while (cases--) compute_max_profit();
    return 0;
}

Lattice Path Counting in Rectangles

Problem Specification

Count monotonic paths from $(0,0)$ to any coordinate within rectangle $[r_1, r_2] \times [c_1, c_2]$. Modulo arithmetic applies.

Algorithmic Approach

Paths to $(r,c)$ follow $\binom{r+c}{c}$. Summing over the rectangle reduces to evaluating a $2$D prefix sum of binomial coefficients. The hockey-stick identity $\sum_{i=0}^r \binom{i+c}{c} = \binom{r+c+1}{c+1}$ simplifies the inner summation, enabling $O(1)$ evaluation per rectangle corner after factorial precomputation.

Implementation

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

constexpr int MOD = 1000000007;
constexpr int MAX_N = 400005;
long long fact[MAX_N], inv_fact[MAX_N], mod_inv[MAX_N];

void prepare_combinatorics() {
    fact[0] = inv_fact[0] = 1;
    mod_inv[1] = 1;
    for (int i = 2; i < MAX_N; ++i) mod_inv[i] = MOD - (MOD/i) * mod_inv[MOD%i] % MOD;
    for (int i = 1; i < MAX_N; ++i) {
        fact[i] = fact[i-1] * i % MOD;
        inv_fact[i] = inv_fact[i-1] * mod_inv[i] % MOD;
    }
}

long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD;
}

long long rectangle_paths(int r, int c) {
    return (nCr(r + c + 1, c + 1) - 1 + MOD) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    prepare_combinatorics();
    long long ans = (rectangle_paths(r2, c2) - rectangle_paths(r1-1, c2) - rectangle_paths(r2, c1-1) + rectangle_paths(r1-1, c1-1)) % MOD;
    cout << (ans + 2*MOD) % MOD << '\n';
    return 0;
}

Power Up Merging Configurations

Problem Specification

Given a multiset, merge pairs of equal integers $x$ into $x+1$. Count distinct final configurations.

Algorithmic Approach

Model the merging process by tracking propagation counts across integer levels. Dynamic programming computes valid states for each value, utilizing prefix sums to transition efficiently. The algorithm aggregates counts while ensuring merge constraints are satisfied.

Implementation

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

constexpr int MOD = 998244353;
constexpr int MAX_VAL = 300100;
int freq[MAX_VAL], dp_state[MAX_VAL], prefix_sum[MAX_VAL];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    int min_v = 1e9, max_v = 0;
    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        freq[x]++;
        min_v = min(min_v, x);
        max_v = max(max_v, x);
    }

    int carry = freq[min_v];
    fill(prefix_sum, prefix_sum + carry + 1, 1);

    for (int val = min_v + 1; val <= max_v + 60; ++val) {
        carry = freq[val] + carry / 2;
        for (int i = 0; i < freq[val]; ++i) dp_state[i] = 0;
        for (int i = freq[val]; i <= carry; ++i) dp_state[i] = prefix_sum[(i - freq[val]) * 2];
        
        prefix_sum[carry] = dp_state[carry];
        for (int i = carry - 1; i >= 0; --i) {
            prefix_sum[i] = (prefix_sum[i+1] + dp_state[i]) % MOD;
        }
    }
    cout << prefix_sum[0] << '\n';
    return 0;
}

Segmentation Product Summation

Problem Specification

Partition an $n$-digit number into segments. Sum the products of segment values across all partitions. Modulo $998244353$.

Algorithmic Approach

Let $dp[i]$ denote the total sum for the first $i$ digits. The recurrence $dp[i] = \sum_{j=0}^{i-1} dp[j] \times S(j+1, i)$ can be optimized by separating the digit contribution and scaling previous results. This simplifies to $dp[i] = 10 \cdot dp[i-1] + d_i \cdot \sum_{j=0}^{i-1} dp[j]$, enabling linear execution.

Implementation

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

constexpr int MOD = 998244353;
constexpr int MAX_LEN = 200005;
long long dp_val[MAX_LEN], prefix_acc[MAX_LEN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; string s;
    cin >> n >> s;
    s = " " + s;
    int digit = s[1] - '0';
    dp_val[1] = digit;
    prefix_acc[1] = 1;

    for (int i = 2; i <= n; ++i) {
        digit = s[i] - '0';
        dp_val[i] = (dp_val[i-1] * 10 + prefix_acc[i-1] * digit) % MOD;
        prefix_acc[i] = (prefix_acc[i-1] + dp_val[i-1]) % MOD;
        dp_val[i] = (dp_val[i] + dp_val[i-1] * digit) % MOD;
    }
    cout << dp_val[n] << '\n';
    return 0;
}

Range Zero Transformation Queries

Problem Specification

Given $q$ queries, determine if a subarray $[l, r]$ can be zeroed using length-$k$ uniform increments.

Algorithmic Approach

Transforming the array via difference sequences reveals that operations affect indices modulo $k$ independently. By maintaining prefix sums of the difference array partitioned by residue class, each query validates consistency across relevant classes. Boundary conditions and modulo alignment are verified in constant time.

Implementation

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

constexpr int MAX_N = 200005;
constexpr int MAX_K = 10;
long long arr[MAX_N], diff_prefix[MAX_N][MAX_K];

void handle_query() {
    int l, r, n, k;
    cin >> l >> r;
    for (int mod_res = max(r - k + 2, l); mod_res <= r; ++mod_res) {
        long long val = diff_prefix[mod_res][mod_res % k] - diff_prefix[l-1][mod_res % k];
        if (mod_res % k == l % k) val += arr[l-1];
        if (val != 0) {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        for (int j = 0; j < k; ++j) diff_prefix[i][j] = diff_prefix[i-1][j];
        diff_prefix[i][i % k] += arr[i] - arr[i-1];
    }
    int q; cin >> q;
    while (q--) handle_query();
    return 0;
}