Wireless Network Coverage Optimization

A city grid consists of 129 east-west streets and 129 north-south streets, forming intersections at integer coordinates (x, y) where 0 ≤ x, y ≤ 128. Some intersections host public venues, each with a known count of facilities. A single wireless transmitter must be placed such that its coverage area — an axis-aligned square centered at the installation point with side length 2d (including boundaries) — maximizes the total number of covered venues.

The solution enumerates all possible transmitter positions in the grid (129 × 129 candidates), computes for each position how many venue fall within the square [x−d, x+d] × [y−d, y+d], and tracks both the maximum coverage count and the number of positions achieving it.

int d, n;
vector<tuple<int, int, long long>> venues;

int main() {
    ios::sync_with_stdio(false);
    cin >> d >> n;
    venues.resize(n);
    for (auto& [x, y, k] : venues) cin >> x >> y >> k;

    long long best = -1;
    int ways = 0;

    for (int cx = 0; cx <= 128; ++cx) {
        for (int cy = 0; cy <= 128; ++cy) {
            long long total = 0;
            for (const auto& [x, y, k] : venues) {
                if (abs(x - cx) <= d && abs(y - cy) <= d) {
                    total += k;
                }
            }
            if (total > best) {
                best = total;
                ways = 1;
            } else if (total == best) {
                ++ways;
            }
        }
    }

    cout << ways << " " << best << "\n";
}

Constrained Shortest Path in Directed Graphs

Given a directed graph with unit edge weights, find the shortest path from source s to target t, under the constraint that every vertex along the path must only have outgoing edges leading to nodes that are reachable from t (i.e., lie in the reverse-reachable subgraph rooted at t). This ensures no "dead-end" branches divert from the eventual destination.

The algorithm proceeds in two phases:

1. Reverse reachability analysis: Perform BFS/DFS starting from t on the reversed graph to identify all nodes that can reach t. Mark these as valid.
2. Constrained shortest path: Run BFS (or 0-1 BFS, though all weights are 1) from s, but only traverse edges u → v where v is marked valid in step 1.

vector<vector<int>> rev_adj, adj;
vector<bool> valid;
vector<int> dist;

void markReachable(int t) {
    queue<int> q;
    q.push(t);
    valid[t] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : rev_adj[u]) {
            if (!valid[v]) {
                valid[v] = true;
                q.push(v);
            }
        }
    }
}

int bfsFrom(int s, int t) {
    fill(dist.begin(), dist.end(), -1);
    queue<int> q;
    q.push(s);
    dist[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == t) return dist[u];
        for (int v : adj[u]) {
            if (dist[v] == -1 && valid[v]) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return -1;
}

Integer Root Finding for High-Degree Polynomials

Given a polynomial P(x) = a₀ + a₁x + … + aₙxⁿ with potentially huge coefficients (up to 10¹⁰⁰⁰⁰), determine all integer roots in the range [1, m], where m ≤ 10⁶.

Direct evaluation is infeasible due to coefficient magnitude. Instead, the solution applies modular arithmetic with multiple distinct large primes pᵢ. For each prime pᵢ, coefficients are reduced modulo pᵢ, and Horner’s method evaluates P(x) mod pᵢ for all x ∈ [1, m]. A candidate x is retained only if P(x) ≡ 0 (mod pᵢ) for all selected primes — a high-probability guarantee of exact divisibility given sufficient primes and their size.

const vector<int> MODS = {20011, 20021, 20023, 20029, 20047,
                           20051, 20063, 20071, 20089, 20101};

vector<vector<long long>> coeffs_mod(MODS.size(), vector<long long>(105));
vector<vector<bool>> zero_mod(MODS.size());

void parseCoeff(int idx) {
    string s; cin >> s;
    bool neg = (s[0] == '-');
    int start = neg ? 1 : 0;
    for (int i = 0; i < MODS.size(); ++i) {
        long long val = 0;
        for (char c : s.substr(start)) {
            val = (val * 10 + (c - '0')) % MODS[i];
        }
        coeffs_mod[i][idx] = neg ? (MODS[i] - val) % MODS[i] : val;
    }
}

int main() {
    int n, m; cin >> n >> m;
    for (int i = 0; i <= n; ++i) parseCoeff(i);

    for (int i = 0; i < MODS.size(); ++i) {
        zero_mod[i].resize(MODS[i], false);
        for (int x = 0; x < MODS[i]; ++x) {
            long long res = coeffs_mod[i][n];
            for (int j = n - 1; j >= 0; --j) {
                res = (res * x + coeffs_mod[i][j]) % MODS[i];
            }
            if (res == 0) zero_mod[i][x] = true;
        }
    }

    vector<int> roots;
    for (int x = 1; x <= m; ++x) {
        bool candidate = true;
        for (int i = 0; i < MODS.size(); ++i) {
            if (!zero_mod[i][x % MODS[i]]) {
                candidate = false;
                break;
            }
        }
        if (candidate) roots.push_back(x);
    }

    cout << roots.size() << "\n";
    for (int r : roots) cout << r << "\n";
}