Problem A: Treasure Chest

We need to calculate the minimum time to reach the chest and return to the start, given the ability to pull the chest towards the key for a maximum distance of k. There are two scenarios based on the relative positions of the chest pos_chest and the key pos_key:

• If pos_key <= pos_chest: We pickup the key on the way to the chest. The total distance is simply pos_chest.
• If pos_key > pos_chest: We move the chest towards the key as much as possible. The new chest position is min(pos_chest + k, pos_key). We then proceed to the key and walk back to the chest. The total distance becomes pos_key + (pos_key - min(pos_chest + k, pos_key)).

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int pos_chest, pos_key, k;
        cin >> pos_chest >> pos_key >> k;
        if (pos_key <= pos_chest) {
            cout << pos_chest << "\n";
        } else {
            int new_chest = min(pos_chest + k, pos_key);
            cout << pos_key + (pos_key - new_chest) << "\n";
        }
    }
    return 0;
}

Problem B: Points and Minimum Distance

The objective is to pair 2n numbers into n coordinates such that the total Manhattan distance of a path traversing all points without backtracking is minimized. When backtracking is avoided, the total distance depends only on the extreme coordinates: X_max - X_min + Y_max - Y_min. To minimize this expression, we sort the 2n integers. The first n elements serve as the x-coordinates and the remaining n as the y-coordinates, which minimizes the spread in both dimensions.

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> vals(2 * n);
        for (int i = 0; i < 2 * n; ++i) cin >> vals[i];
        sort(vals.begin(), vals.end());
        int dist = (vals[n - 1] - vals[0]) + (vals[2 * n - 1] - vals[n]);
        cout << dist << "\n";
        for (int i = 0; i < n; ++i) {
            cout << vals[i] << " " << vals[n + i] << "\n";
        }
    }
    return 0;
}

Problem C: Torn Lucky Ticket

We need to find the number of pairs of pieces that form a "lucky ticket" when concatenated. A lucky ticket has equal sums of digits in its left and right halves. Given that ticket lengths are at most 5 and digit sums are at most 45, we can maintain a 2D frequency array freq[length][sum].

For each piece, we attempt to pair it with another piece either on its left or its right. If we append a piece to the left, we iterate over the number of digits i from the right of the current piece that will form the right half of the concatenated ticket. The length of the required left piece would be 2*i - L, and its digit sum must be 2*right_sum - total_sum. We add the corresponding frequency count to our answer. The same logic applies when appending to the right.

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

int freq[12][100];

int main() {
    int n;
    cin >> n;
    vector<string> tickets(n);
    for (int i = 0; i < n; ++i) {
        cin >> tickets[i];
        int len = tickets[i].size();
        int s = 0;
        for (char c : tickets[i]) s += c - '0';
        freq[len][s]++;
    }

    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        int L = tickets[i].size();
        int total_sum = 0;
        for (char c : tickets[i]) total_sum += c - '0';

        int right_sum = 0;
        for (int j = L - 1; j >= 0; --j) {
            right_sum += tickets[i][j] - '0';
            int left_len = 2 * (L - j) - L;
            int left_sum = 2 * right_sum - total_sum;
            if (left_len > 0 && left_sum > 0) {
                ans += freq[left_len][left_sum];
            }
        }

        int left_sum = 0;
        for (int j = 0; j < L; ++j) {
            left_sum += tickets[i][j] - '0';
            int right_len = 2 * (j + 1) - L;
            int right_req_sum = 2 * left_sum - total_sum;
            if (right_len > 0 && right_req_sum > 0) {
                ans += freq[right_len][right_req_sum];
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

Problem D: XOR Construction

Given an array a of size n-1, we must construct a permutation b of 0 to n-1 such that b_i ^ b_{i+1} = a_i. If we fix b_1, the rest of the array is completely determined since b_i = b_1 ^ prefix_i, where prefix_i is the prefix XOR of a. To ensure b is a valid permutation of [0, n-1], we need b_1 ^ prefix_i < n for all i.

We can build a binary trie containing all prefix_i values. We then iterate b_1 from 0 to n-1 and use the trie to find the maximum possible XOR value of b_1 with any prefix_i. If this maximum value is less than n, then b_1 is a valid starting value. We then reconstruct the sequence using this valid b_1.

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

struct Node {
    int ch[2];
} trie[6000005];
int node_cnt = 1;

void insert(int val) {
    int curr = 1;
    for (int i = 19; i >= 0; --i) {
        int bit = (val >> i) & 1;
        if (!trie[curr].ch[bit]) {
            trie[curr].ch[bit] = ++node_cnt;
        }
        curr = trie[curr].ch[bit];
    }
}

int max_xor(int val) {
    int curr = 1, res = 0;
    for (int i = 19; i >= 0; --i) {
        int bit = (val >> i) & 1;
        if (trie[curr].ch[bit ^ 1]) {
            res |= (1 << i);
            curr = trie[curr].ch[bit ^ 1];
        } else {
            curr = trie[curr].ch[bit];
        }
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n), pref(n);
    for (int i = 1; i < n; ++i) {
        cin >> a[i];
        pref[i] = pref[i - 1] ^ a[i];
        insert(pref[i]);
    }

    int start_val = 0;
    for (; start_val < n; ++start_val) {
        if (max_xor(start_val) < n) break;
    }

    cout << start_val;
    for (int i = 1; i < n; ++i) {
        cout << " " << (start_val ^ pref[i]);
    }
    cout << "\n";
    return 0;
}