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

Maximum Number of Achievable Transfer Requests

Problem (restated)

n buildings, m ≤ 16 transfer requests [from, to]. A subset is achievable if every building has net degree 0. Maximize the subset size.

Intuition

Net-zero transfers ⇔ the selected edges form a balanced circulation. 2^16 is 65k, so enumerate. MITM would split requests and match opposite degree vectors, but that is unnecessary here.

Approaches

Enumerate request subsets

Unverified

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

Idea. For each mask, apply the selected requests to a degree array; if every building is 0, update the answer with the popcount. Self-requests [i,i] always help.

Walkthrough. n=2, requests two [0,1], two [1,0], one [0,0], one extra [0,1] → 5 (drop the unmatched [0,1]). Cycle [0,3],[3,1],[1,2],[2,0] → 4.

Trade-offs. Backtracking with pruning is similar. MITM on degree maps is the generalization when m grows past ~20.

Solution

export function maximumRequests(n: number, requests: number[][]): number {
  const m = requests.length;
  let ans = 0;
  for (let mask = 0; mask < 1 << m; mask++) {
    const bal = new Array<number>(n).fill(0);
    let cnt = 0;
    for (let i = 0; i < m; i++) {
      if ((mask & (1 << i)) === 0) continue;
      const req = requests[i]!;
      bal[req[0]!]! -= 1;
      bal[req[1]!]! += 1;
      cnt++;
    }
    if (cnt <= ans) continue;
    let ok = true;
    for (let i = 0; i < n; i++) if (bal[i] !== 0) { ok = false; break; }
    if (ok) ans = cnt;
  }
  return ans;
}

export function maximumRequests(n: number, requests: number[][]): number {
  const m = requests.length;
  let ans = 0;
  for (let mask = 0; mask < 1 << m; mask++) {
    const bal = new Array<number>(n).fill(0);
    let cnt = 0;
    for (let i = 0; i < m; i++) {
      if ((mask & (1 << i)) === 0) continue;
      const req = requests[i]!;
      bal[req[0]!]! -= 1;
      bal[req[1]!]! += 1;
      cnt++;
    }
    if (cnt <= ans) continue;
    let ok = true;
    for (let i = 0; i < n; i++) if (bal[i] !== 0) { ok = false; break; }
    if (ok) ans = cnt;
  }
  return ans;
}

Template connection

Constraint-satisfaction MITM degenerates to brute subset enumeration when m ≤ 16. The join key would have been the n-dimensional degree vector.

Reflection

Each mask is a subset of requests. After applying it, the subset is legal when every building’s net change is 0. The answer is the largest popcount.
The empty mask is 0. A request with from == to does not change any net, and it still counts.
Order does not matter; the balance does. There are at most 16 requests.