Problem A: The Man who became a God

To solve this problem, consider the absolute differences between adjacent elements in the sequence. Let the sequence be (a_1, a_2, \dots, a_n). The total cost is initially the sum of (|a_i - a_{i+1}|) for all (1 \le i < n). The operation allows removing (k-1) of these differences to minimize the remaining sum.

The optimal strategy is to elimiante the largest differences. Calculate all (n-1) adjacent absolute differences, sort them in descending order, and sum the values starting from the (k)-th largest difference to the end. This effective subtracts the (k-1) largest values from the total sum.

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

using namespace std;

void solve() {
    int n, k;
    if (!(cin >> n >> k)) return;
    
    vector<int> diffs;
    int prev_val;
    cin >> prev_val;
    
    for (int i = 1; i < n; ++i) {
        int curr_val;
        cin >> curr_val;
        diffs.push_back(abs(curr_val - prev_val));
        prev_val = curr_val;
    }
    
    sort(diffs.begin(), diffs.end(), greater<int>());
    
    long long min_cost = 0;
    for (size_t i = k - 1; i < diffs.size(); ++i) {
        min_cost += diffs[i];
    }
    
    cout << min_cost << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

Problem B: Hamon Odyssey

The objective is to partition the array into the maximum number of contiguous segments such that the bitwise AND of each segment equals zero.

A greedy approach works here. Iterate through the array while maintaining a running bitwise AND value for the current segment. As soon as this running value becomes zero, a valid segment is formed. Increment the partition count and reset the running value to start a new segment. If the end of the array is reached and no segments were formed (meaning the total AND of the entire array is not zero, or logic dictates a single group), the answer is adjusted. Specifically, if the greedy pass yields zero partitions, it implies the entire array must be treated as a single group, provided the problem constraints allow it, but typically if no zero-AND sub-segment exists, the answer defaults to 1 if the total AND is zero, otherwise the problem constraints usually ensure a solution exists. Based on the standard logic for this problem, if no cut is made, the result is 1.

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int n;
    cin >> n;
    
    int partitions = 0;
    int current_and = -1;
    bool active = false;
    
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        
        if (!active) {
            current_and = val;
            active = true;
        } else {
            current_and &= val;
        }
        
        if (current_and == 0) {
            partitions++;
            active = false;
        }
    }
    
    if (partitions == 0) {
        partitions = 1;
    }
    
    cout << partitions << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

Problem C: Vampiric Powers, anyone?

The operations allowed imply that any generated number is the XOR sum of a contiguous subarray of the original sequence. The task reduces to finding the maximum XOR sum among all possible contiguous subarrays.

Using prefix XORs, the XOR sum of a subarray from index (l) to (r) can be expressed as (P_r \oplus P_{l-1}), where (P_i) is the prefix XOR up to index (i). Since the values in the array are small (less than (2^8)), the prefix XORs are also bounded within ([0, 255]).

To find the maximum XOR efficiently, maintain a boolean array or set tracking which prefix XOR values have been encountered so far. For each new prefix XOR calculated, compare it against all previously seen prefix XOR values to update the global maximum. This approach leverages the small value domain to avoid an (O(n^2)) brute force.

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

using namespace std;

void solve() {
    int n;
    cin >> n;
    
    vector<bool> seen(256, false);
    seen[0] = true;
    
    int prefix_xor = 0;
    int max_xor = 0;
    
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        prefix_xor ^= val;
        
        for (int j = 0; j < 256; ++j) {
            if (seen[j]) {
                max_xor = max(max_xor, prefix_xor ^ j);
            }
        }
        seen[prefix_xor] = true;
    }
    
    cout << max_xor << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}