Canvas Painting

The problem involves finding the maximum number of effective operations to reduce distinct colors. With n initial colors, each operation can reduce one color by making two positions share the same color. The answer is n minus the maximum effective operations.

Algorithm: Group painting intervals by their left endpoint. A min-heap tracks available intervals by their right endpoint. Process positions from left to right. At each position, select the available interavl with the smallest right endpoint to minimize waste. Increment the count for each used interval. The final result is the initial count minus the used operations.

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using ll = long long;

void process_case() {
    int interval_cnt, pos_limit;
    std::cin >> interval_cnt >> pos_limit;

    std::map<int, std::vector<int>> start_to_ends;
    for (int i = 0; i < interval_cnt; ++i) {
        int left, right;
        std::cin >> left >> right;
        start_to_ends[left].push_back(right);
    }

    int result = pos_limit;
    std::vector<std::pair<int, std::vector<int>>> intervals(start_to_ends.begin(), start_to_ends.end());
    std::priority_queue<int, std::vector<int>, std::greater<>> active_ends;

    for (size_t idx = 0; idx < intervals.size(); ++idx) {
        auto [current_left, right_list] = intervals[idx];
        for (int r : right_list) {
            active_ends.push(r);
        }
        int next_left = (idx + 1 == intervals.size()) ? pos_limit : intervals[idx + 1].first;
        for (int pos = current_left; pos < next_left; ++pos) {
            while (!active_ends.empty() && active_ends.top() <= pos) {
                active_ends.pop();
            }
            if (active_ends.empty()) break;
            --result;
            active_ends.pop();
        }
    }
    std::cout << result << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int test_cases;
    std::cin >> test_cases;
    while (test_cases--) {
        process_case();
    }
    return 0;
}

Min-Max Tree

This problem requires partitioning a tree into dirceted chains, where each chain has a defined maximum and minimum value. A dynamic programming approach on trees is used.

Define dp[node][state] for a node node:

• state = 0: node acts as an internal point in a chain.
• state = 1: node serves as the maximum value, with the chain direction propagating upwards.
• state = 2: node serves as the minimum value, with the chain direction propagating downwards.

Let total be the sum of dp[child][0] over all children. Compute:

• upward_gain = max(total, max over children (total - dp[child][0] + dp[child][2] + value[child] - value[node]))
• downward_gain = max(total, max over children (total - dp[child][0] + dp[child][1] + value[node] - value[child]))

Then:

• dp[node][0] = upward_gain + downward_gain - total
• dp[node][1] = downward_gain
• dp[node][2] = upward_gain

The answer is dp[root][0].

#include <iostream>
#include <vector>
#include <array>
using ll = long long;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int node_count;
    std::cin >> node_count;
    std::vector<int> node_value(node_count + 1);
    for (int i = 1; i <= node_count; ++i) {
        std::cin >> node_value[i];
    }

    std::vector<std::vector<int>> adjacency(node_count + 1);
    for (int i = 1; i < node_count; ++i) {
        int u, v;
        std::cin >> u >> v;
        adjacency[u].push_back(v);
        adjacency[v].push_back(u);
    }

    std::vector<std::array<ll, 3>> dp(node_count + 1, {0,0,0});
    auto compute_dp = [&](auto&& self, int current, int parent) -> void {
        ll child_sum = 0;
        for (int neighbor : adjacency[current]) {
            if (neighbor == parent) continue;
            self(self, neighbor, current);
            child_sum += dp[neighbor][0];
        }

        ll up_val = child_sum, down_val = child_sum;
        for (int neighbor : adjacency[current]) {
            if (neighbor == parent) continue;
            up_val = std::max(up_val, child_sum - dp[neighbor][0] + dp[neighbor][2] + node_value[neighbor] - node_value[current]);
            down_val = std::max(down_val, child_sum - dp[neighbor][0] + dp[neighbor][1] + node_value[current] - node_value[neighbor]);
        }
        dp[current][0] = up_val + down_val - child_sum;
        dp[current][1] = down_val;
        dp[current][2] = up_val;
    };

    compute_dp(compute_dp, 1, 0);
    std::cout << dp[1][0] << '\n';
    return 0;
}