USACO 2026 First Contest Silver Division - Mooclear Reactor

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Each constraint is of the form \(a_x + a_y = z\). Think of the \(N\) rods as vertices of a graph, and each constraint as an (undirected) edge \((x,y,z)\). In a connected component, all \(a_i\) are tied together by these equations. Take any node as a “root” and express every \(a_i\) in that component as an affine function of a single parameter \(k\):

$$ a_i = s_i \cdot k + t_i,\quad s_i \in {-1,1},\ t_i \in \mathbb{Z}. $$ We can build this using BFS/DFS. Start with some node \(u\) and set \(s_u = 1\), \(t_u = 0\), so \(a_u = k\). For an edge \((u,v,z)\) we must have $$ a_u + a_v = z \Rightarrow a_v = z - a_u = -s_u k + (z - t_u). $$ So we set \(s_v = -s_u\) and \(t_v = z - t_u\). Doing this consistently over the component assigns a sign and offset to every node.

When we revisit an already visited node \(v\) via another path, we get a consistency condition. From the BFS labels we have \(a_u = s_u k + t_u\) and \(a_v = s_v k + t_v\), but also from the new constraint we need \(a_u + a_v = z\): $$ s_u k + t_u + s_v k + t_v = z \Rightarrow (s_u + s_v)k + (t_u + t_v) = z. $$ If \(s_u + s_v = 0\), the \(k\) term cancels, and we must check \(t_u + t_v = z\); otherwise the system is inconsistent and the answer is \(-1\). If \(s_u + s_v \neq 0\), this equation determines \(k\): $$ k = \frac{z - (t_u + t_v)}{s_u + s_v}. $$ This \(k\) must be an integer; if it isn’t, or if a different cycle forces a different \(k\), the component is impossible. In the code, this is handled by a flag fixed and a fixed_k for each component.

Once a component is consistent, we consider two cases:

1. \(k\) fixed in this component (by some cycle): then every \(a_i\) is fully determined: \(a_i = s_i \cdot k + t_i\). We just count how many \(i\) satisfy \(L_i \le a_i \le R_i\) and add that to the global answer.

2. \(k\) is free in this component (no cycle pinned it): each rod \(i\) contributes a condition on \(k\): $$ L_i \le s_i k + t_i \le R_i. $$ If \(s_i = 1\), this becomes \(L_i - t_i \le k \le R_i - t_i\). If \(s_i = -1\), it becomes \(t_i - R_i \le k \le t_i - L_i\). So each rod gives an integer interval \([low_i,, high_i]\) of valid \(k\) where it is active. For a given \(k\), the number of active rods is the number of intervals containing \(k\). We want the maximum possible value of this over all integer \(k\). This is a classic “maximum overlap of intervals” problem: we do a sweep-line by turning each interval into events \((low_i, +1)\) and \((high_i+1, -1)\), sort them, and keep a running sum to find the maximum overlap best in that component.

Finally, we sum over all components: if any component is impossible, print \(-1\); otherwise, for each component with fixed \(k\) add its fixed-count, and for each with free \(k\) add its best overlap. This runs in \(O(N+M)\) per test (plus sorting all events, still \(O((N+M)\log(N+M))\) overall), and respects all constraints.

Source code

The source code for the solution in C++ can be seen below.

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

using namespace std;

using ll = long long;

const int MAXN = 200005;

ll L[MAXN], R[MAXN];
int sign_var[MAXN];
ll offset_var[MAXN];
bool visited[MAXN];
vector<pair<int, ll>> adj[MAXN];

void solve() {
    int N, M;
    cin >> N >> M;

    for (int i = 1; i <= N; ++i) {
        cin >> L[i];
    }
    for (int i = 1; i <= N; ++i) {
        cin >> R[i];
    }

    // reset graph + visited for current test
    for (int i = 1; i <= N; ++i) {
        adj[i].clear();
        visited[i] = false;
    }

    // read edges
    for (int i = 0; i < M; ++i) {
        int x, v;
        ll z;
        cin >> x >> v >> z;
        adj[x].push_back({v, z});
        adj[v].push_back({x, z});
    }

    ll total_max_rods = 0;
    bool global_impossible = false;

    for (int start = 1; start <= N; ++start) {
        if (visited[start]) 
            continue;

        vector<int> component;
        bool fixed = false;
        ll fixed_k = 0;
        bool local_possible = true;

        queue<int> q;
        q.push(start);
        visited[start] = true;
        sign_var[start] = 1;
        offset_var[start] = 0;

        // BFS over this connected component
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            component.push_back(u);

            for (auto &edge : adj[u]) {
                int v = edge.first;
                ll z = edge.second;

                int next_sign = -sign_var[u];
                ll next_offset = z - offset_var[u];

                if (!visited[v]) {
                    visited[v] = true;
                    sign_var[v] = next_sign;
                    offset_var[v] = next_offset;
                    q.push(v);
                } 
                else {
                    int sum_sign = sign_var[u] + sign_var[v];
                    ll sum_offset = offset_var[u] + offset_var[v];

                    if (sum_sign == 0) {
                        // k cancels out; check consistency
                        if (sum_offset != z) {
                            local_possible = false;
                        }
                    } 
                    else {
                        // solve for k
                        ll num = z - sum_offset;
                        if (num % sum_sign != 0) {
                            local_possible = false;
                        } 
                        else {
                            ll k = num / sum_sign;
                            if (fixed && fixed_k != k) {
                                local_possible = false;
                            }
                            fixed = true;
                            fixed_k = k;
                        }
                    }
                }
            }
        }

        if (!local_possible) {
            global_impossible = true;
            break;
        }

        if (fixed) {
            // k is fixed; just count valid rods
            ll count = 0;
            for (int u : component) {
                ll val = (ll)sign_var[u] * fixed_k + offset_var[u];
                if (val >= L[u] && val <= R[u]) {
                    count++;
                }
            }
            total_max_rods += count;
        } 
        else {
            // k is free; find k that maximizes number of valid rods
            vector<pair<ll, int>> events;

            for (int u : component) {
                ll low, high;
                if (sign_var[u] == 1) {
                    low = L[u] - offset_var[u];
                    high = R[u] - offset_var[u];
                } 
                else {
                    low = offset_var[u] - R[u];
                    high = offset_var[u] - L[u];
                }

                if (low <= high) {
                    events.push_back({low, 1});
                    events.push_back({high + 1, -1});
                }
            }

            sort(events.begin(), events.end());

            int best = 0;
            int current = 0;
            for (size_t j = 0; j < events.size(); ++j) {
                current += events[j].second;
                if (j + 1 == events.size() || events[j].first != events[j + 1].first) {
                    best = max(best, current);
                }
            }

            total_max_rods += best;
        }
    }

    if (global_impossible) {
        cout << -1 << "\n";
    } 
    else {
        cout << total_max_rods << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;

    while (T--) {
        solve();
    }
    return 0;
}