USACO 2025 US Open Contest Silver Division - Sequence Construction

Problem link: TBA

Video link: here

Solution Author: Stefan Dascalescu

Problem Solution

In order to solve the problem, we must first find the optimal way to construct numbers which have a bitwise XOR of popcounts equal to \(k\). A way to think about it is to have popcounts equal to the powers of two making the bitwise representation of \(k\), and the smallest numbers having these number of bits are those equal to powers of two - \(1\).

For example, if we want a number with \(4\) bits, we would want to go for \(15\), as its binary representation is \(1111\).

After finding the initial set of numbers, we want to see whether the parity of this sum is the same as the parity of the target sum. If this happens, then we can simply append half the difference twice without affecting the overall XOR.

Otherwise, we need to change the parity and there are two possible optimal ways of doing it. Either we double the smallest number (they are all odd, so doubling it changes the parity), or we append \(1\) and \(2\) to the sequence. We can check the optimal way and see if we can construct the sum after that.

For more details check the solution code below.

Source code

The source code in C++ can be seen below.

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    long long m, k;
    cin >> m >> k;

    vector<long long> powers;
    long long sum = 0;
    for (int i = 0; i < 5; i++) {
        if (k & (1<<i)) {
            int val = (1<<(1<<i)) - 1;
            powers.push_back(val);
            sum += val;
        }
    }

    if (m < sum) {
        cout << -1 << '\n';
        return;
    }

    if ((m - sum) % 2 == 0) {
        if (m > sum) {
            powers.push_back((m - sum) / 2);
            powers.push_back((m - sum) / 2);
        }
    }
    else {
        if (powers[0] < 3) {
            sum += powers[0];
            powers[0] *= 2;
        }
        else {  
            powers.push_back(1);
            powers.push_back(2);
            sum += 3;
        }

        if (m < sum) {
            cout << -1 << '\n';
            return;
        }
        if (m > sum) {
            powers.push_back((m - sum) / 2);
            powers.push_back((m - sum) / 2);
        }
    }

    cout << powers.size() << '\n';
    for (auto x : powers) {
        cout << x << " ";
    }
    cout << '\n';
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }
    return 0;
}