Problem A: Interval Completion Timing

The task involves determining the exact timestamp when a cumulative workload finishes with in a timeline defined by alternating active and inactive periods. First, compute the total required duration. If no intervals are provided or the total duration exceeds the final boundary, the task is impossible. Otherwise, flatten all interval boundaries into a sorted sequence. Locate the first boundary that meets or exceeds the total duration. If the boundary corresponds to the end of an active window (odd index in a 0-based flattened array), the completion timee equals the total duration. If it corresponds to the start of a window (even index), the completion time is pushed to that boundary, as the workload falls within a rest period.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

void process_case() {
    int n;
    if (!(cin >> n)) return;
    
    long long total_duration = 0;
    for (int i = 0; i < n; ++i) {
        long long work_segment;
        cin >> work_segment;
        total_duration += work_segment;
    }
    
    int m;
    cin >> m;
    if (m == 0) {
        cout << -1 << '\n';
        return;
    }
    
    vector<long long> boundaries;
    boundaries.reserve(m * 2);
    for (int i = 0; i < m; ++i) {
        long long start, finish;
        cin >> start >> finish;
        boundaries.push_back(start);
        boundaries.push_back(finish);
    }
    
    if (total_duration > boundaries.back()) {
        cout << -1 << '\n';
        return;
    }
    
    auto it = lower_bound(boundaries.begin(), boundaries.end(), total_duration);
    int idx = distance(boundaries.begin(), it);
    
    if (idx % 2 != 0) {
        cout << total_duration << '\n';
    } else {
        cout << *it << '\n';
    }
}

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

Problem B: Maximum Gap in Power Sum Ranges

This problem requires finding the largest continuous subsegment within a given range that does not contain any integer representable as a sum of powers of two given bases. The approach involves generating all valid combinations of the form x^a + y^b that fall within the target interval. Careful overflow checking is applied during exponentiation. The generated values are sorted and deduplicated. Finally, iterate through the sorted values to compute the maximum distance between adjacent restricted numbers, including the gaps from the range start to the first value and from the last value to the range end.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve_power_gap() {
    long long base_x, base_y, range_l, range_r;
    cin >> base_x >> base_y >> range_l >> range_r;
    
    vector<long long> restricted;
    for (long long p1 = 1; ; ) {
        if (p1 > range_r) break;
        for (long long p2 = 1; ; ) {
            long long combination = p1 + p2;
            if (combination >= range_l && combination <= range_r) {
                restricted.push_back(combination);
            }
            if (range_r / base_y < p2) break;
            p2 *= base_y;
        }
        if (range_r / base_x < p1) break;
        p1 *= base_x;
    }
    
    sort(restricted.begin(), restricted.end());
    restricted.erase(unique(restricted.begin(), restricted.end()), restricted.end());
    
    long long max_gap = 0;
    long long prev_boundary = range_l - 1;
    
    for (long long val : restricted) {
        max_gap = max(max_gap, val - prev_boundary - 1);
        prev_boundary = val;
    }
    max_gap = max(max_gap, range_r - prev_boundary);
    
    cout << max_gap << '\n';
}

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

Problem C: Tree Evasion Simulation

The goal is to maximize the time a fleeing agent can avoid capture on a tree structure. The strategy involves identifying the path between the two agents and simulating their movement towards each other. First, perform a depth-first traversal to record each node's depth, parent pointer, and the maximum reachable depth within its subtree. Reconstruct the unique path from the starting position up to the root. Iterate through simultaneous steps where both agents move closer along this path. At each step, calculate the potential evasion distance by combining the current separation, the steps already taken, and the longest available branch from the fleeing agent's current position. The maximum value across all steps, multiplied by two to account for turn-based movement, yields the optimal evasion time.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

void solve_tree_evasion() {
    int node_count, start_position;
    cin >> node_count >> start_position;
    
    vector<vector<int>> adj(node_count + 1);
    for (int i = 0; i < node_count - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    vector<int> parent_ptr(node_count + 1, 0);
    vector<int> node_depth(node_count + 1, 0);
    vector<int> max_sub_depth(node_count + 1, 0);
    
    function<void(int, int, int)> compute_tree = [&](int u, int p, int d) {
        parent_ptr[u] = p;
        node_depth[u] = d;
        int local_max = 0;
        for (int v : adj[u]) {
            if (v != p) {
                compute_tree(v, u, d + 1);
                local_max = max(local_max, max_sub_depth[v]);
            }
        }
        max_sub_depth[u] = local_max + 1;
    };
    compute_tree(1, -1, 0);
    
    vector<int> chase_path;
    for (int curr = start_position; curr != -1; curr = parent_ptr[curr]) {
        chase_path.push_back(curr);
    }
    
    int max_evasion = 0;
    int path_len = chase_path.size();
    
    for (int step_b = 0, step_a = path_len - 1; step_b < step_a; ++step_b, --step_a) {
        int node_b = chase_path[step_b];
        int node_a = chase_path[step_a];
        int separation = node_depth[node_b] - node_depth[node_a];
        int branch_potential = max_sub_depth[node_b] - 1;
        int total_steps = step_b + separation + branch_potential;
        max_evasion = max(max_evasion, total_steps * 2);
    }
    
    cout << max_evasion << '\n';
}

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