# PERMXOR - Editorial

Setter: Prasant Kumar
Tester: Harris Leung
Editorialist: Trung Dang

Medium

Bit Manipulation

# PROBLEM:

For a permutation P of length N (where N is an even integer), we define the function F(P) as:

F(P) = (P_1 \oplus P_2) + (P_3 \oplus P_4) + \ldots + (P_{n-1} \oplus P_n). Here, \oplus denotes the bitwise XOR operation.

Given an even integer N, construct a permutation P of length N, such that F(P) is minimum.

# EXPLANATION:

Define T_i = P_{2i - 1} \oplus P_{2i} for all 1 \le i \le \frac{N}{2}, our goal is to minimize \sum T.

We have the following observation:

T_1 \oplus T_2 \oplus \ldots \oplus T_{N/2} = P_1 \oplus P_2 \oplus \ldots \oplus P_N = 1 \oplus 2 \oplus \ldots \oplus N = \begin{cases} N \\ N \oplus 1 \end{cases}

The exact details here do not matter, what matters here is the fact that each on bit in N must appears at least once among T_1, T_2, \ldots, T_{N/2}. Furthermore, we know that T_i \ge 1 for all i. This leads to the following greedy strategy:

• For as many i as possible, set T_i = 2^k, where k is some on bit of N (we call these values "large T")
• For the remaining elements, set T_i = 1.

For example, in the case of N = 12, the strategy listed above becomes setting T = {8, 4, 1, 1, 1, 1}

To actually create the permutation P with the desired T, we have the following observation:

• To make T_i = 1, we need P_{2i - 1} = 2x and P_{2i} = 2x + 1 for some number x \ge 1. Therefore, we can split numbers from 1 to N into \frac{N}{2} - 1 such pairs, with 1 and N being unpaired.
• To make large T values, we can go down from N, and at each point remove one bit from N and match it to an element in some pair, while taking the other element in the pair to continue making large T values. We repeat this process until we reach 1. For example, the following shows the process of making large T values for N = 12.
• Match 12 with 4 to create T_1 = 8. Since 4 is initially paired with 5, take 5 as the current number.
• Match 5 with 1 to create T_2 = 4.
We see that this process conveniently removes some pairs along with N and 1 entirely, therefore the remaining pairs are unharmed so we can match them to set T_i = 1.

A small caveat: if N has odd on bits, then we see the process ends with 0 and not 1. For example with N = 14:

• Match 14 with 6. Current number is 7.
• Match 7 with 3. Current number is 4.
• Match 4 with 0.

In this case, it is safe is replace 0 with 1 and take 1 more cost. This is because T_1 \oplus T_2 \oplus \ldots \oplus T_{N/2} forces the parity of the number of on 0-th bit in T, which means in this case we are â€śforcedâ€ť to take 1 more cost to satisfy this parity.

# TIME COMPLEXITY:

Time complexity is O(N) per test case.

# SOLUTION:

Setter's Solution
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
#define int long long
#define endl "\n"
using namespace __gnu_pbds;

typedef tree<int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int sf=2e5+10;
int M=1e9+7;
int fac[sf],invFac[sf];
int power(int a,int b){
int ans=1;
while(b>0){
if(b&1){
ans*=a;
ans%=M;
}
a*=a;
a%=M;
b/=2;
}
return ans;
}
int findInv(int a){
return power(a,M-2);
}
void preFac(){ // pre process
fac[0]=invFac[0]=1;
for(int i=1;i<sf;i++){
fac[i]=(fac[i-1]*i)%M;
invFac[i]=findInv(fac[i]);
}
}
int nCr(int n,int r){  // call only if preprocess is done
return ((fac[n]*invFac[r])%M * invFac[n-r])%M;
}
int msb(int n){ // change 63 to 31 if 32 bit integer is used and use __builtin_clz(n)
return 63 - __builtin_clzll(n);
}

//DSU
class DSU{
vector<int> childCnt,par;
public:
DSU(int n){
childCnt.resize(n+1);
par.resize(n+1);
for(int i=0;i<=n;i++){
par[i]=-1;
childCnt[i]=1;
}
}
int findPar(int u){
if(par[u]==-1){
return u;
}
return par[u]=findPar(par[u]);
}
void unite(int u,int v){
int p1=findPar(u);
int p2=findPar(v);
if(p1!=p2){
if(childCnt[p1]>childCnt[p2]){
childCnt[p1]+=childCnt[p2];
par[p2]=p1;
}else{
childCnt[p2]+=childCnt[p1];
par[p1]=p2;
}
}
}
int findSize(int u){
int p1=findPar(u);
return childCnt[p1];
}
};

// => order_of_key() postion in sorted array
// => pre-process
// => change size of array, modulus if required.
// -------------------------------------------------------------------------------------------------------------------------------------------

signed main(){
ios_base::sync_with_stdio(0) , cin.tie(0);
int t;cin>>t;
while(t--){
int n;cin>>n;
int used[n+1]{0};
vector<pair<int,int>> ans;
int cur=n;
int nxt;
while(true){
for(int i=1;i<20;i++){
if(cur&(1ll<<i)){
nxt=cur-(1ll<<i);
break;
}
}
used[cur]=true;
used[nxt]=true;
if(nxt<=1){
used[1]=true;
ans.push_back({cur,1});
break;
}

ans.push_back({cur,nxt});
if(nxt&1){
cur=nxt-1;
}else cur=nxt+1;
}
for(int i=2;i<=n;i+=2){
if(used[i])continue;
ans.push_back({i,i+1});
}
for(auto x : ans){
cout<<x.first<<" "<<x.second<<" ";
}cout<<endl;
}

return 0;
}

Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
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) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

assert(getchar()==EOF);
}
const ll mod=998244353;
const int N=1e5+1;
int n;
int lg[N];
int tot=200000;
void solve(int n){
if(n==0){
cout << '\n';
return;
}
//cout << "solve " << n << endl;
if(n==1<<lg[n]){
for(int j=2; j<=n ;j++) cout << j << ' ';
cout << "1\n";
return;
}
int m=n^(1<<lg[n]);
for(int i=m+2; i<n ;i++) cout << i << ' ';
int k=(m+1)^(1<<lg[m+1]);
cout << n << ' ' << m << ' ' << m+1 << ' ' << k << ' ';
for(int i=k+1; i<m ;i++) cout << i << ' ';
//cout << m << ' ' << k << endl;
//system("pause");
solve(k-1);
}
const int iu=1e5;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
for(int i=2; i<=iu ;i++){
lg[i]=lg[i/2]+1;
}
while(t--){
tot-=n;
assert(n%2==0);
solve(n);
}

}

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<bool> chk(n + 1);
for (int cur = n, i = 0; cur != 0; cur -= cur & -cur, i ^= 1) {
int oth = (cur - (cur & -cur)) ^ (i);
if (oth == 0) {
oth = 1;
}
chk[cur ^ i] = chk[oth] = true;
cout << (cur ^ i) << " " << oth << " ";
}
for (int i = 2; i < n; i += 2) {
if (!chk[i]) {
cout << i << " " << i + 1 << " ";
}
}
cout << '\n';
}
}

3 Likes

How to prove the greedy strategy can get a minimum \sum T ?

Set bits of N could not be neutralized through the given operation, because the total count of those set bits from 1 to N would be odd.

If we have two distinct numbers, then their xor will have at least 1 bit set. Since we cant neutralize set bits of N, we could make ceil(X/2) numbers of pairs(here X is the count of set bits in N) such that their sum is equal to N (if X is even) or N+1 ( if x is odd).

The remaining numbers could be paired in such a way that their xor would be equal to 1 ( if Y is even then (Y^(Y+1)) == 1).

2 Likes

I have watched your solution and i think that for n = 14 the best solution would be 9,1,1,1,1,1,1 i.e. 1 xor 8 and remaining could be paired to give xor equal 1 . I have tested your solution and I donâ€™t get it why to pair the last number with something other than itâ€™s previous number .I think the optimized solution would be to xor 1 with 2^x where 2^x<n<2^x+1 and rest to be paired with alternative number .

So @shshshsh it seems your suggestion would be the following pairs:
(1,8), (2,3), (4,5), (6,7), (9,10), (11,12), (13,14)
which gives XOR results of 9,1,1,1,3,7,3 for a total of 25.

However the editorial is also wrong (or at least unclear), because it leaves 2 stranded, implying a match with 5 which is not optimal. I think the best pairing for 14 is
(14,6), (7,3), (1,2), (4,5), (8,9), (10,11), (12,13) for a total of 19

I believe they just made a small error. 7 matches with 3, and the current number should be 2 (instead of 4), which gets matched with 0.