PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Daanish Mahajan
Tester: Aryan
Editorialist: Taranpreet Singh
DIFFICULTY
Easy-Medium
PREREQUISITES
Casework and Bitwise operations
PROBLEM
Given integers K and N, find a subset of numbers in the range [1, N] such that the size of the subset is K and the bitwise XOR of the subset is maximum possible.
EXPLANATION
Subtask 1
A Brute force approach would be to try all subsets and considering only subsets of size K, pick the one with maximal XOR. The time complexity of this approach is O(N*2^N), and this shall be sufficient only for the first subtask
Subtask 2
Let us use Dynamic Programming here. Let’s denote state (X, SZ, XOR) as the subset of elements in range [1, X] such that the size of subset is SZ and bitwise XOR of subset elements is XOR. We can make forward transitions from state (X, SZ, XOR) to (X+1, SZ, XOR) if element (X+1) is not included, and to state (X+1, SZ+1, XOR \oplus (X+1)) if element (X+1) is included in subset.
Each state can be represented by a boolean variable, leading to a three-dimensional boolean array depicting whether there exists a subset of first X elements whose size is SZ and whose XOR is XOR.
Additionally, to recover the actual subset, create another three-dimensional boolean array, say P, such that if DP(X, SZ, XOR) is true, then P(X, SZ, XOR) = true reflect that element X is included in the subset which had size SZ and XOR XOR.
This is a well-known technique related to Dynamic Programming, which can be used to recover the actual subset. One example is here.
Code for subtask 2
import java.util.*;
import java.io.*;
class OPTSET{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), K = ni();
int M = Integer.highestOneBit(N)<<1;
boolean[][][] DP = new boolean[1+N][1+K][M];
boolean[][][] taken = new boolean[1+N][1+K][M];
DP[0][0][0] = true;
for(int i = 0; i< N; i++){
for(int sz = 0; sz <= K; sz++){
for(int xor = 0; xor < M; xor++){
if(!DP[i][sz][xor])continue;
if(!DP[i+1][sz][xor]){
DP[i+1][sz][xor] = true;
taken[i+1][sz][xor] = false;
}
if(sz+1 <= K && !DP[i+1][sz+1][xor^(i+1)]){
DP[i+1][sz+1][xor^(i+1)] = true;
taken[i+1][sz+1][xor^(i+1)] = true;
}
}
}
}
int maxXor = M-1;
while(!DP[N][K][maxXor])maxXor--;
boolean[] inc = new boolean[1+N];
for(int i = N, sz = K, xor = maxXor; i>= 1; i--){
if(taken[i][sz][xor]){
inc[i] = true;
sz--;
xor ^= i;
}
}
for(int i = 1; i<= N; i++)
if(inc[i])
p(i+" ");
pn("");
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new OPTSET().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Final Subtask
We need to do a lot of casework, trying to find the maximal XOR of the subset.
Let us handle tests with N \leq 7 by subtask 1 solution.
Let’s make cases based on values of K
K = 1
Since we select only 1 element, select N as that leads to maximal XOR
K = 2
We need to select two elements with maximal XOR. Let’s find largest B such that 2^B \leq N. Then 2^{B+1}-1 is the maximal XOR possible from a subset of integers from [1, N]. Let’s pick two integers 2^B and 2^B-1 as their XOR is 2^{B+1}-1
K = N
All elements must be selected.
K = N-1
All but one element must be selected. Let’s compute X = 1 \oplus 2 \oplus \ldots \oplus N. We must exclude element v such that X \oplus v is maximized, which can be easily checked with a single loop.
K = N-2
Now, we need to exclude two elements. Again, let’s include all elements in subset for now and compute X = 1 \oplus 2 \oplus \ldots \oplus N. Now we need to exclude two elements x and y such that X \oplus x \oplus y is maximum possible.
It is easy to prove that maximizing X \oplus x \oplus y is same as minimizing X \oplus (2^{B+1}-1) \oplus x \oplus y. So let’s take X = X \oplus (2^{B+1}-1).
We can see that we need to exclude two elements x and y such that X \oplus x \oplus y is minimum possible, where 1 \leq x, y \leq N and x \neq y
- If X = 0, we cannot make X \oplus x \oplus y = 0 as that requires x = y. So let’s choose x = 2 and y = 3, making X \oplus 2 \oplus 3 = 1
- If X = 2^b for some b, let’s choose x = 2^b+2^c and y = 2^c where c \neq b. Specifically, if b \gt 0, choose c = 0, else choose c = 1. This way, X \oplus x \oplus y = 0
- Otherwise, X has at least two bits set. Let’s choose x = 2^b such that 2^b is the largest power of two less than X, and choose y = X \oplus x. This way, X \oplus x \oplus y = X \oplus x \oplus X \oplus x = 0
All these choices are such that X \oplus x \oplus y becomes minimum possible, as X \oplus x \oplus y is the XOR of remaining two elements XORed with 2^{B+1}-1. So if X \oplus x \oplus y = 0, it implies XOR of remaining elements is 2^{B+1}-1 which is maximum possible.
General case
Now, we have 3 \leq K \leq N-3. We shall do casework just like we did for K = N-2 case.
Let’s include first K elements in subset. Now, we’ll aim to swap some elements from included to not-included and from not-included to included state such that XOR of included elements.
Let’s compute X = 1 \oplus 2 \oplus \ldots \oplus K. Now, this time, our current subset has exactly K elements and has XOR X, so we need to swap some elements from not-included and from include to not-included such that the number of elements remains same, and XOR is maximized.
Let’s try following cases
-
K \lt 2^B-1
We have both 2^B-1 and 2^B not inluded currently, and we see that (2^B-1) \oplus 2^B = 2^{B+1}-1, which is maximum XOR possible. So we’ll add these two elements into subset and remove two elements x and y such that Y = X \oplus x \oplus y becomes minimum possible. Let’s apply similar logic as K = N-2 again- If X = 0, then instead of adding 2^{B-1}-1 and 2^{B-1}, let’s add elements 2^B-2 and 2^B and remove elements 2 and 3 from subset. This way, X \oplus (2^B-2) \oplus 2^B \oplus 2 \oplus 3 = 2^B \oplus (2^B-1) = 2^{B+1}-1
- If X = 2^b for some b, then let’s choose c \neq b.
- If b \gt 0, exclude elements 2^b and 1, and add elements 2^B-2 and 2^B, as X \oplus 2^b \oplus 1 \oplus (2^B-2) \oplus 2^B = 2^{B+1}-1
- If X = 2^0, exclude elements 2 and 3 and add elements 2^B-1 and 2^B, as 1 \oplus 2 \oplus 3 \oplus (2^B-1) \oplus 2^B = 2^{B+1}-1
- Otherwise, X has at least two bits set. Let’s include elements 2^B-1 and 2^B and exclude two elements x = 2^b and y = X \oplus 2^b where 2^b \leq X and b is largest possible.
-
If K = 2^B-1, then simply add element 2^B and remove 2^B-1, making XOR 2^{B+1}-1
-
If K \gt 2^B -1
Now, both 2^B and 2^B-1 are already included. X is the XOR of all elements.- If X \lt 2^B, then we can simply include element K+1 into subset, and remove v = X \oplus (K+1) \oplus (2^{B+1}-1) from subset. We can see that v \lt 2^B, therefore already included in subset.
- Now we have X \geq 2^B. Let’s add two elements x and y into subset such that Y = X \oplus (2^{B+1}-1) \oplus x \oplus y \neq 0. For convenience, include K+1 and one from K+2 and K+3 satisfying above criteria. Additionally, now all elements till 2^B+1 are included in subset. The purpose behind Y \neq 0 is that we now need to exclude two elements w and z from subset such that w \neq z and Y \oplus w \oplus z = 0, which is possible only if Y \gt 0.
- If Y = 2^b for some b, then choose w = 2^b+2^c where c \neq b and z = 2^c. Choose smallest such c.
- Otherwise, Y has atleast 2 bits set. Choose w = 2^b where 2^b \leq Y and b is largest possible, and choose z = Y \oplus w.
If you have managed to follow till here, Congratulations, you have sovled this huge labyrinth of casework. I understand the pain you had to go through to unravel this massive mess.
TIME COMPLEXITY
The time complexity is O(T*log(N) + \sum K)
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
# define pb push_back
#define pii pair<int, int>
#define mp make_pair
# define ll long long int
using namespace std;
const int maxt = 10000, maxn = 1e6, maxtn = 4e6, maxk = 1e6, maxtk = 2e6;
const string newln = "\n", space = " ";
bool inc[maxn + 10];
int n, k;
void add(int x){
assert(!inc[x]);
inc[x] = true;
}
void remove(int x){
assert(inc[x]);
inc[x] = false;
}
int hsb(int x){
int ans = -1;
while(x > 0){
x >>= 1; ans++;
}
return ans;
}
int main()
{
int t; int tn = 0, tk = 0;
cin >> t;
while(t--){
cin >> n >> k; tn += n; tk += k;
if(k == 1){
inc[n] = true;
}else{
int b = hsb(n);
if(b <= 2){
int mxr = -1, mid = -1;
for(int i = 1; i < 1 << n; i++){
if(__builtin_popcount(i) != k)continue;
int pxr = 0;
for(int j = 0; j < n; j++){
if((i >> j) & 1)pxr ^= (j + 1);
}
if(pxr > mxr){
mxr = pxr; mid = i;
}
}
for(int j = 0; j < n; j++){
if((mid >> j) & 1)inc[j + 1] = true;
}
}else{
int maxans = (1 << (b + 1)) - 1;
if(n == k){
for(int i = 1; i <= n; i++)inc[i] = true;
}else if(n == k + 1){
int txr = 0;
for(int i = 1; i <= n; i++){
inc[i] = true; txr ^= i;
}
int mxr = -1, skip = -1;
for(int i = 1; i <= n; i++){
if((txr ^ i) > mxr){
mxr = txr ^ i;
skip = i;
}
}
remove(skip);
}else if(n == k + 2){
int txr = maxans;
for(int i = 1; i <= n; i++){
inc[i] = true; txr ^= i;
}
int mb = hsb(txr), first, second;
int sb = __builtin_popcount(txr);
if(sb >= 2){
first = 1 << mb; second = txr ^ first;
}else if(sb == 1){
first = mb == 0 ? 2 : 1; second = (1 << mb) + first;
}else{
first = 2; second = 3;
}
remove(first); remove(second);
txr ^= first ^ second; assert(sb == 0 ? txr == 1 : txr == 0);
}else{
int txr = 0;
for(int i = 1; i <= k; i++){
inc[i] = true; txr ^= i;
}
int sb = __builtin_popcount(txr);
int mb = hsb(txr);
if(k < (1 << b) - 1){
int afirst, asecond, bfirst, bsecond;
if(sb >= 2){
afirst = 1 << b; asecond = afirst - 1;
bfirst = 1 << mb; bsecond = txr ^ bfirst;
}else if(sb == 1){
if(mb == 0){
afirst = 1 << b; asecond = afirst - 1;
bfirst = (1 << mb) + 2; bsecond = 2;
}else{
afirst = 1 << b; asecond = afirst - 2;
bfirst = 1 << mb; bsecond = 1;
}
}else{
afirst = 1 << b; asecond = afirst - 4;
bfirst = 1; bsecond = 2;
}
add(afirst); add(asecond);
remove(bfirst); remove(bsecond);
txr ^= afirst ^ asecond ^ bfirst ^ bsecond; assert(txr == maxans);
}else if(k == (1 << b) - 1){
int first = (1 << b), second = first - 1;
add(first);
remove(second);
txr ^= first ^ second; assert(txr == maxans);
}else{
if(txr & (1 << b)){
int afirst, asecond, bfirst, bsecond;
if((txr ^ (k + 1) ^ (k + 2)) == maxans){
afirst = k + 1; asecond = k + 3;
}else{
afirst = k + 1; asecond = k + 2;
}
txr ^= afirst ^ asecond;
assert(txr != maxans);
txr ^= maxans;
int mb = hsb(txr);
if(__builtin_popcount(txr) >= 2){
bfirst = 1 << mb; bsecond = bfirst ^ txr;
}else{
bfirst = mb == 0 ? 2 : 1; bsecond = (1 << mb) + bfirst;
}
add(afirst); add(asecond);
remove(bfirst); remove(bsecond);
txr ^= bfirst ^ bsecond; assert(txr == 0);
}else{
int first = k + 1, second = txr ^ first ^ maxans;
add(first);
remove(second);
}
}
}
}
}
int ck = 0, txr = 0;
for(int i = 1; i <= n; i++){
if(inc[i]){
txr ^= i;
cout << i << (ck == k - 1 ? newln : space);
inc[i] = false; ck++;
}
}
assert(ck == k);
}
assert(tn <= maxtn); assert(tk <= maxtk);
}
Tester's Solution
/* in the name of Anton */
/*
Compete against Yourself.
Author - Aryan (@aryanc403)
Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/
#ifdef ARYANC403
#include <header.h>
#else
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize ("-ffloat-store")
#include<bits/stdc++.h>
#define dbg(args...) 42;
#endif
using namespace std;
#define fo(i,n) for(i=0;i<(n);++i)
#define repA(i,j,n) for(i=(j);i<=(n);++i)
#define repD(i,j,n) for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"
typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
vi readVectorInt(int n,lli l,lli r){
vi a(n);
for(int i=0;i<n-1;++i)
a[i]=readIntSp(l,r);
a[n-1]=readIntLn(l,r);
return a;
}
const lli INF = 0xFFFFFFFFFFFFFFFL;
lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}
class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{ return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }};
void add( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt==m.end()) m.insert({x,cnt});
else jt->Y+=cnt;
}
void del( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt->Y<=cnt) m.erase(jt);
else jt->Y-=cnt;
}
bool cmp(const ii &a,const ii &b)
{
return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}
#define bcnt(x) (__builtin_popcountll(x))
const lli mod = 1000000007L;
// const lli maxN = 1000000007L;
lli getMsb(lli n){
const lli logN=30;
for(lli i=logN;i>=0;i--){
if(n&(1LL<<i))
return i;
}
dbg(n);
assert(false);
}
void bruteforce(lli n,lli k){
lli mx=-1,ans=0;
for(lli msk=0;msk<(1LL<<n);++msk){
if(bcnt(msk)!=k)
continue;
lli cur=0;
for(lli j=0;j<n;++j){
if(msk&(1LL<<j))
cur^=j+1;
}
if(cur>mx){
mx=cur;
ans=msk;
}
}
for(lli j=0;j<n;++j){
if(ans&(1LL<<j))
cout<<j+1<<" ";
}
cout<<endl;
}
void solve(lli n,lli k){
if(n<8){
bruteforce(n,k);
return;
}
dbg(n,k);
const lli msb=getMsb(n);
const lli mxAns=(2LL<<msb)-1;
vi vis(n+1);
bool fl=true;
if(k==1){
vis[n]=1;
fl=false;
}
else if(k==n){
fl=false;
vis=vi(n+1,1);
} else if(k==n-1){
fl=false;
lli cnt=0;
for(lli i=1;i<=n;++i)
cnt^=i;
lli rmv=1;
for(lli i=1;i<=n;++i){
if((cnt^i)>(cnt^rmv))
rmv=i;
}
vis=vi(n+1,1);
vis[rmv]=0;
} else if(k==n-2){
lli cnt=0;
for(lli i=1;i<=n;++i)
cnt^=i;
cnt^=mxAns;
vis=vi(n+1,1);
const lli bitc=__builtin_popcountll(cnt);
if(bitc>=2)
{
const lli f=getMsb(cnt);
vis[1LL<<f]=vis[cnt^(1LL<<f)]=0;
}
else if(bitc==1)
{
const lli f=getMsb(cnt);
const lli b=(f?0:1);
vis[1LL<<b]=vis[cnt^(1LL<<b)]=0;
}
else
{
vis[1LL<<msb]=vis[(1LL<<msb)+1]=0;
fl=false;
}
} else {
lli cnt=0;
for(lli i=1;i<=k;++i){
cnt^=i;
vis[i]=1;
}
if(k<(1LL<<msb)-1){
const lli bitc = bcnt(cnt);
if(bitc>=2){
vis[1LL<<msb]=vis[(1LL<<msb)-1]=1;
cnt^=(1LL<<msb)^((1LL<<msb)-1)^mxAns;
const lli f=getMsb(cnt);
vis[1LL<<f]=vis[cnt^(1LL<<f)]=0;
}
else if(bitc==1) {
const lli f=getMsb(cnt);
if(f){
vis[(1LL<<msb)]=vis[(1LL<<msb)-2]=1;
vis[cnt]=vis[1]=0;
} else {
vis[(1LL<<msb)]=vis[(1LL<<msb)-1]=1;
vis[cnt^2]=vis[2]=0;
}
} else {
vis[(1LL<<msb)]=vis[(1LL<<msb)-4]=1;
vis[1]=vis[2]=0;
}
} else if(k==(1LL<<msb)-1){
vis[1LL<<msb]=1;
vis[(1LL<<msb)-1]=0;
} else {
if((cnt&(1LL<<msb))==0){
vis[k+1]=1;
cnt^=k+1;
vis[cnt^mxAns]=0;
} else {
cnt^=k+1;
vis[k+1]=1;
if((cnt^(k+2))==mxAns){
cnt^=k+3;
vis[k+3]=1;
} else{
cnt^=k+2;
vis[k+2]=1;
}
cnt^=mxAns;
const lli bitc=bcnt(cnt);
if(bitc>=2){
const lli f=getMsb(cnt);
vis[1LL<<f]=vis[cnt^(1LL<<f)]=0;
} else {
const lli f=getMsb(cnt);
const lli b=(f?0:1);
vis[1LL<<b]=vis[cnt^(1LL<<b)]=0;
}
}
}
}
lli ans=0,val=0;
for(lli i=1;i<=n;++i){
if(vis[i])
{
cout<<i<<" ";
ans^=i;
val++;
}
}
// cout<<ans;
dbg(vis);
assert(val==k);
if(fl){
dbg(n,k,ans);
assert(ans==(2LL<<msb)-1);
}
cout<<endl;
}
int main(void) {
ios_base::sync_with_stdio(false);cin.tie(NULL);
// freopen("txt.in", "r", stdin);
// freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
lli T=readIntLn(1,1e4);
lli sumn=0,sumk=0;
while(T--)
{
const lli n=readIntSp(1,1e6);
const lli k=readIntLn(1,n);
sumn+=n;
sumk+=k;
assert(sumn<=4e6);
assert(sumk<=2e6);
solve(n,k);
} aryanc403();
readEOF();
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class OPTSET{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), K = ni();
int maxAns = (Integer.highestOneBit(N)<<1)-1;
//M-1 is the maximum XOR possible
boolean[] inc = new boolean[1+N];
if(N <= 7){
int best = brute(N, K);
for(int i = 0; i< N; i++)if(((best>>i)&1) == 1)inc[i+1] = true;
}else if(K == 1){
inc[N] = true;
}else if(K == 2){
int B = Integer.highestOneBit(N);
//V^(V-1) = M-1 holds
inc[B-1] = inc[B] = true;
}else if(K == N){
for(int i = 1; i<= N; i++)inc[i] = true;
}else if(K+1 == N){
//Try excluding each element one by one, and pick the choice leading to maximal XOR
int X = 0;
for(int i = 1; i<= N; i++)X ^= i;
int exc = 0, xor = -1;
for(int i = 1; i<= N; i++)if((X^i) > xor){
exc = i;
xor = X^i;
}
//exc is the element excluded
for(int i = 1; i<= N; i++)if(i != exc)inc[i] = true;
}else if(K+2 == N){
int XOR = 0;
for(int i = 1; i<= N; i++){
inc[i] = true;
XOR ^= i;
}
XOR ^= maxAns;
//Now we want to flip 2 positions x and y such that x^y = XOR
//Deleting two elements x and y such that x^y = XOR
if(bitCount(XOR) >= 2){
int x = Integer.highestOneBit(XOR), y = XOR^x;
inc[x] = inc[y] = false;
}else if(bitCount(XOR) == 1){
if(XOR == 1){
int x = 2, y = 3;
inc[x] = inc[y] = false;
}else{
int x = XOR^1, y = 1;
inc[x] = inc[y] = false;
}
}else{
//We cannot achieve maxAns, so we achieve maxAns-1 by removing x and y such that x^y = 1
int x = Integer.highestOneBit(N), y = x+1;
inc[x] = inc[y] = false;
}
}else{
//3 <= K <= N-3
int XOR = 0;
for(int i = 1; i<= K; i++){
inc[i] = true;
XOR ^= i;
}
int B = Integer.highestOneBit(N);
if(K < B-1){
int btc = bitCount(XOR);
if(btc >= 2){
inc[B-1] = inc[B] = true;
XOR ^= (B-1)^B^maxAns;
int x = Integer.highestOneBit(XOR), y = XOR^x;
inc[x] = inc[y] = false;
}else if(btc == 1){
if(XOR == 1){
inc[B-1] = inc[B] = true;
inc[2] = inc[3] = false;
}else{
inc[B-2] = inc[B] = true;
inc[XOR] = inc[1] = false;
}
}else{
inc[B] = inc[B-2] = true;
inc[2] = inc[3] = false;
}
}else if(K == B-1){
inc[B] = true;
inc[B-1] = false;
}else{
if((XOR & B) == 0){
inc[K+1] = true;
XOR ^= K+1;
inc[XOR^maxAns] = false;//XOR^maxAns shall have highest bit off, hence included in subset
}else{
if((XOR^(K+1)^(K+2)) == maxAns){
inc[K+1] = inc[K+3] = true;
XOR ^= (K+1)^(K+3);
}else{
inc[K+1] = inc[K+2] = true;
XOR ^= (K+1)^(K+2);
}
XOR ^= maxAns;
if(bitCount(XOR) >= 2){
int x = Integer.highestOneBit(XOR), y = XOR^x;
inc[x] = inc[y] = false;
}else{
if(XOR == 1){
inc[2] = inc[3] = false;
}else{
inc[XOR+1] = inc[1] = false;
}
}
}
}
}
for(int i = 1; i<= N; i++)
if(inc[i])
p(i+" ");
pn("");
}
int bitCount(int x){
return x == 0?0:(1+bitCount(x&(x-1)));
}
int brute(int N, int K){
int best = 0, maxXor = -1;
for(int mask = 1; mask < 1<<N; mask++){
if(bitCount(mask) != K)continue;
int XOR = 0;
for(int i = 0; i< N; i++)if(((mask>>i)&1)==1)XOR ^= (1+i);
if(XOR > maxXor){
maxXor = XOR;
best = mask;
}
}
return best;
}
void dbg(Object... o){System.err.println(Arrays.deepToString(o));}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new OPTSET().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 