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

Distribute Repeating Integers

Problem (yeniden ifade)

nums değer sıklıkları ve her biri tek bir değerden quantity[i] kopya isteyen m ≤ 10 müşteri. Yığın yetiyorsa birkaç müşteri aynı değeri paylaşabilir. Hepsi tatmin edilebilir mi?

Sezgi

nums’u sıklık yığınlarına sıkıştır. Küçük küme müşteriler: 2^m maske. Her yığın, sıklığa sığan henüz tatmin edilmemiş bir alt maskeye verilir.

Yaklaşımlar

Alt maske atama DP

Doğrulanmadı

Zaman O(k * 3^m)Alan O(2^m)

Fikir. sums[mask] = o müşterilerin toplam talebi. ok[mask] = şimdiye kadarki yığınlarla bu küme tatmin edilebilir. Her sıklık f için, her ulaşılmış mask, tümleyeninin her alt maskesi: sums[sub] ≤ f ise mask | sub işaretle.

Yürüyüş. [1,2,3,4], [2] → false (2’lik yığın yok). [1,2,3,3], [2] → true. [1,1,2,2,3,3,4,4,4,4], [2,3] → true (4’ler 3 alır, başka yığın 2).

Trade-off. Alt maske dolaşımı yığın başına 3^m, 4^m değil. Çift etiket MITM: müşterileri ikiye bölüp atamaları eşleştirmek mümkün; m≤10 iken tam maske yeter.

Çözüm

export function canDistribute(nums: number[], quantity: number[]): boolean {
  const cnt = new Map<number, number>();
  for (const x of nums) cnt.set(x, (cnt.get(x) ?? 0) + 1);
  const freqs = [...cnt.values()];
  const m = quantity.length;
  const full = (1 << m) - 1;
  const sums = new Array<number>(1 << m).fill(0);
  for (let mask = 1; mask <= full; mask++) {
    let s = 0;
    for (let i = 0; i < m; i++) if (mask & (1 << i)) s += quantity[i]!;
    sums[mask] = s;
  }
  let ok = new Array<boolean>(1 << m).fill(false);
  ok[0] = true;
  for (const f of freqs) {
    const nxt = ok.slice();
    for (let mask = 0; mask <= full; mask++) {
      if (!ok[mask]) continue;
      const need = full ^ mask;
      let sub = need;
      while (true) {
        if (sums[sub]! <= f) nxt[mask | sub] = true;
        if (sub === 0) break;
        sub = (sub - 1) & need;
      }
    }
    ok = nxt;
    if (ok[full]) return true;
  }
  return ok[full]!;
}

export function canDistribute(nums: number[], quantity: number[]): boolean {
  const cnt = new Map<number, number>();
  for (const x of nums) cnt.set(x, (cnt.get(x) ?? 0) + 1);
  const freqs = [...cnt.values()];
  const m = quantity.length;
  const full = (1 << m) - 1;
  const sums = new Array<number>(1 << m).fill(0);
  for (let mask = 1; mask <= full; mask++) {
    let s = 0;
    for (let i = 0; i < m; i++) if (mask & (1 << i)) s += quantity[i]!;
    sums[mask] = s;
  }
  let ok = new Array<boolean>(1 << m).fill(false);
  ok[0] = true;
  for (const f of freqs) {
    const nxt = ok.slice();
    for (let mask = 0; mask <= full; mask++) {
      if (!ok[mask]) continue;
      const need = full ^ mask;
      let sub = need;
      while (true) {
        if (sums[sub]! <= f) nxt[mask | sub] = true;
        if (sub === 0) break;
        sub = (sub - 1) & need;
      }
    }
    ok = nxt;
    if (ok[full]) return true;
  }
  return ok[full]!;
}

Şablon bağlantısı

Atama / partisyon bitmask DP: her yığın kalan müşterilerin bir alt maskesini alır. m büyürse aynı bölme MITM olur.

Yansıma

sums[mask] o müşterilerin toplam talebi. Her sıklık f, ulaşılmış bir maskenin tümleyeninden sums[sub] ≤ f olan alt maskeyi işaretler.
Bir sıklık kovası bir grup müşteriye gider. Aynı kova iki kez kullanılmaz.
Talep toplama sığmazsa false. Müşteri sayısı küçük, maske 2^m. Boş müşteri kümesi true.