063 — Bitmask DP Intro

এই level-এর সবচেয়ে কঠিন note — তাড়াহুড়ো নেই। 062-এ শিখলে প্রতিটা subset একটা সংখ্যা (mask)। আজ সেই idea-টা এক ধাপ এগিয়ে: সেই mask-কে DP-র state বানানো। "কোন কোন জিনিস এখনো পর্যন্ত নেওয়া/ঘোরা হয়েছে" — পুরো সেই set একটা ছোট্ট int-এ ভরে ফেলা। এটাই Traveling Salesman আর assignment problem-এর বিখ্যাত সমাধানের ভিত্তি। আমরা এখানে শুধু দরজাটা খুলব। ধীরে, কয়েকবার পড়ো।

Source

• Original source: USACO Guide — DP Bitmasks
• Platform: USACO Guide — https://usaco.guide/gold/dp-bitmasks
• Topic: Math-based programming fundamentals → Level 4: Bit Manipulation → bitmask dynamic programming
• Difficulty: Hard
• Pattern: state as mask (visited set = একটা int, dp[mask])
• Basic idea inherited from: 062 — Subset Generation using Bits (mask = subset)

1. Problem in simple words

একটা ছোট, পরিষ্কার উদাহরণ দিয়ে bitmask DP-র ধারণা পাকা করি — assignment problem:

n জন কর্মী আর n টা কাজ আছে। কর্মী i কাজ j করলে খরচ cost[i][j]। প্রতিজনকে ঠিক একটা করে কাজ, প্রতিটা কাজ ঠিক একজনকে — মোট খরচ সবচেয়ে কম করতে হবে।

ভাবার মূল চ্যালেঞ্জ: "কোন কোন কাজ এখনো বাকি / নেওয়া হয়ে গেছে" — সেই তথ্যটা কীভাবে track করব? উত্তর: একটা bitmask দিয়ে।

(আরেকটা ক্লাসিক উদাহরণ Traveling Salesman, কিন্তু assignment-টা প্রথমবারের জন্য পরিষ্কার।)

2. What is the math idea?

মূল idea: পুরো "নেওয়া হয়ে গেছে" set-কে একটা int-এ encode করা, আর সেটাকে DP table-এর index বানানো।

• mask-এর j-তম bit জ্বলা মানে কাজ j ইতিমধ্যে কাউকে দেওয়া হয়ে গেছে।
• dp[mask] = "এই mask-এর কাজগুলো বণ্টন করতে সবচেয়ে কম খরচ কত।"
• mask-এ যতগুলো bit জ্বলা = এ পর্যন্ত কতজন কর্মীকে কাজ দেওয়া হয়েছে (i = popcount(mask))।

Transition: কর্মী i-কে কোন নতুন কাজ j (যেটা mask-এ এখনো নেই) দেবো — সব সম্ভাবনা দেখে সবচেয়ে কম খরচ নিই।

3. Which basic idea does this inherit from?

সরাসরি 062 (Subset Generation)-এর উপর — সেখানে শিখলে mask মানে subset (কোন কোন element নেওয়া)। এখানে সেই subset = "কোন কোন কাজ নেওয়া হয়ে গেছে", আর mask শুধু একটা ছবি নয়, DP-র state।

এর সাথে লাগে আগের primitive গুলো:

• 054 check — কাজ j নেওয়া কিনা: mask & (1 << j)
• 055 set — কাজ j নিলাম: mask | (1 << j)
• 058 popcount — কতজন কর্মী হয়ে গেছে: bin(mask).count("1")

মানে 063 = পুরো bit-primitive টুলবক্স একসাথে, DP-র কাঠামোয়।

4. Real-life analogy

ভাবো একটা ছোট অফিসে একটা চাবির বোর্ড — প্রতিটা কাজের জন্য একটা হুক। কাজ শুরু হলে সেই হুক থেকে চাবি তুলে নেওয়া হয় (hook খালি = bit জ্বলা = কাজ নেওয়া)।

বোর্ডের দিকে তাকিয়েই তুমি বলতে পারো "এখন পর্যন্ত কোন কোন কাজ চলছে" — পুরো বোর্ডের অবস্থা একটা ছবি, একটা সংখ্যা (mask)। আর তুমি একটা খাতায় লিখে রাখো: "বোর্ড এই অবস্থায় থাকলে, বাকি কাজ শেষ করতে কমপক্ষে কত খরচ" — সেই খাতাই dp[mask]। একই বোর্ড-অবস্থা বারবার এলে আবার হিসেব না করে খাতা থেকে পড়ে নাও — এটাই DP-র memoization।

5. Visual explanation

n = 3। mask-এর প্রতিটা bit একটা কাজ:

mask = 0 0 0  ->  কোনো কাজ নেওয়া হয়নি (শুরু), কর্মী 0-এর পালা
mask = 1 0 1  ->  কাজ 0 আর কাজ 2 নেওয়া হয়েছে (2টা bit -> কর্মী 2-এর পালা)
mask = 1 1 1  ->  সব কাজ নেওয়া (শেষ অবস্থা, খরচ 0 বাকি)

কর্মী index = কত bit জ্বলা:

popcount(000) = 0  -> এখন কর্মী 0 কাজ বাছবে
popcount(101) = 2  -> এখন কর্মী 2 কাজ বাছবে
popcount(111) = 3  -> সবাই হয়ে গেছে, base case

Transition (mask = 000, কর্মী 0):

কর্মী 0 -> কাজ 0 নিলে: cost[0][0] + dp[001]
কর্মী 0 -> কাজ 1 নিলে: cost[0][1] + dp[010]
কর্মী 0 -> কাজ 2 নিলে: cost[0][2] + dp[100]
dp[000] = এই তিনটার মধ্যে সবচেয়ে ছোট

6. Example input and output

cost = [[9, 2, 7],
        [6, 4, 3],
        [5, 8, 1]]

সম্ভাব্য বণ্টন (কর্মী->কাজ) আর মোট খরচ:
  0->0, 1->1, 2->2 : 9 + 4 + 1 = 14
  0->1, 1->0, 2->2 : 2 + 6 + 1 = 9
  0->1, 1->2, 2->0 : 2 + 3 + 5 = 10
  0->2, 1->1, 2->0 : 7 + 4 + 5 = 16
  ... (মোট 3! = 6 রকম)

সবচেয়ে কম: 0->1, 1->0, 2->2  ->  9
output: 9

আরেকটা:

cost = [[1]]            ->  1     (একজন, একটা কাজ)
cost = [[1, 2],
        [2, 1]]         ->  2     (0->0, 1->1 = 1+1)

edge case: n = 1 → একটাই বণ্টন। সব permutation-এর সবচেয়ে কমটাই উত্তর।

7. Brute force thinking

DP না জানলে, সব permutation চেষ্টা করা স্বাভাবিক — কর্মীদের কাজ বণ্টনের প্রতিটা সম্ভাবনা ধরে খরচ যোগ করো:

from itertools import permutations

def assignment_brute(cost):
    n = len(cost)
    best = float("inf")
    for perm in permutations(range(n)):       # প্রতিটা কাজ-বণ্টন
        total = sum(cost[i][perm[i]] for i in range(n))
        best = min(best, total)
    return best

কাজ করে — সব n! রকম বণ্টন দেখে সবচেয়ে কমটা নিই। কিন্তু n! খুব দ্রুত বিস্ফোরিত হয়।

8. Why brute force may be slow

n! (factorial) ভয়ংকর দ্রুত বাড়ে — 10! ≈ 36 লাখ, 13! ≈ 62 কোটি, 15! প্রায় ট্রিলিয়ন। অথচ অনেক permutation আসলে একই sub-problem বারবার করে।

n!     vs   2^n × n  (bitmask DP):
n=10 : 3.6M       vs   ~10K
n=15 : 1.3T       vs   ~0.5M
n=20 : huge       vs   ~20M  (চলে!)

মূল অপচয়: "কাজ {0,2} নেওয়া হয়ে গেছে, বাকিটা কত কমে শেষ হয়?" — এই উত্তর বহু permutation-এ একই, কিন্তু brute force প্রতিবার নতুন করে গোনে। bitmask DP সেটা একবার গুনে dp[mask]-এ রেখে দেয়।

9. Better thinking

mask-কে state বানাও: dp[mask] = mask-এর কাজগুলো বণ্টনের সবচেয়ে কম খরচ। কর্মী index = popcount(mask):

def assignment_bitmask(cost):
    n = len(cost)
    FULL = (1 << n) - 1
    INF = float("inf")
    dp = [INF] * (1 << n)
    dp[FULL] = 0                              # সব কাজ নেওয়া -> বাকি খরচ 0

    for mask in range(FULL - 1, -1, -1):      # বেশি-নেওয়া থেকে কম-নেওয়ার দিকে
        i = bin(mask).count("1")              # এখন কর্মী i-এর পালা
        for j in range(n):
            if not (mask & (1 << j)):         # কাজ j এখনো বাকি
                cand = cost[i][j] + dp[mask | (1 << j)]
                if cand < dp[mask]:
                    dp[mask] = cand
    return dp[0]                              # কিছু নেওয়া হয়নি, শুরু থেকে

এখানে state সংখ্যা 2^n, প্রতিটায় n টা transition → O(2^n × n)। n!-এর তুলনায় আকাশ-পাতাল।

10. Thinking tweak

আসল "আহা!" — "কোন কোন জিনিস নেওয়া হয়ে গেছে" — এই পুরো set একটা int-এ ভরে ফেলা যায়, আর সেই int-কে DP-র index বানালে একই sub-problem আর বারবার গুনতে হয় না।

brute force প্রতিটা permutation আলাদা দেখে, কিন্তু আসল sub-problem তো "এই কাজগুলো নেওয়া অবস্থায় বাকিটা কত?" — সেটা নির্ভর করে শুধু কোন কাজগুলো নেওয়া তার উপর, কোন ক্রমে নেওয়া তার উপর নয়। mask ঠিক সেই "কোনগুলো নেওয়া" ধরে রাখে (ক্রম ভুলে যায়), তাই বহু permutation একই mask-এ মিলে যায় — আর আমরা একবার গুনে রেখে দিই। বোনাস চাল: popcount(mask) = কতজন হয়ে গেছে, তাই আলাদা করে "কোন কর্মী" track করতে হয় না।

11. Step-by-step dry run

ছোট cost = [[1, 2], [2, 1]] (n = 2)। FULL = 11 = 3।

base: dp[11] = 0।

mask = 10 (= 2, কাজ 1 নেওয়া, popcount 1 → কর্মী 1):

কাজ 0 বাকি -> cost[1][0] + dp[11] = 2 + 0 = 2
dp[10] = 2

mask = 01 (= 1, কাজ 0 নেওয়া, popcount 1 → কর্মী 1):

কাজ 1 বাকি -> cost[1][1] + dp[11] = 1 + 0 = 1
dp[01] = 1

mask = 00 (= 0, কিছু নেওয়া হয়নি, popcount 0 → কর্মী 0):

কাজ 0 -> cost[0][0] + dp[01] = 1 + 1 = 2
কাজ 1 -> cost[0][1] + dp[10] = 2 + 2 = 4
dp[00] = min(2, 4) = 2

উত্তর dp[0] = 2 (বণ্টন: কর্মী 0→কাজ 0, কর্মী 1→কাজ 1, খরচ 1+1=2) ✓।

12. Python solution

from itertools import permutations


def assignment_bitmask(cost):
    """assignment problem-এর সর্বনিম্ন খরচ, bitmask DP দিয়ে।
    dp[mask] = mask-এর কাজগুলো বণ্টন করতে বাকি সর্বনিম্ন খরচ।"""
    n = len(cost)
    FULL = (1 << n) - 1
    INF = float("inf")
    dp = [INF] * (1 << n)
    dp[FULL] = 0                              # সব কাজ নেওয়া -> খরচ 0

    for mask in range(FULL - 1, -1, -1):      # বেশি-নেওয়া থেকে কম-নেওয়ার দিকে
        i = bin(mask).count("1")              # এখন কর্মী i-এর পালা
        for j in range(n):
            if not (mask & (1 << j)):         # কাজ j এখনো বাকি (054 check)
                cand = cost[i][j] + dp[mask | (1 << j)]   # j নিলাম (055 set)
                if cand < dp[mask]:
                    dp[mask] = cand
    return dp[0]


def assignment_brute(cost):
    """একই উত্তর সব permutation দেখে (যাচাইয়ের জন্য)।"""
    n = len(cost)
    best = float("inf")
    for perm in permutations(range(n)):
        total = sum(cost[i][perm[i]] for i in range(n))
        best = min(best, total)
    return best


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert assignment_bitmask([[1]]) == 1
assert assignment_bitmask([[1, 2], [2, 1]]) == 2          # 1 + 1
assert assignment_bitmask([[9, 2, 7],
                           [6, 4, 3],
                           [5, 8, 1]]) == 9               # 2 + 6 + 1 (0->1,1->0,2->2)

# DP আর brute force একই উত্তর দেয় (random matrix-এ)
import random
for _ in range(120):
    n = random.randint(1, 6)
    cost = [[random.randint(0, 20) for _ in range(n)] for _ in range(n)]
    assert assignment_bitmask(cost) == assignment_brute(cost)

print(assignment_bitmask([[1, 2], [2, 1]]))               # 2
print(assignment_bitmask([[9, 2, 7], [6, 4, 3], [5, 8, 1]]))  # 9
print("সব test pass!")

13. Line-by-line explanation

dp[FULL] = 0

base case — সব কাজ নেওয়া হয়ে গেলে আর কোনো খরচ বাকি নেই।

for mask in range(FULL - 1, -1, -1):
    i = bin(mask).count("1")

আমরা বেশি-bit (বেশি কাজ নেওয়া) থেকে কম-bit-এর দিকে যাই, যাতে dp[mask | (1 << j)] (বেশি bit) আগে থেকেই হিসেব হয়ে থাকে। popcount(mask) বলে দেয় এখন কোন কর্মীর পালা — কারণ যত কাজ নেওয়া, ততজন কর্মী বণ্টন হয়ে গেছে।

if not (mask & (1 << j)):
    cand = cost[i][j] + dp[mask | (1 << j)]

কাজ j এখনো বাকি কিনা দেখি (054 check)। বাকি থাকলে কর্মী i-কে j দিই: এই খরচ cost[i][j] + বাকিটা dp[mask | (1 << j)] (055 set দিয়ে নতুন state)। সব বৈধ j-র মধ্যে সবচেয়ে ছোটটা dp[mask]-এ রাখি।

assert আর random for loop DP-কে brute force-এর সাথে 120টা random matrix-এ মিলিয়ে নিচ্ছে। সব ঠিক থাকলে সব test pass!।

14. Output walkthrough

চালালে যা ছাপবে:

2
9
সব test pass!

প্রথম দুই লাইন দুটো print থেকে: [[1,2],[2,1]]→2 (কর্মী 0→0, 1→1), [[9,2,7],[6,4,3],[5,8,1]]→9 (0→1, 1→0, 2→2 = 2+6+1)। সব assert (random cross-check loop সহ) চুপচাপ pass করেছে। শেষে সব test pass!।

15. Time complexity

O(2^n × n) — 2^n টা mask (state), প্রতিটায় n টা কাজ চেষ্টা করি। n!-এর তুলনায় বিশাল উন্নতি; তাই n ≈ 20 পর্যন্ত চলে।

16. Space complexity

O(2^n) — dp array-এ প্রতিটা mask-এর জন্য একটা মান রাখতে হয়। এই exponential memory-ই n-কে ছোট (≤ 20-22) থাকতে বাধ্য করে।

17. Common mistakes

1. mask-এর iteration ক্রম ভুল — dp[mask] নির্ভর করে dp[বেশি bit-ওয়ালা mask]-এর উপর; তাই বেশি-bit আগে হিসেব হতে হবে (এখানে উল্টো দিকে loop)।
2. কর্মী index ভুল বের করা — i = popcount(mask); আলাদা করে track করতে গেলে বাগ আসে।
3. range(1 << n) বনাম range(n) — state সংখ্যা 2^n, কাজ সংখ্যা n — দুটো গুলিয়ো না (README #6)।
4. n বড় দেখে bitmask চাপানো — 2^n exponential; n > 22-23 হলে memory/time উড়ে যাবে। n ≤ 20 দেখলেই কেবল bitmask।
5. Precedence ফাঁদ — mask & (1 << j) সবসময় bracket-এ; if not (mask & (1 << j)) লেখো।

18. Harder problems that inherit this idea

• LeetCode — Shortest Path Visiting All Nodes (https://leetcode.com/problems/shortest-path-visiting-all-nodes/) — dp[mask][node], ক্লাসিক bitmask DP।
• LeetCode — Partition to K Equal Sum Subsets (https://leetcode.com/problems/partition-to-k-equal-sum-subsets/) — mask দিয়ে used-set track।
• USACO Guide — DP Bitmasks (https://usaco.guide/gold/dp-bitmasks) — পুরো topic-এর গাইড।
• CSES — Hamiltonian Flights / Elevator Rides (https://cses.fi/problemset/) — bitmask DP-র সংগ্রহ।

19. Pattern learned

Bitmask DP (state as mask) — "কোন কোন জিনিস নেওয়া/ভিজিট হয়েছে" set-কে int বানিয়ে dp[mask]-এ index করা, popcount দিয়ে ধাপ ট্র্যাক করা। বড় শিক্ষা: sub-problem নির্ভর করে কোন জিনিসগুলো নেওয়া তার উপর, ক্রমের উপর নয়; mask সেই set ধরে রাখে বলে n! থেকে 2^n × n-এ নামে।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "visited/used set একটা int-এ ভরো, dp[mask] বানাও; popcount দিয়ে ধাপ গোনো। 'n ছোট (≤ 20), সব permutation/visit লাগে' দেখলেই bitmask DP — n! থেকে 2^n × n। এটাই TSP/assignment-এর চাবি।"

পরের ধাপ → 064 — Gray Code (DP থেকে ফিরে bit pattern-এর সৌন্দর্যে — পরপর সংখ্যায় ঠিক 1 bit বদল)। সম্পর্কিত → 062 — Subset Generation using Bits।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি নেই — বরং "common interview pattern" / "Google-style pattern"।