A. Grid Navigation with Direction Toggle

Given an n × m grid, start at (1,1) with orientation o = 0. When o = 0, movement is only vertical; when o = 1, only horiznotal. Each move costs 1. At k specified positions, you may flip o (cost 1). Find the minimal cost to reach (n,m).

Solution: Model each toggle point as two nodes—one for each orientation—and connect them with toggle edges. Within rows/columns, connect adjacent points with movement edges weighted by Manhattan distance. Run Dijkstra from the start node (orientation 0 at (1,1)).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXK = 200010;

int read() {
    int x = 0, w = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * w;
}

vector<pair<int, int>> rowPoints[MAXK], colPoints[MAXK];
vector<pair<int, int>> graph[MAXK * 2];

void addEdge(int u, int v, int w) {
    graph[u].emplace_back(v, w);
}

ll dist[MAXK * 2];
bool visited[MAXK * 2];

void dijkstra(int start) {
    fill(dist, dist + MAXK * 2, LLONG_MAX);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    dist[start] = 0;
    pq.emplace(0, start);
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (auto [v, w] : graph[u]) {
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.emplace(dist[v], v);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n = read(), m = read(), k_input = read();
    vector<int> xs = {1}, ys = {1};
    int k = 1;
    for (int i = 0; i < k_input; ++i) {
        int x = read(), y = read();
        if (x == 1 && y == 1) {
            addEdge(1, 2, 1);
        } else if (x != n || y != m) {
            xs.push_back(x);
            ys.push_back(y);
            ++k;
        }
    }
    xs.push_back(n);
    ys.push_back(m);
    ++k;

    for (int i = 0; i < k; ++i) {
        rowPoints[xs[i]].emplace_back(ys[i], i);
        colPoints[ys[i]].emplace_back(xs[i], i);
    }

    for (int r = 1; r <= n; ++r) {
        sort(rowPoints[r].begin(), rowPoints[r].end());
        for (size_t j = 0; j + 1 < rowPoints[r].size(); ++j) {
            auto [y1, idx1] = rowPoints[r][j];
            auto [y2, idx2] = rowPoints[r][j + 1];
            int diff = y2 - y1;
            int u0 = idx1 * 2 + 1, v0 = idx2 * 2 + 1;
            int u1 = idx1 * 2 + 2, v1 = idx2 * 2 + 2;
            addEdge(u0, v0, diff);
            addEdge(v0, u0, diff);
            addEdge(u0, v1, diff + 1);
            addEdge(v0, u1, diff + 1);
        }
    }

    for (int c = 1; c <= m; ++c) {
        sort(colPoints[c].begin(), colPoints[c].end());
        for (size_t j = 0; j + 1 < colPoints[c].size(); ++j) {
            auto [x1, idx1] = colPoints[c][j];
            auto [x2, idx2] = colPoints[c][j + 1];
            int diff = x2 - x1;
            int u0 = idx1 * 2 + 1, v0 = idx2 * 2 + 1;
            int u1 = idx1 * 2 + 2, v1 = idx2 * 2 + 2;
            addEdge(u1, v1, diff);
            addEdge(v1, u1, diff);
            addEdge(u1, v0, diff + 1);
            addEdge(v1, u0, diff + 1);
        }
    }

    dijkstra(1);
    ll answer = min(dist[k * 2 - 1], dist[k * 2]);
    if (answer == LLONG_MAX) cout << "-1\n";
    else cout << answer << '\n';
    return 0;
}

B. Enumerating XOR Values of Increasing Subsequences

Given an array a of length n (≤10⁶), with values in [0,5000], output all distinct XOR values obtainable from strictly increasing subsequences.

Observation: All possible XOR results lie in [0, 8192). Use dynamic programming over value domain. For each value v, maintain a list of achievable XORs ending with elements ≤ v. When processing element x, extend existing XORs from lists indexed ≤ x, then update higher indices.

#include <bits/stdc++.h>
using namespace std;
const int MAXV = 8192;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<vector<int>> buckets(MAXV);
    vector<int> maxIndex(MAXV, MAXV - 1);
    vector<bool> possible(MAXV, false);
    possible[0] = true;
    int count = 1;

    for (int i = 1; i < MAXV; ++i)
        buckets[i].push_back(0);

    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        for (int base : buckets[x]) {
            int newVal = base ^ x;
            if (!possible[newVal]) {
                possible[newVal] = true;
                ++count;
            }
            while (maxIndex[newVal] > x) {
                buckets[maxIndex[newVal]--].push_back(newVal);
            }
        }
        buckets[x].clear();
    }

    cout << count << '\n';
    for (int i = 0; i < MAXV; ++i)
        if (possible[i]) cout << i << ' ';
    cout << '\n';
    return 0;
}

C. Counting Intervals with Absolute Majority

Count the number of subarrays where some element appears more than half the time.

O(n√n) approach: Discretize values. For frequent elements (≥√n occurrences), assign +1 to matches and −1 otherwise; count prefix sum inversions via Fenwick tree. For infrequent elements, iterate over all pairs of their positions and compute valid intervals using combinatorial formulas.

O(n log n) approach: For each distinct value w, define Pᵢ = 2·Sᵢ − i, where Sᵢ counts occurrences of w up to i. Valid intervals correspond to Pᵣ > Pₗ. Track segments of constatn slope in P and use three Fenwick trees to maintain coefficients for cubic prefix sums.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 200010;

ll queryFenwick(vector<ll>& bit, int idx) {
    ll res = 0;
    for (; idx > 0; idx -= idx & -idx) res += bit[idx];
    return res;
}

void updateFenwick(vector<ll>& bit, int idx, ll delta, int n) {
    for (; idx <= n; idx += idx & -idx) bit[idx] += delta;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;

    map<int, vector<int>> positions;
    for (int i = 0; i < n; ++i)
        positions[a[i]].push_back(i + 1);

    ll total = 0;
    const int OFFSET = 200003;

    auto addRange = [&](vector<vector<ll>>& bits, ll l, ll r, ll val) {
        auto apply = [&](int idx, ll coef0, ll coef1, ll coef2) {
            updateFenwick(bits[0], idx, coef0 * val, 2 * OFFSET);
            updateFenwick(bits[1], idx, coef1 * val, 2 * OFFSET);
            updateFenwick(bits[2], idx, coef2 * val, 2 * OFFSET);
        };
        ll t0 = l * l - 3 * l + 2;
        ll t1 = 3 - 2 * l;
        ll t2 = 1;
        apply(l + OFFSET, t0, t1, t2);
        t0 = -(l * l - 3 * l + 2) + (r - l + 1) * (r - l + 2) - 2 * r * (r - l + 1);
        t1 = -(3 - 2 * l) + 2 * (r - l + 1);
        t2 = -1;
        apply(r + 1 + OFFSET, t0, t1, t2);
    };

    auto eval = [&](vector<vector<ll>>& bits, ll x) -> ll {
        ll s0 = queryFenwick(bits[0], x + OFFSET);
        ll s1 = queryFenwick(bits[1], x + OFFSET);
        ll s2 = queryFenwick(bits[2], x + OFFSET);
        return (s0 + s1 * x + s2 * x * x) / 2;
    };

    for (auto& [val, pos] : positions) {
        pos.push_back(n + 1);
        vector<vector<ll>> bits(3, vector<ll>(2 * OFFSET + 10, 0));
        addRange(bits, 0, 0, 1);
        if (pos[0] > 1)
            addRange(bits, -pos[0] + 1, -1, 1);

        ll cnt = 0;
        for (size_t i = 0; i + 1 < pos.size(); ++i) {
            ++cnt;
            ll left = 2 * cnt - pos[i + 1] + 1;
            ll right = 2 * cnt - pos[i];
            total += eval(bits, right - 1) - eval(bits, left - 2);
            addRange(bits, left, right, 1);
        }
    }

    cout << total << '\n';
    return 0;
}

D. Digit-wise Knapsack with Max-per-digit Cost

Given n items (≤20000), each with value ≤10¹², select a subset. The cost is the sum over decimal digits of the maximum digit in that position across selected items. Minimize total cost.

Solution: Process digits from least to most significant. For digit position i (10ⁱ modulus), maintain a set of achievable residues mod 10ⁱ. Prune states: if three residues x < y < z satisfy z − x ≤ 10ⁱ⁻¹, discard y. This ensures ≤10 states per digit, yielding O(n log V) complexity.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<ll> items(n);
    for (ll& x : items) cin >> x;

    int totalCost = 0;
    ll power = 1;
    for (int digit = 0; digit < 17; ++digit) {
        ll modulus = power * 10;
        vector<ll> states = {0};
        for (ll item : items) {
            vector<ll> newStates;
            for (ll s : states)
                newStates.push_back((s + item) % modulus);
            sort(newStates.begin(), newStates.end());
            states.clear();
            for (ll ns : newStates) {
                if (states.empty() || ns - states.back() >= power)
                    states.push_back(ns);
            }
        }
        totalCost += states.back() / power;
        power = modulus;
    }
    cout << totalCost << '\n';
    return 0;
}