0313MediumArrayDynamic ProgrammingBacktrackingBit ManipulationBitmask

Divisible Crate Placements

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A stockroom has size shelves, numbered 1 through size, and size crates, also numbered 1 through size. Exactly one crate goes on each shelf.

A crate is allowed on a shelf only when the two numbers divide one another: the crate number is a multiple of the shelf number, or the shelf number is a multiple of the crate number. Either direction is fine.

Return how many different complete placements satisfy that rule. Two placements differ when some shelf holds a different crate.

Examples

Example 1

Input: size = 3
Output: 3

Writing a placement as the crate on shelf 1, shelf 2, shelf 3, the allowed placements are (1, 2, 3), (2, 1, 3) and (3, 2, 1). Shelf 1 accepts any crate, and shelf 3 accepts only crate 1 or crate 3.

Example 2

Input: size = 4
Output: 8

Eight complete placements obey the rule, one of them being (2, 4, 3, 1): crate 2 on shelf 1, crate 4 on shelf 2, crate 3 on shelf 3 and crate 1 on shelf 4.

Example 3

Input: size = 5
Output: 10

Ten placements obey the rule. Crate 5 can only sit on shelf 1 or shelf 5, and crate 3 can only sit on shelf 1 or shelf 3.

Example 4

Input: size = 6
Output: 36

Thirty-six placements obey the rule, for instance (6, 2, 3, 4, 5, 1) and (1, 6, 3, 4, 5, 2).

Constraints

1 <= size <= 15

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def count_placements(size: int) -> int:

Java

public int countPlacements(int size)

The intended approach

Time O(2^n * n)Space O(2^n)

Fill the shelves in order 1, 2, 3, ... and note that which shelf comes next is determined by how many crates have already been used, so the only state worth keeping is the set of used crates. Index an array by that set as a bitmask, holding how many ways it can arise, and extend each set with every unused crate that is compatible with the next shelf. The entry for the full set is the answer.

Pythonentry point: count_placements

def count_placements(size):
    # Subset dynamic programming, iterative, no recursion at all.
    # O(2^n * n) time and O(2^n) space, which is fine because n is at most 15.
    span = 1 << size
    ways = [0] * span
    ways[0] = 1
    for mask in range(span):
        if ways[mask] == 0:
            continue
        shelf = bin(mask).count("1") + 1
        if shelf > size:
            continue
        for crate in range(1, size + 1):
            bit = 1 << (crate - 1)
            if mask & bit:
                continue
            if crate % shelf == 0 or shelf % crate == 0:
                ways[mask | bit] += ways[mask]
    return ways[span - 1]

The obvious version

Walk the shelves one at a time and try every unused crate that fits, undoing each choice afterwards, counting one for each shelf run that reaches the end.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_count_placements(size):
    used = [False] * (size + 2)

    def walk(shelf):
        if shelf > size:
            return 1
        total = 0
        for crate in range(1, size + 1):
            if used[crate]:
                continue
            if crate % shelf == 0 or shelf % crate == 0:
                used[crate] = True
                total += walk(shelf + 1)
                used[crate] = False
        return total

    return walk(1)

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in