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

Mediummeet-in-the-middle

Campus Bikes II

Problem (restated)

Assign each worker a unique bike. Minimize total Manhattan distance. workers, bikes ≤ 10.

Intuition

This is assignment, not subset-sum MITM. 2^m with m ≤ 10 is the same scale as MITM enumeration, so the catalog files it here; the algorithm is bitmask DP on used bikes.

Approaches

Bitmask assignment DP

Unverified

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

Idea. dp[mask] = min cost to assign the first popcount(mask) workers to the bikes in mask. Transition: give worker k any unused bike j. Iterate masks in increasing order so mask | (1<<j) is written after mask. Answer: min dp[mask] among masks with n bits.

Walkthrough. workers [[0,0],[2,1]], bikes [[1,2],[3,3]] → 6 ((0,0)→(1,2) cost 3 plus (2,1)→(3,3) cost 3).

Trade-offs. Hungarian is overkill at n=10. Splitting workers (true MITM) is possible but messier than this m·2^m DP.

Solution

export function assignBikes(workers: number[][], bikes: number[][]): number {
  const n = workers.length;
  const m = bikes.length;
  const inf = 1e9;
  const dp = new Array<number>(1 << m).fill(inf);
  dp[0] = 0;
  let ans = inf;
  for (let mask = 0; mask < 1 << m; mask++) {
    const cur = dp[mask]!;
    if (cur >= inf) continue;
    let k = 0;
    for (let t = mask; t > 0; t >>= 1) k += t & 1;
    if (k === n) {
      if (cur < ans) ans = cur;
      continue;
    }
    const w = workers[k]!;
    for (let j = 0; j < m; j++) {
      if (mask & (1 << j)) continue;
      const b = bikes[j]!;
      const cost = Math.abs(w[0]! - b[0]!) + Math.abs(w[1]! - b[1]!);
      const nxt = mask | (1 << j);
      dp[nxt] = Math.min(dp[nxt]!, cur + cost);
    }
  }
  return ans;
}

export function assignBikes(workers: number[][], bikes: number[][]): number {
  const n = workers.length;
  const m = bikes.length;
  const inf = 1e9;
  const dp = new Array<number>(1 << m).fill(inf);
  dp[0] = 0;
  let ans = inf;
  for (let mask = 0; mask < 1 << m; mask++) {
    const cur = dp[mask]!;
    if (cur >= inf) continue;
    let k = 0;
    for (let t = mask; t > 0; t >>= 1) k += t & 1;
    if (k === n) {
      if (cur < ans) ans = cur;
      continue;
    }
    const w = workers[k]!;
    for (let j = 0; j < m; j++) {
      if (mask & (1 << j)) continue;
      const b = bikes[j]!;
      const cost = Math.abs(w[0]! - b[0]!) + Math.abs(w[1]! - b[1]!);
      const nxt = mask | (1 << j);
      dp[nxt] = Math.min(dp[nxt]!, cur + cost);
    }
  }
  return ans;
}

Template connection

Assignment / TSP-style bitmask DP. Catalogued under MITM only because 2^m is the MITM-scale enumeration; there is no half-and-join.

Reflection

dp[mask] is the minimum cost of assigning the first popcount(mask) workers to the bikes in the mask. Worker k takes any bike j that is still free.
The cost is Manhattan. One bike goes to one worker. Walk masks in increasing order so a new bit is written after the mask it came from.
There may be fewer workers than bikes. The answer is the minimum among masks with exactly n bits set. n is small.