Problem link ও উৎস
- **Original source:** Self-directed capstone — Codeforces থেকে চোখ-বুজে একটা 1400–1700 rated DP তুলে নাও
- **Platform:** Codeforces —
- **Topic:** dynamic programming (pattern recognition across the whole folder)
- **Difficulty:** Hard
- **Pattern:** Pattern recognition (any family)
- **Basic idea inherited from:** পুরো folder — এটা কোনো নির্দিষ্ট problem নয়, একটা **drill**: code করার আগে শুধু title + constraints থেকে family-র নাম বলা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
এটা একক problem নয়, একটা অভ্যাস। Codeforces problemset-এ যাও, "dp" tag দিয়ে filter করো, 1400–1700 rating-এ একটা problem **না দেখে** তুলে নাও। তারপর **statement পড়ার আগে নয়, code লেখার আগে** — শুধু title আর constraints থেকে বলো কোন DP family (1D / grid / knapsack / LIS / string / interval / DAG / bitmask)। এই note সেই ritual-টাকে একটা reusable checklist বানায়, আর একটা ছোট worked example দিয়ে দেখায় constraints থেকে কীভাবে family + complexity আন্দাজ করা যায়।
### সরাসরি একটি প্রশ্ন দিয়ে শুরু {#_1}
[Codeforces 455A · Boredom](https://codeforces.com/problemset/problem/455/A) দিয়ে শুরু করতে পারেন। একটি value নিলে পাশের value নেওয়া যায় না; value অনুযায়ী লাভ গুনে take-or-skip state ভাবুন। নিচের drill-এর worked example আলাদা; সেটিকে এই judge problem-এর সম্পূর্ণ সমাধান ভাববেন না।
### Input ও output {#8-example-input-and-output}
এই note-এর "input" হলো constraint, "output" হলো family-অনুমান:
```text
"n <= 18, assign n tasks to n workers, min cost" -> bitmask DP, dp[mask]
"two strings up to 1000, min ops to make equal" -> string DP, dp[i][j]
"array up to 1e5, longest increasing subseq" -> LIS, dp[i] (n log n)
"coins unlimited, make amount A (A up to 1e6)" -> unbounded knapsack
"grid 1000x1000, min path cost top-left to bottom" -> grid DP, dp[r][c]
"merge n<=300 stones, cost = sum of merged" -> interval DP, dp[l][r]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি অভিজ্ঞ একজন ডাক্তার, আর রোগী (problem) ঘরে ঢুকল। তুমি পুরো ইতিহাস শোনার আগেই কয়েকটা লক্ষণ (trigger word, n-এর মান) দেখে সম্ভাব্য রোগের শ্রেণি (family) আন্দাজ করো — তারপর পরীক্ষা (5-step doctrine) করে নিশ্চিত হও। অভিজ্ঞতা মানে দ্রুত সঠিক shortlist বানানো, অন্ধ আন্দাজ নয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি গোটা folder — `patterns.md`-এর family-গুলো, `state-transition-thinking.md`-এর 5-step doctrine, আর আগের 23টা problem-এর muscle। আগের প্রতিটা note একটা নির্দিষ্ট family শিখিয়েছে; এই capstone সেগুলোকে এক জায়গায় এনে জিজ্ঞেস করে: "অদেখা একটা problem-এ তুমি কি trigger word থেকেই family চিনতে পারো?"
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic constraint-পড়া। `n`-এর সীমাই target complexity ফাঁস করে দেয়, আর complexity প্রায়ই family-কে সংকীর্ণ করে:
```text
n <= ~20 -> 2^n বা n*2^n সম্ভব -> bitmask DP
n <= ~500 -> O(n^2) বা O(n^3) ঠিক -> interval / two-string grid
n <= ~5000 -> O(n^2) ঠিক -> LIS(n^2) / knapsack
n <= ~10^5, 10^6 -> O(n) বা O(n log n) -> 1D linear / LIS(n log n)
দুটো sequence -> O(n*m) grid -> string DP
grid দেওয়া -> O(rows*cols) -> grid DP
"unlimited / coins" -> budget axis -> knapsack
```
এই mapping-টাই "hidden math": সংখ্যা → অনুমোদিত complexity → সম্ভাব্য family।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
family-অনুযায়ী আলাদা — তাই কোনো একক উত্তর নেই, বরং একটা lookup:
```text
1D linear -> dp[i] (array / দুই rolling variable)
grid -> dp[r][c] (2D array)
knapsack -> dp[budget] (1D, direction-সচেতন)
LIS -> dp[i] ends-at-i (array; n log n হলে tails + bisect)
string DP -> dp[i][j] (2D array)
interval -> dp[l][r] (2D, length-order fill)
DAG -> dp[v] (array + topo order)
bitmask -> dp[mask] (size-2^n array)
```
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতিটা family-র state-আকার ঠিক ততটুকু তথ্য ধরে যতটা "শেষ decision" নিতে লাগে — এটাই doctrine-এর core। তাই data structure-টা state-আকারের সরাসরি অনুবাদ: prefix হলে 1D array, দুই sequence হলে 2D, subset মনে রাখা লাগলে bitmask। সঠিক family চিনলে data structure প্রায় নিজে নিজেই ঠিক হয়ে যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা (যেকোনো DP-র আগে): সব সম্ভাবনা enumerate করো — সব subset, সব permutation, বা সব path — আর best/count নাও। এটা প্রায় সবসময় exponential, কিন্তু এটাই সঠিক recurrence-এর কঙ্কাল দেয়: "শেষ decision কী, আর তার আগে কী জানা লাগত?"
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
enumeration সাধারণত O(2^n), O(n!) বা branching recursion — overlapping subproblem-এর কারণে একই কাজ বারবার হয়। constraint যত বড়, brute তত দ্রুত অচল; আর constraint-এর আকারই বলে দেয় কত দ্রুত হতে **হবে**, তাই কোন family লাগবে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: DP problem অসীম মনে হলেও বেশির ভাগই হাতে-গোনা কয়েকটা family-র সদস্য, আর constraint-এর সংখ্যা সেই family-কে আগেই সংকীর্ণ করে দেয়। তাই "এটা কোন DP?" আন্দাজ নয় — এটা trigger word + n-এর একটা lookup।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** এই capstone-এ "state" হলো তোমার নিজের সিদ্ধান্ত-প্রক্রিয়ার state — কোন family shortlist করেছ আর কেন। কিন্তু drill-টা শক্ত করতে নিচের `classify()` function একটা concrete decision rule encode করে: feature (trigger word, constraint) → family-নাম।
**Transition (decision rule):**
```text
family = first matching rule among:
has two sequences -> "string"
grid + right/down moves -> "grid"
coins/items + capacity -> "knapsack"
DAG / prerequisites -> "dag"
longest increasing/chain -> "lis"
merge/burst a range -> "interval"
n <= 20 + use-each-once -> "bitmask"
sequence + ways/best to i -> "1d-linear"
```
**Base case:** কোনো rule না মিললে → "needs a creative anchor or extra dimension" (LIS-এর শিক্ষা)।
**Answer location:** তোমার লেখা family-নাম, যেটা পরে 5-step doctrine দিয়ে যাচাই করবে।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** unseen problem-এ সরাসরি code-এ ঝাঁপিয়ো না। আগে **family guess লিখে রাখো**, তারপর statement পড়ে guess যাচাই করো, তারপর 5 step কাগজে লেখো — তবেই editor। guess vs reality track করলে তোমার pattern-recognition দ্রুত নিজেকে শোধরায়; ভুল guess নিজেই সবচেয়ে দামি feedback।
### ছবিতে বোঝা {#7-visual-explanation}
একটা decision-tree হিসেবে family-spotting:
```text
problem পড়ো
|
+-- দুটো string / sequence? ------------------> String DP dp[i][j]
|
+-- grid + "right/down"? ---------------------> Grid DP dp[r][c]
|
+-- "coins / items / capacity / budget"? -----> Knapsack dp[budget]
|
+-- "longest increasing / nesting / chain"? --> LIS dp[i]
|
+-- "merge/burst a range, neighbor cost"? ----> Interval dp[l][r]
|
+-- "prerequisites / DAG / longest chain"? ---> DP on DAG dp[v]
|
+-- n <= 20, "use each exactly once"? --------> Bitmask dp[mask]
|
+-- "n steps/days in a row, ways/best"? ------> 1D linear dp[i]
```
উপর থেকে নিচে প্রথম যেটা মেলে, সেটাই তোমার প্রথম সন্দেহ — তারপর doctrine দিয়ে যাচাই।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
একটা কাল্পনিক pick: "n ≤ 16 শহর, প্রতিটা ঠিক একবার ঘুরে min total distance":
1. trigger: "n ≤ 16", "প্রতিটা একবার", "min cost" → subset মনে রাখা লাগবে
2. constraint: n ≤ 16 → 2^16 ≈ 65536 affordable → bitmask সম্ভব
3. family guess: **bitmask DP**, `dp[mask][last]`
4. doctrine: state = "কোন শহর-set ভিজিট করা শেষ + এখন কোথায়"; transition = একটা unvisited শহর যোগ
5. যাচাই: statement পড়ে নিশ্চিত — হ্যাঁ, classic TSP-ধাঁচ ✔
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
# এই capstone-এর "solution" হলো একটা family-classifier:
# unseen problem-এর feature দিলে সম্ভাব্য DP family ফেরত দেয়।
# (একটা practice harness, সত্যিকারের solver নয় — কিন্তু runnable ও testable।)
def classify(features):
"""features: trigger word / constraint-এর একটা dict।"""
n = features.get("n", None)
text = " ".join(features.get("words", [])).lower()
if features.get("two_sequences"):
return "string"
if features.get("grid") and ("right" in text or "down" in text or "path" in text):
return "grid"
if ("coin" in text or "item" in text or "knapsack" in text
or features.get("capacity")):
return "knapsack"
if features.get("dag") or "prerequisite" in text or "dependency" in text:
return "dag"
if "increasing" in text or "nesting" in text or "chain" in text:
return "lis"
if "merge" in text or "burst" in text or "range" in text:
return "interval"
if n is not None and n <= 20 and ("each" in text or "every" in text
or "permutation" in text):
return "bitmask"
if "step" in text or "day" in text or "ways" in text or "house" in text:
return "1d-linear"
return "needs-anchor"
def target_complexity(n):
"""constraint -> অনুমোদিত complexity (পেন্সিল-rule)।"""
if n is None:
return "unknown"
if n <= 20:
return "O(2^n) / O(n*2^n)"
if n <= 500:
return "O(n^2) / O(n^3)"
if n <= 5000:
return "O(n^2)"
if n <= 10 ** 6:
return "O(n) / O(n log n)"
return "O(n) or better"
# ---- tests ----
fam_cases = [
({"two_sequences": True, "words": ["min ops to make equal"]}, "string"),
({"grid": True, "words": ["min path right down"]}, "grid"),
({"words": ["coins unlimited make amount"]}, "knapsack"),
({"words": ["longest increasing subsequence"]}, "lis"),
({"words": ["merge stones range cost"]}, "interval"),
({"words": ["course prerequisite longest chain"], "dag": True}, "dag"),
({"n": 16, "words": ["visit every city once permutation"]}, "bitmask"),
({"words": ["count ways to climb n steps"]}, "1d-linear"),
({"words": ["some weird novel thing"]}, "needs-anchor"),
]
for feat, want in fam_cases:
assert classify(feat) == want, (feat, classify(feat))
comp_cases = [
(16, "O(2^n) / O(n*2^n)"),
(300, "O(n^2) / O(n^3)"),
(5000, "O(n^2)"),
(100000, "O(n) / O(n log n)"),
(None, "unknown"),
]
for n, want in comp_cases:
assert target_complexity(n) == want, (n, target_complexity(n))
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `classify`: feature-dict (trigger word + constraint) নেয়; rule-গুলো `patterns.md`-এর family-spotting table-এর order-এ প্রথম-মিল ভিত্তিতে family-নাম ফেরত দেয়; কিছু না মিললে `"needs-anchor"`।
- `target_complexity`: `n`-এর মান থেকে অনুমোদিত complexity-এর গুচ্ছ দেয় — ঠিক সেই পেন্সিল-নিয়ম যা contest-এ family সংকীর্ণ করতে কাজে লাগে।
- দুই test block দেখায় classifier আর complexity-rule দুটোই প্রত্যাশিত family/complexity দেয়; এটা drill-এর mental model-কে concrete করে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`fam_cases`-এ নয়টা feature-set: আট family-র একটা করে প্রতিনিধি (string, grid, knapsack, lis, interval, dag, bitmask, 1d-linear) আর একটা "novel" যেটা `needs-anchor` দেয়। `comp_cases`-এ পাঁচটা n-মান থেকে complexity। সব assert পাস হলে শেষে print: `সব test pass!`। (মনে রেখো: এটা একটা teaching harness — সত্যিকারের problem-এ এই rule-গুলো শুধু shortlist দেয়, doctrine-এর বদলি নয়।)
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
`classify` ও `target_complexity` দুটোই **O(1)** (constant কয়েকটা string-check)। মূল শিক্ষা অবশ্য picked problem-এর complexity আন্দাজ করা — যা family-অনুযায়ী O(n) থেকে O(n·2^n) পর্যন্ত।
### অতিরিক্ত জায়গা {#19-space-complexity}
harness-টা **O(1)** auxiliary। আসল DP-র space family-অনুযায়ী — 1D-তে O(n) (বা O(1)), grid/string-এ O(n·m), bitmask-এ O(2^n)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- statement পুরো না বুঝে family-তে commit করা — guess লেখো, কিন্তু doctrine দিয়ে যাচাই করো; trigger word মাঝে মাঝে বিভ্রান্ত করে।
- constraint উপেক্ষা করা — একই trigger word ছোট/বড় n-এ আলাদা family চায় (ছোট n হলে bitmask, বড় হলে greedy/অন্য কিছু)।
- কোনো family না মিললে হাল ছাড়া — সেটাই সংকেত যে state-এ একটা creative anchor বা extra dimension লাগবে (LIS-এর শিক্ষা)।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: পুরো folder। [../patterns.md](../patterns.md)-এর family-spotting table আর [../state-transition-thinking.md](../state-transition-thinking.md)-এর 5-step doctrine — এই দুটোই এই capstone-এর মেরুদণ্ড; classifier-টা ওই table-এরই code-রূপ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Codeforces-এর "dp" tag, rating 1700–2000 —