Mechanical Doll
Build a switching network of binary switches (Y-shaped connectors called ``switches'') to route a ball through a sequence of triggers A_1, A_2,, A_m in order. Each switch has two outputs (X and Y) and alternates betwe...
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
Build a switching network of binary switches (Y-shaped connectors called ``switches'') to route a ball through a sequence of triggers $A_1, A_2, \ldots, A_m$ in order. Each switch has two outputs ($X$ and $Y$) and alternates between them each time the ball passes. All triggers route back to the root switch. Minimize the number of switches.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Key Idea: Complete Binary Tree
A complete binary tree with $2^k \ge m$ leaves can sequence $m$ triggers. Each traversal from root to leaf visits a unique leaf due to alternating switches. The $2^k$ leaves are visited in bit-reversal order: the $i$-th traversal (0-indexed) reaches leaf $\text{bitrev}(i, k)$.
Construction
Find the smallest $k$ with $2^k \ge m$. Set $L = 2^k$.
The first $L - m$ visits hit dummy leaves (routed back to the root switch). The remaining $m$ visits hit $A_1, \ldots, A_m$ in order.
For leaf at tree position $p$ (0-indexed): it is visited at time $t = \text{bitrev}(p, k)$. If $t < L - m$, the leaf is dummy (output $= -1$, i.e., root switch). Otherwise, the leaf outputs trigger $A_{t - (L-m)+1}$.
Build the tree bottom-up. If both children of an internal node are dummy, eliminate that node (replace with $-1$). This reduces the switch count.
Assign switch numbers so the root is switch $-1$ (as required by the grader), with switches numbered $-1, -2, \ldots$
Lemma.
A complete binary tree of depth $k$ with alternating switches visits its $2^k$ leaves in bit-reversal order.
Proof.
At depth $d$, a switch sends the ball left on odd passes and right on even passes (or vice versa, depending on initial state). The $i$-th traversal follows the path determined by the bits of $i$ read in reverse, landing at leaf $\text{bitrev}(i, k)$.
Optimization
Eliminating switches where both children are dummy can reduce the count from $2^k - 1$ to as few as $m - 1$ for favorable $m$.
Complexity Analysis
Switches: At most $2m - 1$ (since $2^k < 2m$). With dummy elimination, often fewer.
Time: $O(m)$.
Space: $O(m)$.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
// Grader-provided function
void answer(vector<int> C, vector<int> X, vector<int> Y);
static vector<int> Xv, Yv;
static const int DUMMY = INT_MIN;
static int newSwitch(int x, int y) {
Xv.push_back(x);
Yv.push_back(y);
return -(int)Xv.size();
}
// Build binary switch tree for leafOut[lo..hi-1].
// Returns DUMMY if entire subtree is dummies, else a switch ID or trigger number.
static int buildTree(int lo, int hi, const vector<int>& leafOut) {
if (hi - lo == 1) return leafOut[lo];
int mid = (lo + hi) / 2;
int left = buildTree(lo, mid, leafOut);
int right = buildTree(mid, hi, leafOut);
if (left == DUMMY && right == DUMMY) return DUMMY;
return newSwitch(left, right);
}
void create_circuit(int M, vector<int> A) {
int N = A.size();
// Need leaves for A[0..N-1] plus halt (output 0) = N+1 real visits.
// Pad to next power of 2 with dummy visits that loop back to root.
int need = N + 1;
int k = 0;
while ((1 << k) < need) k++;
int leaves = 1 << k;
int numDummy = leaves - need;
// visitOutput[i] = output of the i-th chronological leaf visit
vector<int> visitOutput(leaves);
for (int i = 0; i < numDummy; i++) visitOutput[i] = DUMMY;
for (int i = 0; i < N; i++) visitOutput[numDummy + i] = A[i];
visitOutput[leaves - 1] = 0; // halt
// Leaf at tree position p is visited at time bitReverse(p, k).
// So leafOutput[p] = visitOutput[bitReverse(p, k)].
auto bitReverse = [](int x, int bits) -> int {
int r = 0;
for (int i = 0; i < bits; i++) { r = (r << 1) | (x & 1); x >>= 1; }
return r;
};
vector<int> leafOutput(leaves);
for (int p = 0; p < leaves; p++)
leafOutput[p] = visitOutput[bitReverse(p, k)];
// Build tree, then replace DUMMY references with root switch
Xv.clear(); Yv.clear();
int root = buildTree(0, leaves, leafOutput);
int S = (int)Xv.size();
for (int i = 0; i < S; i++) {
if (Xv[i] == DUMMY) Xv[i] = root;
if (Yv[i] == DUMMY) Yv[i] = root;
}
// Renumber so root switch becomes -1 (index 0 in arrays).
// Currently root = -S. Remap: -i -> -(S - i + 1).
auto remap = [&](int x) -> int {
if (x <= -1 && x >= -S) return -(S - (-x) + 1);
return x;
};
for (int i = 0; i < S; i++) {
Xv[i] = remap(Xv[i]);
Yv[i] = remap(Yv[i]);
}
reverse(Xv.begin(), Xv.end());
reverse(Yv.begin(), Yv.end());
// C[0] = -1 (root switch); C[i] = -1 for all triggers (return to root)
vector<int> C(M + 1, -1);
answer(C, Xv, Yv);
}
// --- Local testing stub (remove for grader submission) ---
#ifdef LOCAL_TEST
void answer(vector<int> C, vector<int> X, vector<int> Y) {
int S = X.size();
vector<int> state(S, 0);
vector<int> visited;
int cur = C[0], steps = 0;
while (cur != 0 && steps < 100000) {
steps++;
if (cur > 0) { visited.push_back(cur); cur = C[cur]; }
else {
int idx = -cur - 1;
cur = state[idx] == 0 ? X[idx] : Y[idx];
state[idx] ^= 1;
}
}
printf("Visited:");
for (int x : visited) printf(" %d", x);
printf("\nS = %d, halt = %s, reset = %s\n", S,
cur == 0 ? "OK" : "FAIL",
all_of(state.begin(), state.end(), [](int s){return s==0;}) ? "OK" : "FAIL");
}
int main() {
int M, N; scanf("%d %d", &M, &N);
vector<int> A(N);
for (int i = 0; i < N; i++) scanf("%d", &A[i]);
create_circuit(M, A);
}
#endif
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.