Circular Position Shift After Exponential Rounds

Given n children (indexed 0 to n-1) seated in a circle, each initially at position equal to their index. Each round, the child at position i moves clockwise to position (i + m) mod n. After 10^k rounds, determine the final position of child x.

Input Format

One line with four integers: n, m, k, x.

Output Format

One integer: the final position of child x.

Constraints

• 1 < n < 1,000,000
• 0 < m < n
• 1 <= x <= n
• 0 < k < 10^9

Solution

After one round, child i moves to (i + m) mod n. After 10^k rounds, the shift per child is (m * (10^k mod n)) mod n. Use modular exponentiation to compute 10^k mod n efficiently.

#include <iostream>
using namespace std;

typedef long long ll;

ll mod_power(ll base, ll exponent, ll modulus) {
    ll result = 1;
    base %= modulus;
    while (exponent > 0) {
        if (exponent & 1)
            result = (result * base) % modulus;
        base = (base * base) % modulus;
        exponent >>= 1;
    }
    return result;
}

int main() {
    ll n, m, k, x;
    cin >> n >> m >> k >> x;
    ll rounds = mod_power(10, k, n);
    ll shift = (m * rounds) % n;
    cout << (x + shift) % n << endl;
    return 0;
}

Minimizing Distance with Minimal Adjacent Swaps

Two sequences of n distinct integers represent heights of matches. The distance is defined as ∑(a_i - b_i)^2. Adjacent matches in either sequence can be swapped. Find the minimal number of adjacent swaps required to minimize the distance. Output the minimal swaps modulo 99,999,997.

Input Format

• First line: n
• Second line: n intgeers for sequence a
• Third line: n inetgers for sequence b

Output Format

One integer: minimal adjacent swaps modulo 99,999,997.

Solution

The minimal distance is achieved when the sequences have the same relative order. Map each element to its index in sequence b, then compute the inversion count of the permutation of indices in a relative to b.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MOD = 99999997;

struct Element {
    int value;
    int index;
};

bool compare(Element x, Element y) {
    return x.value < y.value;
}

class FenwickTree {
public:
    vector<int> tree;
    int size;

    FenwickTree(int n) {
        size = n;
        tree.resize(n+1, 0);
    }

    void update(int idx, int delta) {
        while (idx <= size) {
            tree[idx] = (tree[idx] + delta) % MOD;
            idx += idx & -idx;
        }
    }

    int query(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum = (sum + tree[idx]) % MOD;
            idx -= idx & -idx;
        }
        return sum;
    }
};

int main() {
    int n;
    cin >> n;
    vector<Element> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].value;
        a[i].index = i;
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i].value;
        b[i].index = i;
    }

    sort(a.begin(), a.end(), compare);
    sort(b.begin(), b.end(), compare);

    vector<int> mapping(n);
    for (int i = 0; i < n; i++)
        mapping[a[i].index] = b[i].index;

    FenwickTree ft(n);
    ll swaps = 0;
    for (int i = n-1; i >= 0; i--) {
        swaps = (swaps + ft.query(mapping[i])) % MOD;
        ft.update(mapping[i] + 1, 1);
    }
    cout << swaps << endl;
    return 0;
}

Maximum Cargo Transport Between Cities

n cities connected by m bidirectional roads, each with a weight limit. Answer q queries: for each pair of cities (x, y), find the maximum weight that can be transported from x to y without exceeding any road's limit.

Input Format

• First line: n m
• Next m lines: x y z (road between x and y with limit z)
• Next line: q (number of queries)
• Next q lines: x y (query)

Output Format

For each query, output the maximum cargo weight, or -1 if unreachable.

Constraints

• 0 < n < 10,000
• 0 < m < 50,000
• 0 < q < 30,000
• 0 ≤ z ≤ 100,000

Solution

Build a maximum spanning tree (using Kruskal) where the tree edge weight is the minimum limit on the unique path between two nodes. Use LCA with binary lifting to answer path minimum queries.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cstring>
using namespace std;

const int MAXN = 10005;
const int MAXM = 50005;
const int LOGN = 15;

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight > other.weight;
    }
};

struct TreeEdge {
    int to, weight;
};

vector<TreeEdge> tree[MAXN];
int parent[MAXN][LOGN], min_edge[MAXN][LOGN];
int depth[MAXN];
int root[MAXN];
bool visited[MAXN];

int find_root(int x) {
    if (root[x] != x)
        root[x] = find_root(root[x]);
    return root[x];
}

void union_set(int x, int y) {
    root[find_root(x)] = find_root(y);
}

void kruskal(vector<Edge>& edges, int n) {
    sort(edges.begin(), edges.end());
    for (int i = 1; i <= n; i++)
        root[i] = i;
    for (const Edge& e : edges) {
        if (find_root(e.u) != find_root(e.v)) {
            union_set(e.u, e.v);
            tree[e.u].push_back({e.v, e.weight});
            tree[e.v].push_back({e.u, e.weight});
        }
    }
}

void dfs(int u, int p, int w, int d) {
    visited[u] = true;
    depth[u] = d;
    parent[u][0] = p;
    min_edge[u][0] = w;
    for (int i = 1; i < LOGN; i++) {
        parent[u][i] = parent[parent[u][i-1]][i-1];
        min_edge[u][i] = min(min_edge[u][i-1], min_edge[parent[u][i-1]][i-1]);
    }
    for (const TreeEdge& e : tree[u]) {
        if (e.to != p) {
            dfs(e.to, u, e.weight, d+1);
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    int result = INT_MAX;
    for (int i = 0; i < LOGN; i++) {
        if (diff & (1 << i)) {
            result = min(result, min_edge[u][i]);
            u = parent[u][i];
        }
    }
    if (u == v) return result;
    for (int i = LOGN-1; i >= 0; i--) {
        if (parent[u][i] != parent[v][i]) {
            result = min(result, min(min_edge[u][i], min_edge[v][i]));
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    result = min(result, min(min_edge[u][0], min_edge[v][0]));
    return result;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++)
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].weight);
    
    kruskal(edges, n);
    memset(visited, false, sizeof(visited));
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            depth[i] = 0;
            dfs(i, 0, INT_MAX, 0);
        }
    }
    
    int q;
    scanf("%d", &q);
    while (q--) {
        int x, y;
        scanf("%d %d", &x, &y);
        if (find_root(x) != find_root(y)) {
            printf("-1\n");
        } else {
            printf("%d\n", lca(x, y));
        }
    }
    return 0;
}