\section{Constructing an assembly}\label{sec:construction}
The threshold theorem guarantees some target colouring, which need not be
specified in advance. It can be found by a bounded number of capacitated
matching problems, even when the side lengths are large.
Berkove, Eickemeyer and Schulman~\cite[Section 7]{BES} formulate frame
assembly as bipartite matching between individual cubes and positions.
Here we compress equal source varieties and geometric requirements into
a network of constant size.

\begin{proposition}[Compressed construction]\label{prop:construction}
Given an explicit list of $q$ sources and $a,b,c\ge2$, one can find a
frame or a complete-box assembly, or report that none exists, in $O(q)$ time.
This bound holds for every explicit input, including unsuccessful ones.
It uses the word-RAM model with the input sizes, dimensions and output
indices fitting in a word. Write $L=4(a+b+c)-16$ for the frame size.
For sources given as 75 binary multiplicities, feasibility and a compressed
assembly have polynomial bit complexity; expanding the placements costs
the output size.
\end{proposition}
\begin{proof}
Reject immediately if $q<L$, or if a complete box is requested and $q<abc$.
Use $L=8+4((a-2)+(b-2)+(c-2))$ and capped nonnegative arithmetic
for these tests, recording whether a demand exceeds $q$. Oversized demands
need not be represented in a word.
Classify each source among the 75 varieties by testing its 24 proper
rotations, recording both its variety and a rotation to the representative.
This takes $O(q)$ time and gives 75 multiplicities and lists of actual copies.

Test each target variety with each distinct assignment of the three side
lengths to its coordinate axes. There are at most six assignments, hence
at most 450 configurations. When exactly two side lengths agree, three
assignments suffice, giving 225 configurations; when all three agree,
only 75 are needed. Every physical target is a proper rotation of one
of the 75 representatives, and every proper rotation permutes the three
coordinate axes. Bringing the target to its representative therefore
permutes the side-length assignment. Sign changes only reverse positions
along an edge; they introduce no additional demand pattern. This proves
that the listed configurations cover every assembly.

For each configuration, use a flow network with 75 source-variety nodes
and at most twenty requirement nodes: eight corners of demand one and
twelve geometric edges whose demands are their assigned side lengths
minus two. Omit zero demands. Add an arc from the network source to each
variety with capacity its multiplicity, and an arc from each requirement
to the sink with capacity its demand. Connect a variety to a requirement
exactly when it fits, with capacity $q$. There are at most 97 vertices,
including source and sink. Identical requirements may be merged.

An integral flow of value $L$ saturates every requirement and gives the
number of copies of each variety to place there. Conversely, any frame
induces such a flow. A shortest-augmenting-path max-flow algorithm has a
number of arithmetic operations bounded in terms of the network size,
independently of the capacities~\cite{EdmondsKarp}. Here the network size
and the number of configurations are constants. Thus all flow tests take
$O(1)$ word operations, or polynomial time in the bit lengths for binary
input. If every test fails, no frame exists.

For binary input, retain the flow counts and the chosen rotations as the
compressed frame assembly. For a complete box, also record counts of unused
varieties and their rotations for each face-interior region and the interior;
consecutive positions in a fixed coordinate order specify their placements.

Expand a successful flow into $L$ distinct source copies and positions.
A precomputed proper rotation for each compatible corner or edge,
composed with the recorded source rotation, gives each placement's
orientation. This takes $O(L)$ time. A complete box exists exactly when a
frame exists and $q\ge abc$: fill face interiors with unused copies
rotated to expose the required single colour, and fill the interior
arbitrarily. Writing these placements takes $O(abc)$ time.
After the initial rejection test, the number of placements is at most $q$,
so both unsuccessful and successful inputs take $O(q)$ time.
\end{proof}