Expert.
Put your skills to the test.

Problem summary

There are2^n planets numbered0…2^n−1. Starting at k, use each jump length at most once and remain inside the range. Visit as many distinct planets as possible.

Source clarification. The bit-folding construction is equivalent to the official linear-output algorithm: https://infos.infosbg.com/files/Contests/ETI/2012/A/analyses/teleport_analysis.pdf.

Constraints

1≤n≤20;0≤k<2^n.

Worked example

An independently prepared worked example; constructive outputs may have other valid forms.

2 2

3
-1 2 -3

Solution analysis

1. Let mask=2^n−1. For j=0…2^(n−1)−1, output the pair of planet labels k XOR j and mask XOR(k XOR j). The first label is k, and each pair contains bitwise complements.
2. The first labels run through exactly one half of the labels, while their complements run through the other half. Thus every planet appears once. Print differences of consecutive labels rather than the labels themselves.
3. For n=2,k=2, the planet order is2,1,3,0. The signed jumps are−1,+2,−3, using every available length once. The output count3 is optimal because there are only three other planets.

Why it works

All labels are distinct by the half-and-complement argument. Within-pair differences give every odd absolute length once. Between-pair differences give every nonzero even length once: partitioning j by the number of trailing ones reduces this claim to the same construction on one fewer bit. This is the folded inductive construction described in the official editorial. Hence all2^n−1 lengths are distinct and every planet is visited.

Watch out. k is0-based. Print signed differences, not vertex labels. Ordinary Gray-code edges reuse powers of two and do not satisfy the distinct-length requirement.

An independently written complete program with standard headers.

#include<iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,start;
    cin>>n>>start;
    int count=1<<n;
    int mask=count-1;
    cout<<mask<<'\n';
    int previous=start;
    bool first=true;
    for(int j=0;j<count/2;j++){
        int a=start^j;
        int b=mask^a;
        // The first a is the starting planet, not a jump.
        if(j>0){
            if(!first){
                cout<<' ';
            }
            cout<<a-previous;
            first=false;
        }
        if(!first){
            cout<<' ';
        }
        cout<<b-a;
        first=false;
        previous=b;
    }
    cout<<'\n';
}