0745HardArrayMathDynamic ProgrammingBacktrackingBit ManipulationNumber TheoryBitmask

Retiring Blades In Paired Sessions

Tracked in this browser only

Trains the technique from

LeetCode 1799Maximize Score After N Operations

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 workshop is retiring its cutting blades. There are 2 * n blades in service and values[i] is the tooth count of blade i.

The retirement happens over n sessions, numbered 1, 2, up to n. In session s the workshop picks any two blades that are still in service, takes them out of service, and banks s * g credits, where g is the greatest common divisor of the two tooth counts. After session n no blade remains in service.

The workshop chooses which two blades to retire in each session, and the session number multiplies whatever that session earns. Return the largest total credit the workshop can bank.

Examples

Example 1

Input: values = [30, 12, 25, 4]
Output: 14

Retire blades 12 and 4 in session 1, whose greatest common divisor is 4, banking 1 * 4 = 4. Retire blades 30 and 25 in session 2, whose greatest common divisor is 5, banking 2 * 5 = 10. The total is 14.

Example 2

Input: values = [9, 12, 18, 4, 6, 8]
Output: 43

Session 1 retires 4 and 8 for 1 * 4 = 4, session 2 retires 12 and 6 for 2 * 6 = 12, and session 3 retires 9 and 18 for 3 * 9 = 27, totalling 43.

Example 3

Input: values = [8, 8, 8, 8]
Output: 24

Every pair of these blades has greatest common divisor 8, so session 1 banks 1 * 8 and session 2 banks 2 * 8, for 24 in total.

Constraints

2 <= values.length <= 14
values.length is even, and equals 2 * n for the number of sessions n.
1 <= values[i] <= 10^6
The largest total credit these bounds allow is 28 * 10^6.

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 best_retirement_credit(values: list[int]) -> int:

Java

public int bestRetirementCredit(int[] values)

The intended approach

Time O(2^m * m^2) for m = values.length, plus O(m^2 log V) to build the divisor table.Space O(2^m) for the mask table and O(m^2) for the divisor table.

The only thing that matters about the past is which blades are gone, and how many are gone already fixes which session is next, so index the search by a bitmask of retired blades. Precompute the greatest common divisor of every pair of tooth counts once. Sweep the masks in increasing numeric order, which visits a mask only after every mask reachable before it, and from a mask with an even population try each pair of blades still in service as the pair for session `population / 2 + 1`, keeping the best credit recorded for the resulting mask. Every pair has to be offered at each step: restricting the choice, for instance by always retiring the lowest-numbered surviving blade, would rule out orderings that pay more. The answer is the value recorded for the full mask.

Pythonentry point: best_retirement_credit

from math import gcd


def best_retirement_credit(values):
    # State is the set of blades already retired; its size fixes which session
    # comes next, so every pair of still-serving blades is tried as that
    # session's pair. O(2^m * m^2) time, O(2^m) space for m = len(values).
    m = len(values)
    full = 1 << m
    table = [[0] * m for _ in range(m)]
    for i in range(m):
        for j in range(i + 1, m):
            table[i][j] = gcd(values[i], values[j])

    best = [-1] * full
    best[0] = 0
    for mask in range(full):
        if best[mask] < 0:
            continue
        retired = bin(mask).count("1")
        if retired % 2:
            continue
        session = retired // 2 + 1
        for i in range(m):
            if mask >> i & 1:
                continue
            for j in range(i + 1, m):
                if mask >> j & 1:
                    continue
                nxt = mask | 1 << i | 1 << j
                gain = best[mask] + session * table[i][j]
                if gain > best[nxt]:
                    best[nxt] = gain
    return best[full - 1]

The obvious version

Recursively split the blades into unordered pairs in every possible way. For a given split, spread its divisor values across the sessions from smallest to largest and total the weighted credit, then keep the best total over all splits.

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

from math import gcd


def bf_best_retirement_credit(values):
    """Enumerate every way of splitting the blades into pairs. For one such
    split, order its divisor values from small to large across the sessions and
    total the credit; keep the largest total over all splits."""
    m = len(values)
    best = [0]

    def walk(remaining, divisors):
        if not remaining:
            ordered = sorted(divisors)
            total = 0
            for k, g in enumerate(ordered):
                total += (k + 1) * g
            if total > best[0]:
                best[0] = total
            return
        first = remaining[0]
        rest = remaining[1:]
        for pos in range(len(rest)):
            partner = rest[pos]
            walk(rest[:pos] + rest[pos + 1:],
                 divisors + [gcd(values[first], values[partner])])

    walk(list(range(m)), [])
    return best[0]

How this problem was checked

Reference solution executed against 14 test cases — 14 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