Two Fun Constructive Problems

April 1, 2026

I generally don't enjoy constructive problems, but recently I solved two that were surprisingly satisfying. My solution turned out quite different from the one proposed in the editorial, so I wanted to share my thought process.

Both problems are quite straightforward (the first one being rated \( 1500 \), the second one \( 1800 \)) and have short implementations.

Even-Odd XOR

Link to the problem

Given an integer \( n \), find any array \( a \) of \(n \) distinct nonnegative integers less than \( 2^{31} \) such that the bitwise XOR of the elements on odd indices equals the bitwise XOR of the elements on even indices.

Let's kick off with some observations. As it's very frequent with this kind of questions involving bitwise operations, it helps to reason bit-by-bit. In particular, the bitwise XOR of the elements on odd indices equals the bitwise XOR of the elements on even indices if and only if the corresponding bits match.

But what does the XOR of a single bit across multiple elements represent? The parity of that bit! More specifically: if the bit is set to \( 1 \) an even number of times, the XOR is \( 0 \); if the bit is set to \( 1 \) an odd number of times, the XOR is \( 1 \). (\( 0 \)s are going to have no effect on the XOR, while pairs of \( 1 \)s are going to cancel out.) Therefore, for any given bit position (there are \( 31 \) such positions, since we are working with nonnegative integers less than \( 2^{31} \)), the count of \( 1 \)s must have the same parity for the elements on the even and odd indeces.

This condition doesn't seem very restrictive. In fact, flipping a single bit on one element is sufficient to make the parity match, and it doesn't matter whether that element sits at an even or odd position. In theory, we could just generate \( n - 1 \) distinct elements, using the final one to satisfy the XOR condition: we just need to ensure that it won't already be present in the sequence.

The solution is surprisingly simple: randomness! If we randomly generate \( n - 1 \) distinct elements, the likelihood that the final one will already be in the sequence is \( (n - 1) / 2^{31} \) which, even in the worst case scenario (for \( n = 2 \cdot 10^5 \)), is going to be significantly less than \( 1\% \). (And if we do hit this unfortunate case, we can just try again.)

This leads to a very compact solution. Here is my implementation (I typically use C++, but when it comes to RNG I find Python's random module to be much more convinient):

            
import random

t = int(input())
for _ in range(t):
    n = int(input())
    while True:
        a = random.sample(range(0, 2 ** 31), n - 1)
        xor = 0
        for i in range(n - 1):
            xor ^= a[i]
        if xor not in a:
            a.append(xor)
            print(" ".join(map(str, a)))
            break

Increasing Subsequences

Link to the problem

You are given a positive integer \( X \). Your task is to find an array of integers of length at most \( 200 \), such that it has exactly \( X \) increasing subsequences, or report that there is no such array.

It's helpful to start by considering some simple cases. For example, suppose that \( a \) is increasing, what is the number of increasing subsequences? Since every subsequence is going to be increasing (by definition we cannot change the order of the elements in a subsequence), the number of increasing subsequences is going to be exactly the number of subsequences. For an array \( a \) of length \( n \), there are exactly \( 2^n \) subsequences. (Think of a subsequence as a subset of indices, the set of all subsequences is going to be the powerset of the set of indices, and since the set of indices has cardinality \( n \), the set of subsequences is going to have cardinality \( 2^n \).)

This already gives us a good starting point: we can start constructing our sequence by picking the largest power of two smaller than or equal to \( X \) and then try to satisfy our condition by adding some elements at the end of it. So, what happens when we add a new element at the end of our increasing subsequence? The answer strictly depends on the number of smaller elements to its left. Say there are \( k \) smaller elements to its left (clearly \( 0 \leq k \leq n \)), the new element will form a new increasing subsequence for each increasing subsequence involving any number of these \( k \) elements, and there are exactly \( 2^k \) such sequences.

This is great, at each step we can just add a new element to our sequence and, if we can control how many smaller elements in increasing order there are to its left, we can simply build \( X \) as sums of powers of two: its binary representation! We can make sure that we don't mess up the count of smaller elements in increasing order by making sure that every new number we add is smaller than the previous.

A clean implementation takes advantage of the binary representation of \( X \): we start from the most significant bit and add each element starting from \( 0 \) and going up to the index of the MSB, then we traverse the remaining set bits from the most to the least significant adding their index to the sequence.

As a more concrete example consider \( X = 13 = 2^3 + 2^2 + 2^0 = (1101)_2 \). Notice that the bits at indices \( 3 \), \( 2 \), and \( 0 \) are set. We start from the most significant bit (index \( 3 \)) and add the numbers from \( 0 \) to \( 3 - 1 = 2 \), creating an increasing subsequence of length \( 3 \). Now \( a = [0, 1, 2] \). Then we add the indeces of the remaining set bits in decreasing order. So \( a = [0, 1, 2, 2, 0] \). Notice that, by the way we constructed the initial sequence, simply adding the number \( k \) at the end ensures that there are exactly \( k \) smaller elements to its left, and because we add elements in decreasing order, this is always true.

So here is my implementation (this time in C++):


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;

	while (t--) {
		ll X;
		cin >> X;

		vector<int> ans;

		ll msb = 63 - __builtin_clzll(X);
		for (int i = 0; i < msb; i++) {
			ans.push_back(i);
		}
		for (int i = msb - 1; i >= 0; i--) {
			if ((X >> i) & 1) {
				ans.push_back(i);
			}
		}

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