Tallest Billboard

Problem (restated)

Assign each rod to the left support, the right support, or neither. The two supports must end at equal height. Maximize that height (0 if impossible). n ≤ 20.

Intuition

Equal supports ⇔ two disjoint subsets with the same sum. 3^n is tight; MITM enumerates 3^{n/2} assignments per half and joins where diffs cancel.

Approaches

export function tallestBillboard(rods: number[]): number {
  const mid = rods.length >> 1;

  const diffs = (arr: number[]): Map<number, number> => {
    let dp = new Map<number, number>([[0, 0]]);
    for (const x of arr) {
      const ndp = new Map(dp);
      for (const [d, h] of dp) {
        const left = d + x;
        ndp.set(left, Math.max(ndp.get(left) ?? 0, h + x));
        const right = d - x;
        ndp.set(right, Math.max(ndp.get(right) ?? 0, h));
      }
      dp = ndp;
    }
    return dp;
  };

  const left = diffs(rods.slice(0, mid));
  const right = diffs(rods.slice(mid));
  let ans = 0;
  for (const [d, h] of left) {
    if (right.has(-d)) ans = Math.max(ans, h + right.get(-d)!);
  }
  return ans;
}

export function tallestBillboard(rods: number[]): number {
  const mid = rods.length >> 1;

  const diffs = (arr: number[]): Map<number, number> => {
    let dp = new Map<number, number>([[0, 0]]);
    for (const x of arr) {
      const ndp = new Map(dp);
      for (const [d, h] of dp) {
        const left = d + x;
        ndp.set(left, Math.max(ndp.get(left) ?? 0, h + x));
        const right = d - x;
        ndp.set(right, Math.max(ndp.get(right) ?? 0, h));
      }
      dp = ndp;
    }
    return dp;
  };

  const left = diffs(rods.slice(0, mid));
  const right = diffs(rods.slice(mid));
  let ans = 0;
  for (const [d, h] of left) {
    if (right.has(-d)) ans = Math.max(ans, h + right.get(-d)!);
  }
  return ans;
}

Template connection

Constraint-satisfaction MITM: the join key is the signed height diff instead of a subset sum.

Reflection

• Split the rods. Each rod goes left, right, or nowhere. The difference is left - right. A difference d meets -d, and the heights add.
• Keep the best height for each difference. Both halves using no rods give difference 0 and height 0, and that is not a billboard.
• n is about 20. Each half is 3**(n / 2) states. [1, 2] answers 0.