0488HardArrayDynamic ProgrammingSorting

Fabric Bolt Cutting Charges

Tracked in this browser only

Trains the technique from

LeetCode 1547Minimum Cost to Cut a Stick

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 mill receives a bolt of cloth length centimetres long and has to divide it at every mark in marks. A mark is written as its distance in centimetres from the left end of the bolt, so every mark sits strictly inside the cloth.

Cutting is done one pass at a time. A pass takes a single piece of cloth, feeds it through the blade at one of the marks still lying inside that piece, and hands back the two pieces either side of it. The mill bills a pass at the width of the piece that went in, no matter where within it the mark sat, and the bill for the job is the sum over all passes.

The passes may be made in any order you like, and the order matters, because a piece already divided is narrower for later passes.

Return the smallest total bill for dividing the bolt at every mark.

Examples

Example 1

Input: length = 7, marks = [5, 1, 4, 3]
Output: 16

Passing at 3 bills 7 and leaves pieces 0-3 and 3-7; passing at 1 bills 3, at 5 bills 4, and at 4 bills 2, for 7 + 3 + 4 + 2 = 16.

Example 2

Input: length = 12, marks = [8]
Output: 12

There is a single mark and a single pass, and the piece fed in is the whole bolt.

Example 3

Input: length = 20, marks = [2, 19]
Output: 38

Passing at 2 bills 20 and passing at 19 then bills 18, for a total of 38.

Constraints

2 <= length <= 10^6
1 <= marks.length <= min(length - 1, 100)
1 <= marks[i] <= length - 1
All values in marks are distinct.

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 min_cutting_charge(length: int, marks: list[int]) -> int:

Java

public int minCuttingCharge(int length, int[] marks)

The intended approach

Time O(m^3)Space O(m^2)

Sort the marks and add `0` and `length` as bracketing points, so every piece that can ever exist is a pair of bracketing points with the marks between them still to be cut. For such a piece, whichever inner mark is fed first bills the piece's full width and leaves two independent sub-pieces, so the cheapest bill for the piece is its width plus the best split over the inner marks. Fill that table by increasing span.

Pythonentry point: min_cutting_charge

def min_cutting_charge(length, marks):
    # Order the marks and bracket them with the two ends of the bolt. A piece is
    # then any pair of bracket points, and whichever mark inside it is fed to the
    # blade first splits it into two smaller pieces that are handled the same way.
    # The charge for that first pass is the piece's whole width, whatever the mark.
    # time O(m^3) over the m marks, space O(m^2)
    points = [0] + sorted(marks) + [length]
    total = len(points)
    dp = [[0] * total for _ in range(total)]
    for span in range(2, total):
        for lo in range(0, total - span):
            hi = lo + span
            best = None
            for mid in range(lo + 1, hi):
                inner = dp[lo][mid] + dp[mid][hi]
                if best is None or inner < best:
                    best = inner
            dp[lo][hi] = best + points[hi] - points[lo]
    return dp[0][total - 1]

The obvious version

Walk every ordering of the marks. For an ordering, hold the current piece edges in a sorted list, and for each mark in turn locate the piece it falls inside, add that piece's width to the bill and insert the mark as a new edge. Keep the smallest bill.

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_min_cutting_charge(length, marks):
    from itertools import permutations
    best = None
    for order in permutations(marks):
        edges = [0, length]
        total = 0
        for mark in order:
            for t in range(len(edges) - 1):
                if edges[t] < mark < edges[t + 1]:
                    total += edges[t + 1] - edges[t]
                    edges.insert(t + 1, mark)
                    break
        if best is None or total < best:
            best = total
    return best

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 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