PERMXOR - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

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

DIFFICULTY:

Medium

PREREQUISITES:

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) {
    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);
}
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;
	}
	int t;t=readInt(1,1000,'\n');
	while(t--){
		n=readInt(1,min(100000,tot),'\n');
		tot-=n;
		assert(n%2==0);
		solve(n);
	}
	readEOF();
	
}
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.