Problem 126: Cuboid Layers

Mathematical Development

Theorem 1 (Layer formula). For a cuboid with dimensions $a \times b \times c$ ($a \leq b \leq c$), the number of cubes in the $k$-th layer ($k \geq 1$) is

Proof. The total volume enclosed by $k$ layers around an $a \times b \times c$ cuboid (including the cuboid itself) is

where the subtraction accounts for the hollow interior. The number of cubes in layer $k$ alone is

Expanding:

Let $u = 2k$. Then $V(k) - V(k-1)$ equals:

Expanding both products and subtracting, collecting terms in powers of $u = 2k$:

Verification: For $k = 1$: $f = 2(ab + bc + ac)$, which is the surface area of the cuboid. For $(a,b,c,k) = (3,2,1,1)$: $f = 2(6+2+3) = 22$. For $k = 2$: $f = 22 + 4(6)(1) + 0 = 46$. Both match the problem statement. $\square$

Lemma 1 (Monotonicity in $k$). For fixed $(a, b, c)$, $f(a, b, c, k)$ is strictly increasing in $k$.

Proof. $f(a,b,c,k+1) - f(a,b,c,k) = 4(a+b+c) + 4(2k-1) > 0$ for all $k \geq 1$ and positive dimensions. $\square$

Lemma 2 (Enumeration bounds). To find all $(a, b, c, k)$ with $f(a, b, c, k) \leq N$:

• $a$: from $1$ while $2a^2 \leq N$ (minimum layer for cube $a \times a \times a$).
• $b$: from $a$ while $2(ab + b^2) \leq N$.
• $c$: from $b$ while $2(ab + bc + ac) \leq N$ (the $k=1$ value).
• $k$: from $1$ while $f(a,b,c,k) \leq N$.

Proof. For $k = 1$ with $a = b = c$: $f = 6a^2$, so $6a^2 \leq N$ gives $a \leq \sqrt{N/6}$, which is weaker than $2a^2 \leq N$ (obtained from $f \geq 2(a^2 + a \cdot b + ...) \geq 2a^2$ with $b = c = a$). The other bounds follow from $f \geq 2(ab + bc + ac)$ (the $k=1$ minimum). $\square$

Editorial

Once the closed formula for the $k$-th layer is available, the problem becomes a counting task: how many tuples $(a,b,c,k)$ produce each layer size $n$? Because the layer size is monotone in every parameter, the search can be bounded very tightly. The constraints $a \le b \le c$ avoid duplicate cuboids, and for each fixed cuboid the layer index is increased only until the formula exceeds the global limit.

The implementation maintains a frequency array $C[n]$ telling how many cuboids realize a layer of size $n$. It enumerates every feasible ordered cuboid, walks through its successive layers, increments the corresponding counts, and finally scans upward for the first value where the count reaches 1000.

Pseudocode

Choose a search limit large enough to contain the first answer.
Initialize a counting array C over all layer sizes up to that limit.

Enumerate side lengths a, b, c with a <= b <= c, stopping each loop as soon as the first layer is already too large.
For each cuboid:
    Increase the layer index k from 1 upward.
    Evaluate the layer-size formula.
    If the value exceeds the search limit, stop increasing k for this cuboid.
    Otherwise increment C at that layer size.

Scan the counting array from small to large and return the first n with C(n) = 1000.

Complexity Analysis

• Time: The four nested loops enumerate all tuples $(a, b, c, k)$ with $f \leq N$. The number of such tuples is $O(N \log N)$ empirically. Total: $O(N \log N)$.
• Space: $O(N)$ for the counting array $C$.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    const int LIMIT = 20000;
    vector<int> C(LIMIT + 1, 0);

    // f(a,b,c,k) = 2(ab+bc+ac) + 4(a+b+c)(k-1) + 4(k-1)(k-2)
    for (int a = 1; 2LL * a * a <= LIMIT; a++) {
        for (int b = a; 2LL * (a * b + b * b) <= LIMIT; b++) {
            for (int c = b; 2LL * ((long long)a * b + (long long)b * c + (long long)a * c) <= LIMIT; c++) {
                long long base = 2LL * (a * b + b * c + a * c);
                long long edge = 4LL * (a + b + c);
                for (int k = 1; ; k++) {
                    long long val = base + edge * (k - 1) + 4LL * (k - 1) * (k - 2);
                    if (val > LIMIT) break;
                    C[(int)val]++;
                }
            }
        }
    }

    for (int n = 1; n <= LIMIT; n++) {
        if (C[n] == 1000) {
            cout << n << endl;
            return 0;
        }
    }

    return 0;
}

"""
Problem 126: Cuboid Layers

Find the least n for which C(n) = 1000, where C(n) counts
the number of cuboids that have exactly n cubes in one of its layers.

Layer formula: f(a,b,c,k) = 2(ab+bc+ac) + 4(a+b+c)(k-1) + 4(k-1)(k-2)
"""

def solve(target=1000):
    LIMIT = 20000
    C = [0] * (LIMIT + 1)

    a = 1
    while 2 * a * a <= LIMIT:
        b = a
        while 2 * (a * b + b * b) <= LIMIT:
            c = b
            while 2 * (a * b + b * c + a * c) <= LIMIT:
                base = 2 * (a * b + b * c + a * c)
                edge = 4 * (a + b + c)
                k = 1
                while True:
                    val = base + edge * (k - 1) + 4 * (k - 1) * (k - 2)
                    if val > LIMIT:
                        break
                    C[val] += 1
                    k += 1
                c += 1
            b += 1
        a += 1

    for n in range(1, LIMIT + 1):
        if C[n] == target:
            return n
    return -1

def visualize():
    """Optional visualization of C(n) distribution."""


if __name__ == "__main__":
    answer = solve()
    assert answer == 18522
    print(answer)