Goal
Consider a permutation of a binary string of a given length N, that produces an output binary string of the same length, such that each bit of the output is equal to some bit of the input. The position of the input bit may not be the same as the position of the corresponding output bit, but all output bits are mapped from different input bits.An example permutation is one that rearranges bits as follows:
b2 b1 b0 → b1 b0 b2
The result of the permutation (on different inputs) is:
binary 001 → 010 yields as integer 1 → 2
binary 011 → 110 yields as integer 3 → 6
binary 101 → 011 yields as integer 5 → 3
For one such permutation, your program will receive a number of clues about the permutation in the following form:
Xi Yi
where Xi and Yi are base 10 numbers and Yi is the result of the permutation on Xi.
From the clues you must deduce the permutation and apply it to all values with a single '1' in their binary representation, that is: 1, 2, 4, 8 ... 2^(N-1).
Next C Lines: Two integers Xi and Yi, where Yi is the result of the permutation on Xi
1 ⩽ C ⩽ N
Solution
The medium problem has the perfect size to analyze the problem. We get two four-bit samples, which read in decimal that 3 → 6 and 6 → 12. When we draw a graph to see where bits from the left number can go to the right, we see the following picture:
When we intersect both graphs the following picture arises:
And this it is. The problem is well formulated that we find the permutations by building the intersection of all clue-graphs and don't have to guess anything. I decided to represent the clue-graphs as \(n\) bitsets - meaning for each binary digit of the left number, a bitset is saved in an \(n\)-dimensional array. To construct a a graph of possible ways from left to right this algorithm is sufficient:
function getGraph(Xi, Yi, n) {
var graph = new Array(n).fill(0);
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
if ((Xi >> i & 1) === (Yi >> j & 1))
graph[i]|= 1 << j;
}
}
return graph;
} which can be simplified (obfuscated) a bit to avoid the branching:
function getGraph(Xi, Yi, n) {
var graph = new Array(n).fill(0);
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
graph[i]|= (~((Xi >> i) ^ (Yi >> j)) & 1) << j;
}
}
return graph;
} Now given this algorithm, the intersection can be made with a binary and operation. This means the following is sufficient to complete this problem:
var inputs = readline().split(' ');
var N = +inputs[0];
var C = +inputs[1];
var G = null;
for (var i = 0; i < C; i++) {
var inputs = readline().split(' ').map(Number);
var tmp = getGraph(inputs[0], inputs[1], N);
if (G === null) G = tmp;
else {
for (var j = 0; j < N; j++) {
G[j]&= tmp[j];
}
}
}
print(G.join(" "));