Problem 1: Optimized Dynamic Programming with Prefix Sums

This problem involves a basic dynamic programming approach where we process from the end to the beginning. The naive solution has a time complexity of O(n²), but we can optimize it using prefix sums and binary search.

We maintain a prefix sum array and for each position, use binary search to find farthest index where the sum constraint is still satisfied. This allows us to compute the DP state efficiently.

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

const int N = 1e5 + 5;
int n, limit;
int values[N], prefix[N];
int dp[N];

int main() {
    cin >> n >> limit;
    for (int i = 1; i <= n; ++i) {
        cin >> values[i];
        prefix[i] = prefix[i - 1] + values[i];
    }

    dp[n] = 1;
    for (int i = n - 1; i >= 1; --i) {
        int left = i, right = n, best = i - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (prefix[mid] - prefix[i - 1] <= limit) {
                best = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        dp[i] = dp[best + 1] + 1;
    }

    for (int i = 1; i <= n; ++i) {
        cout << dp[i] << " ";
    }
    return 0;
}

Problem 2: Tree Dynamic Programming with State Transitions

This problem involves a binary tree structure and requires a bottom-up dynamic programming approach. We define a 3-dimensional DP state where each node has a state based on how many children belong to a specific group and which group the current node belongs to.

The transition logic involves combining results from left and right children while considering edge weights. The solution uses depth-first search to process nodes in post-order.

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

const int MAX = 1005;
int n;
int depth[MAX], size[MAX];
int dp[MAX][MAX][2]; // dp[node][count][group]

vector<pair<int, int>> tree[MAX];

void dfs(int node) {
    size[node] = 1;
    for (auto child : tree[node]) {
        int v = child.first;
        dfs(v);
        size[node] += size[v];
    }

    if (size[node] == 1) {
        dp[node][1][1] = 0;
        dp[node][0][0] = 0;
        return;
    }

    for (int i = 0; i <= min(size[node], n/2); ++i) {
        for (int j = 0; j <= i; ++j) {
            // Transition logic combining left and right children
            // This is simplified - actual transitions involve multiple cases
            dp[node][i][0] = max(dp[node][i][0], dp[node*2][j][0] + dp[node*2+1][i-j][0]);
            // Additional cases with edge weights and different group combinations
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int parent;
        cin >> parent >> depth[i];
        tree[parent].push_back({i, depth[i]});
    }

    memset(dp, -0x3f, sizeof(dp));
    dfs(1);
    cout << max(dp[1][n/2][0], dp[1][n/2][1]);
    return 0;
}

Problem 3: Recursive Coloring Strategy with Uncertainty Handling

This problem involves determining the color of a root node in a tree based on leaf values. The strategy involves a bottom-up approach where each node's color is determined by its children.

If a node has more blue chilrden, it becomes blue. If more red, it becomes red. If equal, it's uncertain. For uncertain root nodes, we need to explore paths to determine the minimum changes needed to make it red.

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

const int MAX = 1e5 + 5;
int n;
int color[MAX];
vector<int> children[MAX];
vector<int> result;

void dfs1(int node) {
    if (children[node].empty()) return;

    int cnt[2] = {0};
    for (int child : children[node]) {
        dfs1(child);
        if (color[child] != -1) cnt[color[child]]++;
    }

    if (cnt[0] > cnt[1]) color[node] = 0;
    else if (cnt[0] == cnt[1]) color[node] = -1;
    else color[node] = 1;
}

void dfs2(int node) {
    if (children[node].empty()) {
        if (color[node] == -1) result.push_back(node);
        return;
    }

    if (color[node] == -1) {
        for (int child : children[node]) {
            if (color[child] == 0) continue;
            dfs2(child);
        }
    } else if (color[node] == 1) {
        int cnt[2] = {0};
        for (int child : children[node]) {
            if (color[child] != -1) cnt[color[child]]++;
        }

        if (cnt[1] - cnt[0] == 1) {
            for (int child : children[node]) {
                if (color[child] == 0) continue;
                dfs2(child);
            }
        }
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int parent;
        cin >> parent;
        children[parent].push_back(i);
    }

    for (int i = 1; i <= n; ++i) cin >> color[i];

    dfs1(1);

    if (color[1] == 1) {
        cout << -1 << endl;
        return;
    } else if (color[1] == 0) {
        for (int i = 1; i <= n; ++i) {
            if (children[i].empty() && color[i] == -1) {
                result.push_back(i);
            }
        }
    } else {
        dfs2(1);
    }

    sort(result.begin(), result.end());
    cout << result.size() << endl;
    for (int val : result) cout << val << " ";
    cout << endl;
}

Problem 4: Game Theory with Modular Reductions

This problem involves analyzing a game theory scenario where players take turns removing values from piles. The key insight is that we can reduce each pile modulo (a + b) without changing the outcome.

We categorize piles into different ranges and analyze their impact on the game outcome based on parity and existence of certain pile sizes.

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

const int MOD = 1e9 + 7;
int power(int x, int exp) {
    int result = 1;
    while (exp > 0) {
        if (exp & 1) result = 1LL * result * x % MOD;
        x = 1LL * x * x % MOD;
        exp >>= 1;
    }
    return result;
}

int n, a, b;
int count[3];
int answer[4];

void solve() {
    cin >> n >> a >> b;
    bool swapped = false;
    if (a > b) {
        swap(a, b);
        swapped = true;
    }

    int multiplier = 1;
    while (n--) {
        int x;
        cin >> x;
        x %= (a + b);
        if (x < a) {
            multiplier = 2LL * multiplier % MOD;
        } else if (x < b) {
            count[0]++;
        } else if (x < 2 * a) {
            count[1]++;
        } else {
            count[2]++;
        }
    }

    answer[0] = (1LL * (power(2, count[0]) - 1) * power(2, count[1] + count[2])) % MOD;
    answer[0] = (1LL * answer[0] + 1LL * count[2] * power(2, count[1] - 1)) % MOD;
    answer[0] = (1LL * answer[0] + 1LL * (power(2, count[2]) - 1 - count[2]) * power(2, count[1])) % MOD;

    answer[2] = power(2, count[1] - 1);
    answer[3] = answer[2];

    if (swapped) swap(answer[0], answer[1]);
    for (int i = 0; i < 4; ++i) {
        cout << 1LL * answer[i] * multiplier % MOD << " ";
    }
    cout << endl;
}