PORX - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Given N and X, find any permutation of \{1, 2, \ldots, N\} that maximizes the number of indices satisfying P_i\mid i = X.

EXPLANATION:

We’ll say an integer a is a submask of an integer b, if every bit that’s set in the binary representation of a is also set in the binary representation of b.
For example, 13 equals 1101_2 in binary, and 5 (101_2 in binary) is a submask of it while 2 (10_2 in binary) is not.

For P_i \mid i = X to hold, both P_i and i have to be submasks of X.
In particular, this means that if i is not a submask of X, it doesn’t matter what P_i equals: P_i\mid i will never equal X.

Now, consider some index i such that i is indeed a submask of X.
What should P_i be to make P_i\mid i = X?
Well, P_i should definitely contain all the bits of X that i doesn’t contain.
Observe that since i is a submask of X, these remaining bits will form exactly the value X-i.

Apart from the bits of X-i, P_i can also contain any other bits that are set in both i and X.
However, notice that adding extra bits will only increase the value of P_i, so no matter what, if we want P_i\mid i = X we must have P_i \geq X-i.
In particular, if X-i \gt N, there’s no way to give any valid P_i to index i.

So, we’re left with only a handful of candidate indices: those for which i is a submask of X and X-i \leq N.
It’s easy to see that all of these candidates can be satisfied: just give the value X-i to index i.
The one exception is if i = X, in which case we can’t use the value X - i = 0. However, in this case we can set P_i = X instead (which wouldn’t have been used anywhere else).

After satisfying all these indices, place the remaining elements in the empty spots however you like to complete the permutation.

TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n, x; cin >> n >> x;
        vector ans(n+1, 0);

        set<int> rem;
        for (int i = 1; i <= n; ++i) rem.insert(i);

		// Satisfy all candidate indices
        for (int i = 1; i <= n; ++i) {
            if (x-i <= n and x-i >= 1) ans[i] = x-i;
            if (i == x) ans[i] = x;
            rem.erase(ans[i]);
        }

		// Fill in empty spots
        for (int i = 1; i <= n; ++i) {
            if (ans[i]) continue;
            ans[i] = *begin(rem);
            rem.erase(ans[i]);
        }
        for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
        cout << '\n';
    }
}