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';
}
}