Messy
Given n (a power of 2), determine an unknown permutation P of \ 0, 1,, n-1\ in two phases: Phase 1 (Add): Insert binary strings of length n into a set S. Shuffle: P is applied to every string in S (bit i moves to posi...
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
Given $n$ (a power of 2), determine an unknown permutation $P$ of $\{0, 1, \ldots, n-1\}$ in two phases:
Phase 1 (Add): Insert binary strings of length $n$ into a set $S$.
Shuffle: $P$ is applied to every string in $S$ (bit $i$ moves to position $P(i)$).
Phase 2 (Check): Query whether a binary string belongs to the shuffled set.
Both phases allow at most $O(n \log n)$ operations.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Use divide and conquer on bit positions.
Phase 1: Adding Strings
For D&C on range $[l, r)$ with a ``context'' set $C$ (bit positions outside $[l, r)$ that are always set to 1):
Let $\text{mid} = (l + r) / 2$.
For each $i \in [l, \text{mid})$: add a string with bit $i$ set to 1 and all bits in $C$ set to 1 (all others 0).
Recurse on $[l, \text{mid})$ with $C' = C \cup [\text{mid}, r)$, and on $[\text{mid}, r)$ with $C' = C \cup [l, \text{mid})$.
Each level adds $n/2$ strings across all recursive calls, totalling $O(n \log n)$ strings over $\log n$ levels.
Phase 2: Checking Membership
After the shuffle, for D&C on range $[l, r)$ with a known set of candidate output positions and shuffled context bits:
For each candidate position $p$, check the string with bit $p$ and context bits set. If present, $p$ maps to the left half $[l, \text{mid})$; otherwise, to the right half.
Recurse, using the classified positions as context for sub-problems.
Each level performs $n$ checks, totalling $O(n \log n)$.
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
// Grader: void add_element(string), bool check_element(string),
// void compile_set(), void answer(int[])
int n;
int P[1024];
void addStrings(int l, int r, vector<int> &ctx) {
if (r - l <= 1) return;
int mid = (l + r) / 2;
for (int i = l; i < mid; i++) {
string s(n, '0');
s[i] = '1';
for (int c : ctx) s[c] = '1';
add_element(s);
}
vector<int> leftCtx = ctx;
for (int i = mid; i < r; i++) leftCtx.push_back(i);
addStrings(l, mid, leftCtx);
vector<int> rightCtx = ctx;
for (int i = l; i < mid; i++) rightCtx.push_back(i);
addStrings(mid, r, rightCtx);
}
void findPerm(int l, int r, vector<int> &positions, vector<int> &ctx) {
if (r - l == 1) { P[l] = positions[0]; return; }
int mid = (l + r) / 2;
vector<int> leftPos, rightPos;
for (int p : positions) {
string s(n, '0');
s[p] = '1';
for (int c : ctx) s[c] = '1';
if (check_element(s)) leftPos.push_back(p);
else rightPos.push_back(p);
}
vector<int> leftCtx = ctx;
for (int p : rightPos) leftCtx.push_back(p);
findPerm(l, mid, leftPos, leftCtx);
vector<int> rightCtx = ctx;
for (int p : leftPos) rightCtx.push_back(p);
findPerm(mid, r, rightPos, rightCtx);
}
void restore_permutation(int N, int w, int r) {
n = N;
vector<int> emptyCtx;
addStrings(0, n, emptyCtx);
compile_set();
vector<int> allPos(n);
iota(allPos.begin(), allPos.end(), 0);
vector<int> emptyCtx2;
findPerm(0, n, allPos, emptyCtx2);
answer(P);
}Complexity Analysis
Add operations: $O(n \log n)$.
Check operations: $O(n \log n)$.
Time: $O(n^2 \log n)$ total work (each string operation touches $O(n)$ bits).
Space: $O(n \log n)$ for the set of strings.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
// Grader functions:
void add_element(string x);
bool check_element(string x);
void compile_set(); // called between phase 1 and phase 2
void answer(int P[]);
int n;
int P[1024]; // the permutation we're trying to find
void addStrings(int l, int r, vector<int> &context) {
if (r - l <= 1) return;
int mid = (l + r) / 2;
// For each i in [l, mid), add string with bit i = 1 and context bits = 1
for (int i = l; i < mid; i++) {
string s(n, '0');
s[i] = '1';
for (int c : context) s[c] = '1';
add_element(s);
}
// Recurse: left half with context += [mid, r)
vector<int> leftCtx = context;
for (int i = mid; i < r; i++) leftCtx.push_back(i);
addStrings(l, mid, leftCtx);
// Right half with context += [l, mid)
vector<int> rightCtx = context;
for (int i = l; i < mid; i++) rightCtx.push_back(i);
addStrings(mid, r, rightCtx);
}
void findPerm(int l, int r, vector<int> &positions, vector<int> &context) {
if (r - l == 1) {
P[l] = positions[0];
return;
}
int mid = (l + r) / 2;
// Determine which positions in 'positions' correspond to [l, mid)
vector<int> leftPos, rightPos;
for (int p : positions) {
string s(n, '0');
s[p] = '1';
for (int c : context) s[c] = '1';
if (check_element(s)) {
leftPos.push_back(p);
} else {
rightPos.push_back(p);
}
}
// Recurse
vector<int> leftCtx = context;
for (int p : rightPos) leftCtx.push_back(p);
findPerm(l, mid, leftPos, leftCtx);
vector<int> rightCtx = context;
for (int p : leftPos) rightCtx.push_back(p);
findPerm(mid, r, rightPos, rightCtx);
}
void restore_permutation(int N, int w, int r) {
n = N;
// Phase 1: add strings
vector<int> emptyCtx;
addStrings(0, n, emptyCtx);
// Shuffle happens here
compile_set();
// Phase 2: determine permutation
vector<int> allPos(n);
iota(allPos.begin(), allPos.end(), 0);
vector<int> emptyCtx2;
findPerm(0, n, allPos, emptyCtx2);
// P[i] = position where original bit i ends up
// Actually P[i] gives us: original position i maps to output position P[i]
// We need to invert: answer[P[i]] = i (or however the grader expects it)
answer(P);
}
int main() {
int N, w, r;
scanf("%d %d %d", &N, &w, &r);
restore_permutation(N, w, r);
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.