CF472D: Reconstructing a Tree from Pairwise Distances

A key observation is that the vertex closest to node 1 must be its direct child. This serves as the foundation for a recursive reconstruction strategy.

Define a function check_subtree(v, parent) that attempts to build the subtree rooted at v. The logic relies on identifying the children of v. To determine if a candidate vertex y belongs to the subtree of v (where v != 1), we examine the relationship between distances involving v, its parent p, and y:

• If y is inside the subtree of v, the distance equality holds: dist[p][y] - dist[v][y] == dist[p][v].
• If y is outside, the result is dist[p][y] - dist[v][y] == -dist[p][v].

We iteratively pick the unvisited node closest to v that satisfies the "inside" condition to be a child and recurse.

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

const int MAXN = 2005;
int nodes, dist[MAXN][MAXN];
int parent[MAXN];
bool visited[MAXN];

bool explore(int curr, int prev) {
    visited[curr] = true;
    while (true) {
        int nearest = INT_MAX, choice = 0;
        for (int k = 1; k <= nodes; ++k) {
            // Verify distance consistency
            if (abs(dist[prev][k] - dist[curr][k]) != dist[prev][curr]) return true;
            
            // Check if k is a child of curr
            if (!visited[k] && dist[prev][k] - dist[curr][k] == dist[prev][curr]) {
                if (dist[curr][k] < nearest) {
                    nearest = dist[curr][k];
                    choice = k;
                }
            }
        }
        if (!choice) break;
        parent[choice] = curr;
        if (explore(choice, curr)) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> nodes;
    for (int i = 1; i <= nodes; ++i) {
        for (int j = 1; j <= nodes; ++j) {
            cin >> dist[i][j];
            // Validate matrix properties
            if (i == j && dist[i][j] != 0) { cout << "NO"; return 0; }
            if (i != j && dist[i][j] == 0) { cout << "NO"; return 0; }
            if (i > j && dist[i][j] != dist[j][i]) { cout << "NO"; return 0; }
        }
    }

    visited[1] = true;
    int attempts = 0;
    while (true) {
        attempts++;
        int best_dist = INT_MAX, target = 0;
        for (int i = 1; i <= nodes; ++i) {
            if (!visited[i] && dist[1][i] < best_dist) {
                best_dist = dist[1][i];
                target = i;
            }
        }
        if (!target) break;
        parent[target] = 1;
        if (explore(target, 1)) { cout << "NO"; return 0; }
        if (attempts > nodes + 5) { cout << "NO"; return 0; }
    }
    cout << "YES";
    return 0;
}

CF500E: Counting Uncovered Units in Interval Sequence

Given a sequence of intervals defined by a starting point p[i] and length l[i], the goal is to find the total uncovered length between the start of interval l and the end of interval r.

We model this using a "domino effect":

1. limit[i]: The furthest coordinate reachable if interval i falls.
2. next_idx[i]: The index of the first interval to the right of i that remains standing after i falls.
3. gap[i]: The uncovered distance between limit[i] and the start of next_idx[i].

We build these arrays from right to left. Then, we apply binary lifting (doubling) to answer queries efficiently. jump[k][i] represents the interval we reach after $2^k$ steps of falling, and holes[k][i] stores the accumulated uncovered length over those steps.

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

const int MAXN = 200005;
const int LOG = 20;
int n, q, start[MAXN], len[MAXN];
int limit[MAXN], next_idx[MAXN];
int jump[MAXN][LOG], holes[MAXN][LOG];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> start[i] >> len[i];
    }

    start[n + 1] = INT_MAX;
    next_idx[n] = n + 1;
    limit[n] = start[n] + len[n];

    for (int i = n - 1; i >= 1; --i) {
        next_idx[i] = i + 1;
        limit[i] = start[i] + len[i];
        while (start[i] + len[i] >= start[next_idx[i]]) {
            limit[i] = max(limit[i], limit[next_idx[i]]);
            next_idx[i] = next_idx[next_idx[i]];
        }
    }

    for (int i = n; i >= 1; --i) {
        if (next_idx[i] <= n) {
            holes[i][0] = start[next_idx[i]] - limit[i];
        }
        jump[i][0] = next_idx[i];
    }
    jump[n + 1][0] = n + 1;

    for (int p = 1; p < LOG; ++p) {
        for (int i = n; i >= 1; --i) {
            jump[i][p] = jump[jump[i][p - 1]][p - 1];
            holes[i][p] = holes[i][p - 1] + holes[jump[i][p - 1]][p - 1];
        }
        jump[n + 1][p] = n + 1;
    }

    cin >> q;
    while (q--) {
        int left, right;
        cin >> left >> right;
        int total_gap = 0;
        int curr = left;
        for (int p = LOG - 1; p >= 0; --p) {
            if (jump[curr][p] <= right) {
                total_gap += holes[curr][p];
                curr = jump[curr][p];
            }
        }
        cout << total_gap << "\n";
    }
    return 0;
}

CF241E: Assigning Weights Under Difference Constraints

The problem requires assigning edge weights of either 1 or 2 such that certain distance constraints are met (specifically, $dis_v \le dis_u + 2$ and $dis_u e dis_v$). This is a classic Difference Constraints system.

We first identify the relevant path from node 1 to node n using DFS. Only edges on paths that can lead to n are critical for the constraints. For these edges $(u, v)$, we add:

• $dist[v] \le dist[u] + 2$ (weight limit)
• $dist[u] e dist[v]$, which can be handled by $dist[v] e dist[u]$, typically enforced by $dist[u] + 1 e dist[v]$ or checking strictly.

We use Bellman-Ford to find a feasible set of distances. If a negative cycle exists (or constraints violated), the answer is "No". Otherwise, the weight of an edge $(u, v)$ is $dist[v] - dist[u]$. If a edge is not on a valid path, assign weight 2.

#include <bits/stdc++.h>
#define nl "\n"
using namespace std;

const int INF = 1e9;
const int MAXV = 1e5; // Adjusted for typical constraints
int n, m;
vector<int> adj[MAXV];
int src[MAXV], dst[MAXV];
bool reachable[MAXV];
int dist[MAXV];

struct Constraint {
    int u, v, w;
};
vector<Constraint> edges;

void find_reachable(int u) {
    reachable[u] = true;
    if (u == n) return;
    for (int v : adj[u]) {
        if (!reachable[v]) find_reachable(v);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> src[i] >> dst[i];
        adj[src[i]].push_back(dst[i]);
    }

    find_reachable(1);

    // Build constraints for edges on valid paths
    for (int i = 0; i < m; ++i) {
        if (reachable[src[i]] && reachable[dst[i]]) {
            // v <= u + 2
            edges.push_back({src[i], dst[i], 2});
            // u + 1 <= v  (to ensure v > u, effectively v - u >= 1)
            edges.push_back({dst[i], src[i], -1}); 
        }
    }

    fill(dist, dist + n + 1, INF);
    dist[1] = 0;

    // Bellman-Ford
    for (int i = 0; i < n; ++i) {
        bool updated = false;
        for (auto& e : edges) {
            if (dist[e.u] < INF && dist[e.v] > dist[e.u] + e.w) {
                dist[e.v] = dist[e.u] + e.w;
                updated = true;
            }
        }
        if (!updated) break;
    }

    // Check for negative cycles / violations
    for (auto& e : edges) {
        if (dist[e.u] < INF && dist[e.v] > dist[e.u] + e.w) {
            cout << "No" << nl;
            return 0;
        }
    }

    cout << "Yes" << nl;
    for (int i = 0; i < m; ++i) {
        if (reachable[src[i]] && reachable[dst[i]]) {
            cout << dist[dst[i]] - dist[src[i]] << nl;
        } else {
            cout << 2 << nl;
        }
    }
    return 0;
}

CF41D

This problem involves modular arithmetic and dynamic programming. Given the complexity often associated with randomized or brute-force checks in such problems, a common strategy is to iterate over possible values (e.g., 1 to 24) for specific parameters or use DP states involving position and current remainder. Detailed implementation is omitted here due to the abstract nature of the prompt.