Problem A: Shortest Increasing Path

The solution relies on direct case analysis based on the relationship between two integers, start and target. When the destination value strictly exceeds the starting point, a two-step traversal is always sufficient. If the start is at least two units larger than the target, a valid three-step route can be contsructed through intermediate nodes. Configurations where target equals 1, start equals target, or start is exactly one unit greater than target yield no valid path.

#include <iostream>

void process_query() {
    int start, target;
    std::cin >> start >> target;
    
    if (target == 1 || target == start) {
        std::cout << -1 << "\n";
        return;
    }
    if (target > start) {
        std::cout << 2 << "\n";
    } else if (start >= target + 2) {
        std::cout << 3 << "\n";
    } else {
        std::cout << -1 << "\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int cases;
    std::cin >> cases;
    while (cases--) {
        process_query();
    }
    return 0;
}

Problem B: Multiple Construction

This constructive task requires generating a sequence of length 2n containing two instances of every integer from 1 to n, such that the distance between identical values is divisible by their magnitude. A deterministic pattern satisfies these constraints without recursive search: output the integers in descending order, append n a second time, and finally output the integers from 1 to n-1 in ascending order. This arrangement guarantees that each number i appears at positions satisfying the divisibility condition.

#include <iostream>
#include <vector>

void process_query() {
    int n;
    std::cin >> n;
    
    std::vector<int> sequence;
    sequence.reserve(2 * n);
    
    for (int i = n; i >= 1; --i) sequence.push_back(i);
    sequence.push_back(n);
    for (int i = 1; i < n; ++i) sequence.push_back(i);
    
    for (size_t i = 0; i < sequence.size(); ++i) {
        std::cout << sequence[i] << (i == sequence.size() - 1 ? "\n" : " ");
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int cases;
    std::cin >> cases;
    while (cases--) {
        process_query();
    }
    return 0;
}

Problem C: Rabbits

Validating the binary sequence involves tracking the positional flexibility of '0' characters. The algorithm iterates through grouped indices of zeros, maintaining a state flag that indicates whether the current segment can independently satisfy pairing rules. Consecutive blocks or segments located at array boundaries inherently possess directional freedom. Isolated zeros must pair with another zero exactly two positions away; if such a pairinng exists, flexibility propagates forward, otherwise the configuration fails. This state-machine approach efficiently verifies feasibility across all zero clusters without backtracking.

#include <iostream>
#include <string>
#include <vector>

void solve() {
    int len;
    std::cin >> len;
    std::string s;
    std::cin >> s;
    
    std::vector<int> zeros;
    for (int i = 0; i < len; ++i) {
        if (s[i] == '0') zeros.push_back(i);
    }
    
    if (zeros.empty()) {
        std::cout << "YES\n";
        return;
    }
    
    bool flexible = false;
    int idx = 0;
    int z_count = zeros.size();
    
    while (idx < z_count) {
        int block_start = idx;
        while (idx + 1 < z_count && zeros[idx + 1] == zeros[idx] + 1) {
            idx++;
        }
        
        int block_len = idx - block_start + 1;
        bool prev_adjacent = (block_start > 0 && zeros[block_start] == zeros[block_start - 1] + 1);
        
        if (block_len + prev_adjacent > 1) {
            flexible = true;
            idx++;
            continue;
        }
        
        int pos = zeros[block_start];
        if (pos == 0 || pos == len - 1) {
            flexible = true;
        } else {
            bool left_gap = (block_start > 0 && zeros[block_start] - zeros[block_start - 1] == 2);
            if (left_gap && flexible) {
                flexible = true;
            } else {
                bool right_gap = (block_start + 1 < z_count && zeros[block_start + 1] - pos == 2);
                if (right_gap) {
                    flexible = false;
                    idx++; 
                } else {
                    std::cout << "NO\n";
                    return;
                }
            }
        }
        idx++;
    }
    std::cout << "YES\n";
}

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

Problem D: Game on Array

In this allocation game, even integers contribute equally to both participants' totals, making their final scores dependent on a simple split of they weighted sums. Odd integers dictate the competitive advantage. By isolating odd values and ranking them by frequency in descending order, players can simulate optimal alternating selection. Each claimed odd value transforms into its even counterpart (value - 1), merging into the shared pool. Final scores combine the allocated odd counts with half of the accumulated even values.

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

void solve() {
    int n;
    std::cin >> n;
    
    std::map<int, int> freq;
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        freq[val]++;
    }
    
    std::vector<std::pair<int, int>> odd_counts;
    long long shared_pool = 0;
    
    for (auto &[val, count] : freq) {
        if (val & 1) {
            odd_counts.emplace_back(count, val);
        } else {
            shared_pool += 1LL * val * count;
        }
    }
    
    std::sort(odd_counts.begin(), odd_counts.end(), std::greater<>());
    
    long long player1 = 0, player2 = 0;
    bool turn_player1 = true;
    
    for (auto &[count, val] : odd_counts) {
        if (turn_player1) player1 += count;
        else player2 += count;
        
        shared_pool += 1LL * (val - 1) * count;
        turn_player1 = !turn_player1;
    }
    
    player1 += shared_pool / 2;
    player2 += shared_pool / 2;
    std::cout << player1 << " " << player2 << "\n";
}

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

Problem E: Maximum OR Popcount

To maximize the number of set bits in a bitwise OR operation under a strict cost budget, we precompute the cumulative expense required to activate each bit position. Starting from the least significant bit, if a target bit is unset in the global OR sum, we evaluate all array elements to find the minimal addition needed to flip it on. This greedy adjustment accounts for lower-bit dependencies by recalculating costs iteratively. Once a cumulative cost table is established, each query determines the maximum affordable bit activations via a threshold scan.

#include <iostream>
#include <vector>
#include <climits>

void solve() {
    int n, q;
    std::cin >> n >> q;
    
    std::vector<int> arr(n);
    int global_or = 0;
    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
        global_or |= arr[i];
    }
    
    std::vector<int> cumulative_costs;
    cumulative_costs.push_back(0);
    
    for (int bit = 0; bit < 31; ++bit) {
        if ((global_or >> bit) & 1) continue;
        
        int step_cost = cumulative_costs.back();
        bool bit_present = false;
        
        for (int k = bit; k >= 0; --k) {
            int min_add = INT_MAX;
            int target_idx = -1;
            
            for (int i = 0; i < n; ++i) {
                if ((arr[i] >> k) & 1) {
                    bit_present = true;
                    break;
                }
                int mask = ((1 << (k + 1)) - 1);
                int lower_val = mask & arr[i];
                int needed = (1 << k) - lower_val;
                
                if (needed < min_add) {
                    min_add = needed;
                    target_idx = i;
                }
            }
            
            if (bit_present) break;
            step_cost += min_add;
            arr[target_idx] |= (1 << k);
        }
        cumulative_costs.push_back(step_cost);
    }
    
    int base_popcount = __builtin_popcount(global_or);
    while (q--) {
        int budget;
        std::cin >> budget;
        
        int extra_bits = 0;
        while (extra_bits + 1 < cumulative_costs.size() && cumulative_costs[extra_bits + 1] <= budget) {
            extra_bits++;
        }
        std::cout << base_popcount + extra_bits << "\n";
    }
}

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