Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Hardbitmask-dp

Maximize Score After N Operations

Problem (restated)

nums has length 2n (n ≤ 7). In operation k (1-indexed) pick two remaining numbers x,y and score k * gcd(x,y). Maximize the total after n operations.

Intuition

n is tiny, so the used-set of numbers is a bitmask. The operation index is determined by how many numbers are already used: popcount(mask)/2 + 1.

Approaches

Pair bitmask DP

Unverified

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

Idea. dp[mask] = max score using the numbers in mask. Even popcount only. Try every unused pair (i,j), add op * gcd. Precompute the gcd table.

Walkthrough. [1,2] → 1. [3,4,6,8] → 11 (gcd(3,6) then gcd(4,8)). [1,2,3,4,5,6] → 14 (save the large gcd for the last op).

Trade-offs. Pair enumeration inside 2^n is n^2; n=14 bits is ~3e6. Do not assign op from an independent counter — it is a function of the mask.

Solution

function gcd(a: number, b: number): number {
  while (b) {
    const t = a % b;
    a = b;
    b = t;
  }
  return a;
}

export function maxScore(nums: number[]): number {
  const n = nums.length;
  const g: number[][] = Array.from({ length: n }, () => new Array<number>(n).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const d = gcd(nums[i]!, nums[j]!);
      g[i]![j] = d;
      g[j]![i] = d;
    }
  }
  const N = 1 << n;
  const dp = new Array<number>(N).fill(0);
  for (let mask = 0; mask < N; mask++) {
    let bits = 0;
    for (let t = mask; t; t &= t - 1) bits++;
    if (bits % 2) continue;
    const op = (bits >> 1) + 1;
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) continue;
      for (let j = i + 1; j < n; j++) {
        if (mask & (1 << j)) continue;
        const nmask = mask | (1 << i) | (1 << j);
        const cand = dp[mask]! + op * g[i]![j]!;
        if (cand > dp[nmask]!) dp[nmask] = cand;
      }
    }
  }
  return dp[N - 1]!;
}

function gcd(a: number, b: number): number {
  while (b) {
    const t = a % b;
    a = b;
    b = t;
  }
  return a;
}

export function maxScore(nums: number[]): number {
  const n = nums.length;
  const g: number[][] = Array.from({ length: n }, () => new Array<number>(n).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const d = gcd(nums[i]!, nums[j]!);
      g[i]![j] = d;
      g[j]![i] = d;
    }
  }
  const N = 1 << n;
  const dp = new Array<number>(N).fill(0);
  for (let mask = 0; mask < N; mask++) {
    let bits = 0;
    for (let t = mask; t; t &= t - 1) bits++;
    if (bits % 2) continue;
    const op = (bits >> 1) + 1;
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) continue;
      for (let j = i + 1; j < n; j++) {
        if (mask & (1 << j)) continue;
        const nmask = mask | (1 << i) | (1 << j);
        const cand = dp[mask]! + op * g[i]![j]!;
        if (cand > dp[nmask]!) dp[nmask] = cand;
      }
    }
  }
  return dp[N - 1]!;
}

Template connection

Assignment bitmask DP: each transition adds a pair instead of a single item; extra score factor is popcount-driven.

Reflection

dp[mask] is the best score of the numbers inside the mask. Two unset bits form the next pair. The operation number is popcount / 2 + 1, and the addend is that times gcd.
The same number cannot enter two pairs. gcd may be 1. A different operation order changes the multiplier.
The empty mask is 0. The length is 2n and n is small. Two numbers are one operation, and the score is their gcd.