Problem link ও উৎস
- **Original source:** USACO Guide — DP Bitmasks
- **Platform:** USACO Guide —
- **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)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা ছোট, পরিষ্কার উদাহরণ দিয়ে bitmask DP-র ধারণা পাকা করি — **assignment problem**:
`n` জন কর্মী আর `n` টা কাজ আছে। কর্মী `i` কাজ `j` করলে খরচ `cost[i][j]`। প্রতিজনকে ঠিক একটা করে কাজ, প্রতিটা কাজ ঠিক একজনকে — মোট খরচ **সবচেয়ে কম** করতে হবে।
ভাবার মূল চ্যালেঞ্জ: "কোন কোন কাজ এখনো বাকি / নেওয়া হয়ে গেছে" — সেই তথ্যটা কীভাবে track করব? উত্তর: একটা bitmask দিয়ে।
(আরেকটা ক্লাসিক উদাহরণ Traveling Salesman, কিন্তু assignment-টা প্রথমবারের জন্য পরিষ্কার।)
### Input ও output {#6-example-input-and-output}
```text
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
```
আরেকটা:
```text
cost = [[1]] -> 1 (একজন, একটা কাজ)
cost = [[1, 2],
[2, 1]] -> 2 (0->0, 1->1 = 1+1)
```
edge case: `n = 1` → একটাই বণ্টন। সব permutation-এর সবচেয়ে কমটাই উত্তর।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা ছোট অফিসে একটা **চাবির বোর্ড** — প্রতিটা কাজের জন্য একটা হুক। কাজ শুরু হলে সেই হুক থেকে চাবি তুলে নেওয়া হয় (hook খালি = bit জ্বলা = কাজ নেওয়া)।
বোর্ডের দিকে তাকিয়েই তুমি বলতে পারো "এখন পর্যন্ত কোন কোন কাজ চলছে" — পুরো বোর্ডের অবস্থা একটা ছবি, একটা সংখ্যা (mask)। আর তুমি একটা খাতায় লিখে রাখো: "বোর্ড এই অবস্থায় থাকলে, বাকি কাজ শেষ করতে কমপক্ষে কত খরচ" — সেই খাতাই `dp[mask]`। একই বোর্ড-অবস্থা বারবার এলে আবার হিসেব না করে খাতা থেকে পড়ে নাও — এটাই DP-র memoization।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-র কাঠামোয়।
### ভেতরের অঙ্ক {#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-এ এখনো নেই) দেবো — সব সম্ভাবনা দেখে সবচেয়ে কম খরচ নিই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
DP না জানলে, সব permutation চেষ্টা করা স্বাভাবিক — কর্মীদের কাজ বণ্টনের প্রতিটা সম্ভাবনা ধরে খরচ যোগ করো:
```python
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** বারবার করে।
```text
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):
```python
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 করতে হয় না।
### ছবিতে বোঝা {#5-visual-explanation}
`n = 3`। mask-এর প্রতিটা bit একটা কাজ:
```text
mask = 0 0 0 -> কোনো কাজ নেওয়া হয়নি (শুরু), কর্মী 0-এর পালা
mask = 1 0 1 -> কাজ 0 আর কাজ 2 নেওয়া হয়েছে (2টা bit -> কর্মী 2-এর পালা)
mask = 1 1 1 -> সব কাজ নেওয়া (শেষ অবস্থা, খরচ 0 বাকি)
```
কর্মী index = কত bit জ্বলা:
```text
popcount(000) = 0 -> এখন কর্মী 0 কাজ বাছবে
popcount(101) = 2 -> এখন কর্মী 2 কাজ বাছবে
popcount(111) = 3 -> সবাই হয়ে গেছে, base case
```
Transition (mask = 000, কর্মী 0):
```text
কর্মী 0 -> কাজ 0 নিলে: cost[0][0] + dp[001]
কর্মী 0 -> কাজ 1 নিলে: cost[0][1] + dp[010]
কর্মী 0 -> কাজ 2 নিলে: cost[0][2] + dp[100]
dp[000] = এই তিনটার মধ্যে সবচেয়ে ছোট
```
### ছোট input-এ ধাপে ধাপে {#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):
```text
কাজ 0 বাকি -> cost[1][0] + dp[11] = 2 + 0 = 2
dp[10] = 2
```
mask = `01` (= 1, কাজ 0 নেওয়া, popcount 1 → কর্মী 1):
```text
কাজ 1 বাকি -> cost[1][1] + dp[11] = 1 + 0 = 1
dp[01] = 1
```
mask = `00` (= 0, কিছু নেওয়া হয়নি, popcount 0 → কর্মী 0):
```text
কাজ 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) ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
dp[FULL] = 0
```
base case — সব কাজ নেওয়া হয়ে গেলে আর কোনো খরচ বাকি নেই।
```text
for mask in range(FULL - 1, -1, -1):
i = bin(mask).count("1")
```
আমরা বেশি-bit (বেশি কাজ নেওয়া) থেকে কম-bit-এর দিকে যাই, যাতে `dp[mask | (1 << j)]` (বেশি bit) আগে থেকেই হিসেব হয়ে থাকে। `popcount(mask)` বলে দেয় এখন কোন কর্মীর পালা — কারণ যত কাজ নেওয়া, ততজন কর্মী বণ্টন হয়ে গেছে।
```text
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!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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))` লেখো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Shortest Path Visiting All Nodes** (