Teeth on the wheels

A padlock is a stack of dial wheels, and the workshop has a fixed number of notches to cut across them. How the notches are shared decides how many codes the lock has.

The problem

A combination padlock is built from a stack of wheels. Each wheel is cut with a whole number of notches, at least one, and turning the stack to any choice of notch on each wheel gives one code — so the number of distinct codes is the product of the wheel counts.

The workshop's cutter is set for notches cuts in total, and every cut must be used. A lock needs at least two wheels to be a combination lock at all. Choose how to split the notches across the stack so the number of codes is as large as possible, and report that number.

Input. notches — an integer, the total notches to cut, at least 2.

Output. The largest product obtainable by writing notches as a sum of two or more positive integers.

Example.

notches = 10   ->  36

Ten notches as 3 + 3 + 4 gives 36 codes. Five wheels of 2 give 32, two wheels of 5 give 25, and 1 + 9 gives 9 — a one-notch wheel never has anything to say.

A second example, where the answer is smaller than the input:

notches = 3   ->  2

Three notches must be split, so the best is 1 + 2 and the lock has 2 codes, fewer than the 3 a single uncut wheel would have offered. The two-wheel rule bites at the bottom of the range.

Constraints.

• 2 <= notches <= 200

Hints

Approach

Brute force

Enumerate every way to write notches as an ordered sum of positive parts and multiply each out. The number of compositions of n is 2ⁿ⁻¹ — over 10⁵⁹ at n = 200, and most of them repeat the same tail split thousands of times.

The insight

Fix the first wheel at j notches, and the rest is the same question about n - j — with one twist: the remainder may be left whole, so the recurrence takes max(n - j, best[n - j]).

That twist is the whole problem. best[m] is defined as the best product with at least two wheels, so it refuses to report m itself; but once the first wheel exists, leaving the remainder as a single wheel is legal. Taking the max of the two covers both, and every subproblem is strictly smaller, so a table filled upward reads only finished entries.

Algorithm

1. Make a table best of size notches + 1, with best[1] = 1.
2. For total from 2 up to notches, and each first wheel j from 1 to total - 1:
3. Score the split as j * max(total - j, best[total - j]).
4. Keep the largest score as best[total].
5. Return best[notches].

Complexity

Time O(n²) — one inner scan per table entry, 20000 steps at n = 200. Space O(n) for the table.

Solution

"""Teeth on the wheels — one-dimensional DP over the notches left to split."""


def solve(notches):
    # best[m] = largest product from splitting m into TWO OR MORE wheels.
    # best[1] = 1 is the harmless convention: a leftover 1 contributes a factor 1.
    best = [0] * (notches + 1)
    best[1] = 1
    for total in range(2, notches + 1):
        for first in range(1, total):
            rest = total - first
            # The remainder may stay one wheel, or be split again — take the better.
            best[total] = max(best[total], first * max(rest, best[rest]))
    return best[notches]

TESTS = [
    ((10,), 36),
    ((3,), 2),
    ((2,), 1),
    ((4,), 4),
    ((11,), 54),
    ((20,), 1458),
    ((200,), 2 * 3 ** 66),
]

Pitfalls

• Writing the recurrence as j * best[total - j]. It forces the remainder to be split again, so notches = 4 reports 2 * best[2] = 2 instead of 4. The remainder must be allowed to stay whole.
• Seeding best[n] = n. That lets the answer be one uncut wheel, and notches = 3 comes back as 3 — a lock with one wheel, which the brief forbids. Every entry must already assume the split has happened.
• Stopping the inner scan at total // 2 without keeping the max. The split is symmetric only if both halves are scored the same way; drop the max(total - j, best[total - j]) and the shortcut hides the real best.

Variants

• Wax pours — also splits a total into parts, but the parts are handed to you and must come out equal.
• Linear DP — where the "read only entries below you" table order comes from.