Interval Game Theory via Dynamic Programming

Two participants alternately extract characters from either end of a string. Assuming optimal play from both sides, the objective is to predict the final match outcome. The input guarantees an even-length string, with cumulative lengths capped at 2000 across all test cases.

The problem resolves efficiently through interval dynamic programming. We define state[l][r] as the resulting outcome for the substring spanning indices l through r. Since each turn reduces the remaining segment by exactly two characters, only even-length intervals require evaluation. Base cases occur when the substring length equals two; a draw is recorded if characters match, otherwise the first player secures an immediate advantage.

For broader intervals, the current player evaluates both boundary choices. The transition logic compares adjacent values to anticipate the opponent's counteromve, propagating win/loss states backward through the recursion tree. A ternary encoding system tracks outcomes, allowing constant-time state retrieval during evaluation.

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

constexpr int DRAW = 1, FIRST_WIN = 0, SECOND_WIN = 2;
int memo[2005][2005];

void evaluate_match() {
    string seq; cin >> seq;
    int len = seq.size();
    memset(memo, -1, sizeof(memo));

    auto resolve = [&](auto&& self, int left, int right) -> int {
        if (left >= right) return DRAW;
        if (memo[left][right] != -1) return memo[left][right];
        
        int result = DRAW;
        if (left + 1 == right) {
            return memo[left][right] = (seq[left] == seq[right]) ? DRAW : FIRST_WIN;
        }

        int outcome_left = self(self, left + 1, right);
        int outcome_right = self(self, left, right - 1);

        if (seq[left] != seq[right]) {
            if (seq[left] < seq[right]) {
                result = (seq[left + 1] <= seq[left]) ? outcome_left : FIRST_WIN;
            } else {
                result = (seq[right - 1] <= seq[right]) ? outcome_right : FIRST_WIN;
            }
        } else {
            if (seq[left + 1] == seq[left] && seq[right - 1] == seq[right])
                result = max({outcome_left, outcome_right, self(self, left + 1, right - 1)});
            else if (seq[left + 1] == seq[left]) result = outcome_left;
            else if (seq[right - 1] == seq[right]) result = outcome_right;
            else result = self(self, left + 1, right - 1);
        }
        return memo[left][right] = result;
    };

    int final_outcome = resolve(resolve, 0, len - 1);
    const char* outcomes[] = {"Alice", "Draw", "Bob"};
    cout << outcomes[final_outcome] << '\n';
}

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

Bitmask State-Space Routing with Temporal Constraints

Given a weighted undirected graph and two initial deployment points, agents must intercept k dynamic targets. Each target p materializes at vertex x during specific timestamps. Interception succeeds only if an agent occupies the exact location at the precise moment of appearance. The goal minimizes the total elapsed time required to capture every target, or reports impossibility. System limits include n <= 10^4, k <= 8, and timestamps up to 10^8.

This scenario maps to shortest-path computation on an expanded state space. Define dp[mask][u] as the minimal arrival time at vertex u after successfully securing the target subset encoded by mask. Transitions bifurcate into movement (standard graph relaxation) and interception (temporal jumps to valid occurrence times).

The algorithm iterates through all bitmask states. For each configuration, a priority-driven Dijkstra routine propagates minimal travel times across the network. Following path relaxation, the system scans uncovered targets. Using binary search on pre-sorted event timelines, it calculates the earliest feasible interception moment and updates subsequent states. The final answer emerges by partitioning the complete target set between the two starting agents and minimizing their maximum completion time.

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

const int INF = 1e9 + 7;
const int MAX_N = 10005;
const int MAX_K = 8;

struct GraphEdge { int dest, cost; };
vector<GraphEdge> graph[MAX_N];
vector<int> timeline[MAX_K][MAX_N];
int arrival[MAX_N];
int dp[1 << MAX_K][MAX_N];
int global_min[1 << MAX_K];

void propagate_distances(int n) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int u = 1; u <= n; ++u)
        if (arrival[u] < INF) pq.emplace(arrival[u], u);

    while (!pq.empty()) {
        auto [dist, u] = pq.top(); pq.pop();
        if (dist > arrival[u]) continue;
        for (auto& e : graph[u])
            if (arrival[e.dest] > dist + e.cost) {
                arrival[e.dest] = dist + e.cost;
                pq.emplace(arrival[e.dest], e.dest);
            }
    }
}

void compute_agent_plan(int start_node, int n, int k) {
    int limit = 1 << k;
    for (int m = 0; m < limit; ++m)
        fill(dp[m], dp[m] + n + 1, INF);
    dp[0][start_node] = 0;

    for (int m = 0; m < limit; ++m) {
        memcpy(arrival, dp[m], sizeof(dp[m]));
        propagate_distances(n);
        for (int u = 1; u <= n; ++u) dp[m][u] = min(dp[m][u], arrival[u]);

        for (int u = 1; u <= n; ++u) {
            int cur_time = dp[m][u];
            if (cur_time == INF) continue;
            for (int t = 0; t < k; ++t) {
                if (!(m & (1 << t))) {
                    auto& events = timeline[t][u];
                    auto it = lower_bound(events.begin(), events.end(), cur_time);
                    if (it != events.end()) {
                        int next_m = m | (1 << t);
                        dp[next_m][u] = min(dp[next_m][u], *it);
                    }
                }
            }
        }
    }
}

void solve() {
    int n, m, k, q;
    if (!(cin >> n >> m >> k)) return;
    int limit = 1 << k;

    for (int i = 1; i <= n; ++i) {
        graph[i].clear();
        for (int j = 0; j < k; ++j) timeline[j][i].clear();
    }

    for (int i = 0; i < m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    cin >> q;
    while (q--) {
        int p, x, t; cin >> p >> x >> t;
        timeline[p - 1][x].push_back(t);
    }

    for (int j = 0; j < k; ++j)
        for (int i = 1; i <= n; ++i) {
            timeline[j][i].push_back(INF);
            sort(timeline[j][i].begin(), timeline[j][i].end());
        }

    int start1, start2; cin >> start1 >> start2;
    compute_agent_plan(start1, n, k);
    for (int s = 0; s < limit; ++s) {
        global_min[s] = INF;
        for (int i = 1; i <= n; ++i) global_min[s] = min(global_min[s], dp[s][i]);
    }

    compute_agent_plan(start2, n, k);

    int answer = INF;
    for (int s = 0; s < limit; ++s) {
        int t1 = global_min[s];
        int t2 = INF;
        int complement = limit - 1 - s;
        for (int i = 1; i <= n; ++i) t2 = min(t2, dp[complement][i]);
        answer = min(answer, max(t1, t2));
    }

    cout << (answer >= INF ? -1 : answer) << '\n';
}

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

Monotonic Range Assignment via Lazy Propagation

Given a sequence containing integers from 1 to m, compute the minimal contiguous subarray length that fully encompasses all values from 1 to i for every i in [1, m]. Both the sequence length n and value range m scale up to 5*10^5.

Define right_bound[l] as the smallest index r such that the segment a[l..r] contains all required values up to the current iteration. As i advances, right_bound[l] exhibits strict monotonicity across left endpoints. When a new value v appears at positions pos_1, pos_2, ..., the array undergoes interval lifts. Specifically, gaps between consecutive occurrences of v trigger assignments where right_bound is elevated to the current index.

A segment tree maintains the expression right_bound[l] - l + 1. Each node stores the range minimum and supports lazy propagation for bulk assignments. The lazy parameter directly updates the minimum expression using the formula lazy_val - node_right_bound + 1. After processing all instances of the current value, the root node's minimum yields the optimal window length for i.

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

const int INF = 0x3f3f3f3f;
const int MAX_N = 500010;

struct SegmentTree {
    struct Node {
        int l, r, min_right, min_len, lazy;
        bool has_lazy;
    } tree[MAX_N << 2];

    void build(int p, int l, int r) {
        tree[p].l = l; tree[p].r = r;
        tree[p].min_right = INF; tree[p].min_len = INF;
        tree[p].lazy = 0; tree[p].has_lazy = false;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
    }

    void apply(int p, int val) {
        tree[p].min_right = val;
        tree[p].min_len = val - tree[p].r + 1;
        tree[p].lazy = val;
        tree[p].has_lazy = true;
    }

    void push(int p) {
        if (tree[p].has_lazy) {
            apply(p << 1, tree[p].lazy);
            apply(p << 1 | 1, tree[p].lazy);
            tree[p].has_lazy = false;
            tree[p].lazy = 0;
        }
    }

    void pull(int p) {
        tree[p].min_right = min(tree[p << 1].min_right, tree[p << 1 | 1].min_right);
        tree[p].min_len = min(tree[p << 1].min_len, tree[p << 1 | 1].min_len);
    }

    void update(int p, int ql, int qr, int val) {
        if (ql <= tree[p].l && tree[p].r <= qr) {
            apply(p, val);
            return;
        }
        push(p);
        int mid = (tree[p].l + tree[p].r) >> 1;
        if (ql <= mid) update(p << 1, ql, qr, val);
        if (qr > mid) update(p << 1 | 1, ql, qr, val);
        pull(p);
    }

    int find_first_less(int p, int ql, int qr, int threshold) {
        if (tree[p].l > qr || tree[p].r < ql || tree[p].min_right >= threshold) return -1;
        if (tree[p].l == tree[p].r) return tree[p].l;
        push(p);
        int res = find_first_less(p << 1 | 1, ql, qr, threshold);
        return (res != -1) ? res : find_first_less(p << 1, ql, qr, threshold);
    }
} seg;

vector<int> positions[MAX_N];

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int val; cin >> val;
        positions[val].push_back(i);
    }

    seg.build(1, 1, n);

    for (int i = 1; i <= m; ++i) {
        int prev = 0;
        for (int pos : positions[i]) {
            int idx = seg.find_first_less(1, prev + 1, pos, pos);
            if (idx != -1) seg.update(1, prev + 1, idx, pos);
            prev = pos;
        }
        if (positions[i].back() < n) {
            seg.update(1, positions[i].back() + 1, n, INF);
        }
        cout << seg.tree[1].min_len << '\n';
    }
}

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

Exponentially Weighted Range Edges and Graph Decomposition

The final challenge involves directed graphs where edges are defined as range mappings. Each specification (L1, R1, L2, R2, a, b) creates edges from every node u in [L1, R1] to every node v in [L2, R2] with weight a * 2^b. Direct graph construction and standard shortest-path algorithms fail due to the quadratic edge count and astronomical weight magnitudes.

The optimal approach combines vertex decomposition with persistent segment tree optimization. By mapping node intervals to segment tree leaves, range-to-range connections compress into O(log n) links between internal nodes. Large weights are managed by storing distances as structured pairs (bit_length, residual_mod), enabling precise magnitude comparisons without full numeric expansion. Modular arithmetic applies strictly to the final output, while internal traversal logic relies on exact exponential ordering. This methodology reduces effective edge complexity from O(n^2) to O(m log n), aligning with advanced constrained graph traversal techniques.