Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Maximum Number of Achievable Transfer Requests

Problem (yeniden ifade)

n bina, m ≤ 16 transfer isteği [from, to]. Bir alt küme, her binanın net derecesi 0 ise başarılabilir. Alt küme boyutunu büyüt.

Sezgi

Sıfır-net transfer ⇔ seçilen kenarlar dengeli bir dolaşım. 2^16 65k, say. MITM istekleri bölüp zıt derece vektörlerini eşlerdi ama burada gerekmez.

Yaklaşımlar

İstek alt kümelerini say

Doğrulanmadı

Zaman O(2^m·(m+n))Alan O(n)

Fikir. Her maske için seçilen istekleri derece dizisine uygula; her bina 0 ise cevabı popcount ile güncelle. [i,i] öz-istekleri her zaman yardımcı.

Yürüyüş. n=2, iki [0,1], iki [1,0], bir [0,0], bir fazla [0,1] → 5 (eşleşmeyen [0,1]’i bırak). Döngü [0,3],[3,1],[1,2],[2,0] → 4.

Trade-off. Budamalı backtracking benzer. m ~20’yi aşınca derece map’leri üzerinde MITM genellemedir.

Çözüm

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;
}

Şablon bağlantısı

Kısıt-doyurma MITM, m ≤ 16 iken kaba alt küme sayımına iner. Birleşim anahtarı n boyutlu derece vektörü olurdu.

Yansıma

Her maske bir istek alt kümesi. Seçilen isteklerden sonra her binanın neti 0 ise aday. Cevap en büyük popcount.
Boş maske 0. from == to neti bozmaz, sayılır.
Sıra önemli değil, denge önemli. İstek sayısı en fazla 16.