Given an integer, determine if it is a palindrome.

The straightforward apprroach is to treat the input as a string and check if it reads the same forwards and backwards, which can be done in O(n) time where n is the length of the string.

A more efficient approach uses polynomial hashing with O(n) time complexity. We'll implement both forward and backward hash functions to verify if the string is a palindrome.

#include <iostream>
#include <string>
#include <array>
#include <cassert>

typedef long long ll;
const int MAXN = 200005;
const int HASH_COUNT = 2;
const int BASES[HASH_COUNT] = {1234, 5678};
const int MODS[HASH_COUNT] = {1000000123, 1000000403};

ll power[HASH_COUNT][MAXN];
ll inv_power[HASH_COUNT][MAXN];
ll forward_hash[HASH_COUNT][MAXN];
ll backward_hash[HASH_COUNT][MAXN];

ll fast_pow(ll base, ll exp, int mod) {
    ll result = 1;
    while (exp > 0) {
        if (exp & 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

void initialize_hashes() {
    for (int h = 0; h < HASH_COUNT; h++) {
        power[h][0] = 1;
        for (int i = 1; i < MAXN; i++) {
            power[h][i] = (power[h][i - 1] * BASES[h]) % MODS[h];
        }
        inv_power[h][MAXN - 1] = fast_pow(power[h][MAXN - 1], MODS[h] - 2, MODS[h]);
        for (int i = MAXN - 1; i > 0; --i) {
            inv_power[h][i - 1] = (inv_power[h][i] * BASES[h]) % MODS[h];
        }
        assert(inv_power[h][0] == 1);
    }
}

void build_hashes(std::string s) { // s[0] == ' '
    int length = s.size();
    for (int h = 0; h < HASH_COUNT; h++) {
        for (int i = 1; i <= length; i++) {
            forward_hash[h][i] = (forward_hash[h][i - 1] * BASES[h] % MODS[h] + s[i]) % MODS[h];
            backward_hash[h][i] = (backward_hash[h][i - 1] + s[i] * power[h][i - 1] % MODS[h]) % MODS[h];
        }
    }
}

std::array<int> get_forward_hash(int l, int r) {
    assert(l <= r);
    std::array<int> result;
    for (int h = 0; h < HASH_COUNT; h++) {
        result[h] = (forward_hash[h][r] - forward_hash[h][l - 1] * power[h][r - l + 1] % MODS[h] + MODS[h]) % MODS[h];
    }
    return result;
}

std::array<int> get_backward_hash(int l, int r) {
    assert(l <= r);
    std::array<int> result;
    for (int h = 0; h < HASH_COUNT; h++) {
        result[h] = (backward_hash[h][r] - backward_hash[h][l - 1] + MODS[h]) % MODS[h] * inv_power[h][l - 1] % MODS[h];
    }
    return result;
}

void solve_palindrome() {
    initialize_hashes();
    std::string input;
    std::cin >> input;
    int n = input.size();
    input = " " + input; // 1-based indexing
    build_hashes(input);
    
    bool is_palindrome = true;
    for (int h = 0; h < HASH_COUNT; h++) {
        if (get_forward_hash(1, n) != get_backward_hash(1, n)) {
            is_palindrome = false;
            break;
        }
    }
    std::cout << (is_palindrome ? "Yes" : "No") << "\n";
}
</int></int></int></int></cassert></array></string></iostream>

Problem B: Interval Overlap Calculation

Given two intervals [A, B] and [C, D], calculate the size of their intersection.

The key insight is that the intersection of multiple intervals can be found by taking the maximum of all left endpoints and the minimum of all right endpoints. The intersection is then [max_left, min_right], and its length is max(0, min_right - max_left).

This approach has O(n) time complexity for n intervals.

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

void solve_interval_intersection() {
    int num_intervals = 2;
    std::vector<int> left_bounds(num_intervals + 1);
    std::vector<int> right_bounds(num_intervals + 1);
    
    int max_left = -2e9;
    int min_right = 2e9;
    
    for (int i = 1; i <= num_intervals; i++) {
        std::cin >> left_bounds[i] >> right_bounds[i];
        max_left = std::max(max_left, left_bounds[i]);
        min_right = std::min(min_right, right_bounds[i]);
    }
    
    int intersection_length = std::max(0, min_right - max_left);
    std::cout << intersection_length << "\n";
}
</int></int></algorithm></vector></iostream>

Problem C: Synchronized Clocks

There are N clocks, where the i-th clock completes a full cycle in T_i seconds. All clocks start at the zero position simultaneous. Determine the next time when all clocks will be at the zero position again.

The solution involves finding the least common multiple (LCM) of all the periods T_i. This is because the clocks will align at zero at the smallest time that is a multiple of all individual periods.

We can compute the LCM iteratively using the formula LCM(a,b) = (a*b)/GCD(a,b).

#include <iostream>
#include <vector>

typedef long long ll;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

void solve_clock_sync() {
    int N;
    std::cin >> N;
    
    ll current_lcm = 1;
    for (int i = 1; i <= N; i++) {
        ll period;
        std::cin >> period;
        current_lcm = lcm(current_lcm, period);
    }
    
    std::cout << current_lcm << "\n";
}
</vector></iostream>

Problem D: Tree Path Queries with Fixed Node

Given a weighted tree with N nodes and Q queries, each query asks for the shortest path from node x_i to node y_i that must pass through a specific node K.

The key observation is that the shortest path from x_i to y_i passing through K is simply the path from x_i to K followed by the path from K to y_i.

To efficient answer multiple queries, we can preprocess the tree by performing a depth-first search (DFS) from node K to compute distances from K to all other nodes. Then each query can be answered in O(1) time by adding the distances from x_i to K and from K to y_i.

For the general case where each query might have a different K, we can use binary lifting to preprocess the tree for efficient LCA (Lowest Common Ancestor) queries, allowing us to compute path lengths in O(log N) time per query.

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

typedef long long ll;

const int MAX_N = 100005;
const int LOG = 20;

std::vector<:pair ll="">> adj[MAX_N];
int depth[MAX_N];
ll dist_from_root[MAX_N];
int parent[LOG][MAX_N];
ll dist_table[LOG][MAX_N];

void dfs(int u, int p, ll current_dist) {
    depth[u] = depth[p] + 1;
    parent[0][u] = p;
    dist_from_root[u] = current_dist;
    
    for (auto vw : adj[u]) {
        int v = vw.first;
        ll w = vw.second;
        if (v == p) continue;
        dfs(v, u, current_dist + w);
    }
}

void preprocess_lca(int n) {
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= n; i++) {
            parent[j][i] = parent[j-1][parent[j-1][i]];
            dist_table[j][i] = dist_table[j-1][i] + dist_table[j-1][parent[j-1][i]];
        }
    }
}

ll query_path_length(int u, int v) {
    ll total_distance = 0;
    
    if (depth[u] < depth[v]) {
        std::swap(u, v);
    }
    
    int depth_diff = depth[u] - depth[v];
    for (int j = LOG-1; j >= 0; j--) {
        if (depth_diff & (1 << j)) {
            total_distance += dist_table[j][u];
            u = parent[j][u];
        }
    }
    
    if (u == v) {
        return total_distance;
    }
    
    for (int j = LOG-1; j >= 0; j--) {
        if (parent[j][u] != parent[j][v]) {
            total_distance += dist_table[j][u] + dist_table[j][v];
            u = parent[j][u];
            v = parent[j][v];
        }
    }
    
    return total_distance + dist_table[0][u] + dist_table[0][v];
}

void solve_tree_queries() {
    int n;
    std::cin >> n;
    
    for (int i = 1; i < n; i++) {
        int u, v;
        ll w;
        std::cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    // Root the tree at node 1
    depth[0] = 0;
    dist_from_root[0] = 0;
    dfs(1, 0, 0);
    
    // Initialize dist_table for the first level
    for (int i = 1; i <= n; i++) {
        dist_table[0][i] = dist_from_root[i] - dist_from_root[parent[0][i]];
    }
    
    preprocess_lca(n);
    
    int Q;
    std::cin >> Q;
    
    while (Q--) {
        int x, y;
        std::cin >> x >> y;
        std::cout << query_path_length(x, y) << "\n";
    }
}
</:pair></functional></vector></iostream>