Problem A: Minimum Carry Operations

Given n boxes where each trip can carry at most 2 boxes, the minimum number of trips required is ⌈n / 2⌉, which equals (n + 1) // 2 using integer division.

Problem B: Second Largest Unique Value

Given n integers with at least two distinct values, find the second largest unique value.

Approach 1 (Using Set): Insert all element into a std::set to automatically deduplicate and sort. The second-to-last element in the resulting container is the answer.

int n;
std::cin >> n;
std::set<int> unique_vals;
for (int i = 0; i < n; ++i) {
    int x;
    std::cin >> x;
    unique_vals.insert(x);
}
auto it = unique_vals.rbegin();
++it;
std::cout << *it << '\n';

Approach 2 (Sorting + Deduplication): Sort the array and use std::unique to remove duplicates. The second last element in the deduplicated range is the answer.

Approach 3 (Radix Sort for Linear Time): Since values are up to 10⁹, a base-10 radix sort can be applied in O(10·n) time. After sorting, deduplicate and select the second largest unique value.

void radix_sort(std::vector<uint32_t>& arr) {
    const int MAX_DIGITS = 10;
    std::vector<uint32_t> output(arr.size());
    std::vector<int> count(10);

    for (int exp = 1, digit = 0; digit < MAX_DIGITS; ++digit, exp *= 10) {
        std::fill(count.begin(), count.end(), 0);
        for (uint32_t val : arr)
            ++count[(val / exp) % 10];
        for (int i = 1; i < 10; ++i)
            count[i] += count[i - 1];
        for (int i = arr.size() - 1; i >= 0; --i)
            output[--count[(arr[i] / exp) % 10]] = arr[i];
        arr.swap(output);
    }
}

// Usage:
radix_sort(a);
a.erase(std::unique(a.begin(), a.end()), a.end());
std::cout << a[a.size() - 2] << '\n';

Radix sort leverages counting sort per digit, maintaining stability and achieving O(n·d) time where d is the number of digits.

Problem C: Lexicographically Smallest String with Limited Swaps

Given a string S of length N and an integer K, produce the lexicographically smallest string by changing at most K character positions.

Greedy Strategy: Construct the result character-by-character. For each position i, try placing the smallest possilbe character (from 'a' to 'z') that still allows the remaining positions to be fixed within the remaining budget.

To validate a candidate character c at position i:

• Count mismatches so far (bad).
• Add 1 if c ≠ S[i].
• Compute the minimal future mismatches as:
  N - i - Σ min(remaining_freq[x], target_freq[x])
  where remaining_freq is the count of characters left in the original suffix, and target_freq is the count needed from unused characters after choosing c.

If total mismatches ≤ K, commit to c.

int N, K;
std::cin >> N >> K;
std::string S;
std::cin >> S;

std::array<int, 26> rem_orig{}, rem_avail{};
for (char ch : S) {
    ++rem_orig[ch - 'a'];
    ++rem_avail[ch - 'a'];
}

std::string result;
int bad_count = 0;

for (int i = 0; i < N; ++i) {
    --rem_orig[S[i] - 'a'];

    for (int c = 0; c < 26; ++c) {
        if (rem_avail[c] == 0) continue;

        --rem_avail[c];
        result += ('a' + c);

        int future_mismatch = N - i - 1;
        for (int x = 0; x < 26; ++x) {
            future_mismatch -= std::min(rem_orig[x], rem_avail[x]);
        }

        int total_bad = bad_count + (result.back() != S[i]) + future_mismatch;
        if (total_bad <= K) {
            bad_count += (result.back() != S[i]);
            break;
        }

        result.pop_back();
        ++rem_avail[c];
    }
}

std::cout << result << '\n';

Time complexity: O(N·26²), feasible given constraints.

Problem D: Linear Recurrence with Bitwise Operations

A sequence A is defined for n ≥ 1 as:
A[n+K] = (C₁ & A[n+K−1]) ⊕ (C₂ & A[n+K−2]) ⊕ ⋯ ⊕ (C_K & A[n])
Given initial K terms of A and coefficients C, compute A[M] for M up to 10⁹.

Matrix Exponentiation over Bitwise Semiring: The recurrence is linear under the operations ⊕ (XOR) and & (AND). We model it using matrix exponentiation where:

• Matrix multiplication uses XOR as addition and AND as multiplication.
• The identity matrix uses 0xFFFFFFFF (all ones) on the diagonal.

Transition Matrix Construction:

• Rows 1 to K−1: shift identity — place 0xFFFFFFFF at (i, i+1).
• Row K: coefficients C_K, C_{K−1}, ..., C₁ from left to right.

Then, [A_M, A_{M+1}, ..., A_{M+K−1}]ᵀ = T^{M−1} · [A₁, ..., A_K]ᵀ, and we extract the first element.

using u32 = uint32_t;

struct BitMatrix {
    int n;
    std::vector<std::vector<u32>> data;

    BitMatrix(int size) : n(size), data(size, std::vector<u32>(size, 0)) {}

    static BitMatrix identity(int size) {
        BitMatrix I(size);
        for (int i = 0; i < size; ++i)
            I.data[i][i] = ~u32(0);
        return I;
    }

    BitMatrix operator*(const BitMatrix& other) const {
        BitMatrix res(n);
        for (int i = 0; i < n; ++i)
            for (int k = 0; k < n; ++k) if (data[i][k])
                for (int j = 0; j < n; ++j)
                    res.data[i][j] ^= data[i][k] & other.data[k][j];
        return res;
    }
};

BitMatrix power(BitMatrix base, long long exp) {
    auto result = BitMatrix::identity(base.n);
    while (exp > 0) {
        if (exp & 1) result = result * base;
        base = base * base;
        exp >>= 1;
    }
    return result;
}

// Main logic:
int K;
long long M;
std::cin >> K >> M;
std::vector<u32> A(K), C(K);
for (int i = 0; i < K; ++i) std::cin >> A[i];
for (int i = 0; i < K; ++i) std::cin >> C[i];

if (M <= K) {
    std::cout << A[M - 1] << '\n';
    return;
}

BitMatrix trans(K);
for (int i = 0; i < K - 1; ++i)
    trans.data[i][i + 1] = ~u32(0);
for (int j = 0; j < K; ++j)
    trans.data[K - 1][j] = C[K - 1 - j];

auto final_mat = power(trans, M - K);
u32 ans = 0;
for (int i = 0; i < K; ++i)
    ans ^= final_mat.data[0][i] & A[i];
std::cout << ans << '\n';

This approach runs in O(K³ log M) time, efficient for K ≤ 100.