Problem link ও উৎস
- **Original source:** Counting DP (Catalan via balanced brackets)
- **Platform:** CSES Bracket Sequences I (সম্পর্কিত অনুশীলন) —
- **Topic:** Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
- **Difficulty:** Hard
- **Pattern:** counting DP (state = সারাংশ, মান = উপায়সংখ্যা)
- **Basic idea inherited from:** 049 (Catalan), 042 (Pascal's triangle)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n` জোড়া bracket দিয়ে কতগুলো **valid** (সঠিকভাবে মেলানো) sequence বানানো যায়? "Valid" মানে — প্রতিটা খোলা bracket-এর জন্য পরে একটা বন্ধ bracket আছে, আর কোনো prefix-এ বন্ধ bracket খোলার চেয়ে বেশি নেই।
উদাহরণ: `n = 3` জোড়া। উত্তর 5 — `((()))`, `(()())`, `(())()`, `()(())`, `()()()`। (`n = 1` → 1, `n = 2` → 2)।
এই সংখ্যাগুলোই বিখ্যাত **Catalan number** (1, 2, 5, 14, 42, ...)। আমরা এগুলো বের করব **counting DP**-তে: state = "এ পর্যন্ত কয়টা খোলা bracket অমীমাংসিত", মান = "সেই অবস্থায় কয় উপায়ে পৌঁছানো গেল"।
> এটা CP-leaning level। Interview-পথে থাকলে এই counting-DP idea-টা শিখে রাখো (DP topic [DP অধ্যায়](../../../12-dynamic-programming/README.md)-এ পূর্ণ রূপ); বাকি CP-material পরে।
### বাইরের অনুশীলনের সঙ্গে সম্পর্ক {#_1}
এই নোটে n মানে bracket-এর জোড়াসংখ্যা, আর ছোট input-এ O(n²) DP শেখানো হয়েছে। [CSES Bracket Sequences I](https://cses.fi/problemset/task/2064/)-এ n হলো মোট দৈর্ঘ্য, সীমা 10⁶ এবং উত্তর modulo 10⁹+7। তাই সেখানে এই DP সরাসরি যথেষ্ট দ্রুত নয়; n odd হলে 0, নইলে Catalan-এর factorial ও modular inverse পদ্ধতি ব্যবহার করতে হবে।
### Input ও output {#6-example-input-and-output}
```text
n valid bracket sequence Catalan
-------------------------------------------
1 1 ()
2 2 (()), ()()
3 5 ((())) সহ 5টা
4 14
5 42
6 132
closed form যাচাই: C(2n,n)/(n+1)
n=3: C(6,3)/4 = 20/4 = 5 ✓
```
মূল edge case: `n = 0` হলে 1 (খালি sequence শূন্যভাবে valid); আর সংখ্যাগুলো দ্রুত বাড়ে — বড় `n`-এ mod 10⁹+7 লাগে।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি ধাপে ধাপে একটা টাওয়ার বানাচ্ছ, আর প্রতি মুহূর্তে শুধু একটা সংখ্যা মনে রাখছ — "এই মুহূর্তে কতগুলো ব্লক ভারসাম্যহীন ঝুলছে (অমীমাংসিত খোলা bracket)"। পুরো টাওয়ারটা কেমন দেখতে সেটা মনে রাখার দরকার নেই — শুধু এই একটা সংখ্যাই ভবিষ্যৎ সিদ্ধান্তের জন্য যথেষ্ট।
প্রতি ধাপে দুটো পথ: নতুন একটা ঝুলন্ত ব্লক যোগ করো (`(`), বা একটা ঝুলন্ত ব্লক মীমাংসা করো (`)`)। অনেক ভিন্ন টাওয়ার একই "ঝুলন্ত সংখ্যা"-য় থাকতে পারে — তাই আমরা সেই সংখ্যা অনুযায়ী "কয় উপায়ে এখানে এলাম" জমাই। শেষে সব ঝুলন্ত ব্লক মীমাংসিত (0 খোলা) — কয় উপায়ে সেখানে পৌঁছানো গেল, সেটাই উত্তর।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
দুই শিকড়: **Catalan** (049) আর **Pascal's triangle** (042)। 049 থেকে এসেছে balanced bracket / Catalan-এর ধারণা — হয়তো সেখানে closed-form (`C(2n,n)/(n+1)`) বা recurrence দিয়ে শিখেছিলে। 042 থেকে এসেছে "প্রতি ঘর = আগের ঘরগুলোর যোগ" — DP-তে উপায়সংখ্যা জমানোর মূল চাল।
নতুন idea: Catalan-কে একটা **explicit counting DP**-তে ফেলা — state হিসেবে "অমীমাংসিত খোলা bracket"। এই state-নির্বাচন (পুরো sequence নয়, শুধু "কয়টা খোলা") counting DP-র মূল শিল্প। তাই এটা 049 আর 042-এর মিলন, DP-র চশমায়।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল ধারণা **counting DP** — "কয় উপায়ে" প্রশ্নকে state + যোগে ভাঙা:
```text
state = এ পর্যন্ত যা বানিয়েছি তার সারাংশ (পুরো history নয়!)
মান = সেই state-এ পৌঁছানোর মোট উপায়সংখ্যা
transition = প্রতিটা সম্ভাব্য পরের পদক্ষেপে উপায়সংখ্যা যোগ করে ছড়াও
```
Bracket-এ state = এখন কয়টা bracket খোলা (অমীমাংসিত)। প্রতি ধাপে দুই পদক্ষেপ: `(` বসাও (খোলা +1, যদি `n`-এর বেশি না হয়) বা `)` বসাও (খোলা −1, যদি negative না হয়)। পেছনে আছে একই গণিত যা Pascal-এ ছিল — প্রতিটা ঘরে আগত পথের যোগফল; আর শেষে যা পাই তা Catalan number।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
DP না ভেবে — সব সম্ভাব্য `(`/`)`-ক্রম enumerate করো (`2^(2n)`টা), প্রতিটা valid কিনা চেক করো:
```python
from itertools import product
def count_balanced_brute(n):
count = 0
for seq in product("()", repeat=2 * n): # সব 2^(2n) ক্রম
balance = 0
ok = True
for ch in seq:
balance += 1 if ch == "(" else -1
if balance < 0: # বন্ধ বেশি -> invalid
ok = False
break
if ok and balance == 0: # শেষে সব মীমাংসিত
count += 1
return count
```
এটা সংজ্ঞার হুবহু — ঠিক উত্তর দেয় (`count_balanced_brute(3)` → 5)। আর DP যাচাইয়ের নিখুঁত মাপকাঠি। কিন্তু `2^(2n)` ক্রম — দ্রুত অসম্ভব।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
ক্রম-সংখ্যা `2^(2n) = 4^n` — exponential:
```text
n = 5 -> 4^5 = 1024 (ঠিক আছে)
n = 12 -> 4^12 ≈ 1.6 কোটি (ধীর)
n = 20 -> 4^20 ≈ 10^12 (অসম্ভব)
counting DP: প্রতি ধাপে ≤ (n+1)টা state, 2n ধাপ -> O(n²)
```
মূল সমস্যা — হাজারো ভিন্ন prefix একই "খোলা সংখ্যা"-য় এসে মেলে; তাদের আলাদা গোনা অপচয়। DP সেগুলোকে এক state-এ জমিয়ে exponential থেকে polynomial-এ নামায়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: পুরো sequence মনে রাখার দরকার নেই — শুধু "এখন কয়টা bracket খোলা (অমীমাংসিত)" যথেষ্ট। এটাই state।
```text
dp[open] = এই মুহূর্তে 'open'-টা bracket খোলা, কয় উপায়ে এলাম
2n ধাপ চালাও, প্রতি ধাপে:
'(' বসাও: open + 1 (যদি ≤ n) -> new[open+1] += dp[open]
')' বসাও: open − 1 (যদি ≥ 0) -> new[open−1] += dp[open]
শেষে dp[0] = উত্তর (সব মীমাংসিত)
```
`4^n` ক্রম-এর বদলে `2n` ধাপ × `(n+1)` state = `O(n²)`। একই open-count-এর সব prefix এক cell-এ মেলে — এটাই counting DP-র সাশ্রয়।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
এক লাইনের "আহা": **"কয় উপায়ে" প্রশ্ন দেখলেই ভাবো — state কী হবে যেটা পুরো history-র বদলে শুধু "ভবিষ্যৎ সিদ্ধান্তে যা দরকার" তা ধরে? সেই state-এ উপায়সংখ্যা জমাও, transition-এ যোগ করো।**
সবচেয়ে বড় শিল্প — **সঠিক state বাছা**। এখানে "কয়টা খোলা bracket" যথেষ্ট, পুরো sequence নয়; এই সারাংশ-চিন্তাই counting DP-র প্রাণ (concept-notes section 11)। আর বড় `n`-এ mod 10⁹+7 প্রায় সবসময় সঙ্গী — সংখ্যা বিস্ফোরক হয়।
### ছবিতে বোঝা {#5-visual-explanation}
Counting DP-র state ছড়ানো (`n = 2`, dp[খোলা bracket] = উপায়সংখ্যা):
```text
দৈর্ঘ্য 2n = 4, প্রতি ধাপে: '(' -> খোলা+1, ')' -> খোলা−1
খোলা: 0 1 2
শুরু: [1]
| \
ধাপ 1: [0, 1] শুধু '(' বসানো যায় (খোলা 0 -> 1)
| \ |
ধাপ 2: [1, 0, 1]? -> আসলে: '((' -> খোলা2, '()' -> খোলা0
প্রকৃত: খোলা0:1, খোলা2:1 (dp = {0:1, 2:1})
...
ধাপ 3: dp = {1: 2} (( -> ) -> খোলা1; () -> ( -> খোলা1
ধাপ 4: dp = {0: 2} খোলা1 -> ) -> খোলা0
উত্তর = dp[0] = 2 (sequences: (()) আর ()())... আসলে n=2: (()) , ()() ✓
প্রতি ঘর <- (পূর্বের খোলা−1, '(' বসিয়ে) + (পূর্বের খোলা+1, ')' বসিয়ে)
n=1..6: dp[0] = 1, 2, 5, 14, 42, 132 -> Catalan!
```
লক্ষ করো — আমরা পুরো sequence রাখিনি, শুধু "কয়টা খোলা"-র উপর উপায়সংখ্যা জমিয়েছি।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`n = 2` জোড়া bracket — counting DP হাতে চালাই (`dp[open] = উপায়`):
1. **শুরু:** `dp = {0: 1}` (কিছু বসাইনি, 0 খোলা, 1 উপায়)।
2. **ধাপ 1:** open=0 থেকে: `(` → open 1 (`new[1] += 1`); `)` → open −1, বাদ। `dp = {1: 1}`।
3. **ধাপ 2:** open=1 থেকে: `(` → open 2 (`new[2] += 1`); `)` → open 0 (`new[0] += 1`)। `dp = {2: 1, 0: 1}`।
4. **ধাপ 3:** open=2: `)` → open 1 (`new[1] += 1`); `(` বাদ (n-এর বেশি)। open=0: `(` → open 1 (`new[1] += 1`)। `dp = {1: 2}`।
5. **ধাপ 4:** open=1: `)` → open 0 (`new[0] += 2`)। `dp = {0: 2}`।
6. **শেষ:** `dp[0] = 2` — 2টা valid sequence (`(())`, `()()`)। ✓ Catalan(2) = 2।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def count_balanced(n):
"""n জোড়া bracket-এর valid sequence সংখ্যা — counting DP-তে।"""
dp = {0: 1} # dp[open] = কয় উপায়ে open-টা খোলা
for _ in range(2 * n):
new = {}
for open_cnt, ways in dp.items():
if open_cnt + 1 <= n: # '(' বসাও (খোলা বাড়ে)
new[open_cnt + 1] = new.get(open_cnt + 1, 0) + ways
if open_cnt - 1 >= 0: # ')' বসাও (খোলা কমে)
new[open_cnt - 1] = new.get(open_cnt - 1, 0) + ways
dp = new
return dp.get(0, 0) # শেষে সব মীমাংসিত
from itertools import product
def count_balanced_brute(n):
"""সব 2^(2n) ক্রম enumerate — যাচাইয়ের জন্য।"""
count = 0
for seq in product("()", repeat=2 * n):
bal = 0
ok = True
for ch in seq:
bal += 1 if ch == "(" else -1
if bal < 0:
ok = False
break
if ok and bal == 0:
count += 1
return count
def catalan_closed_form(n):
"""C(2n,n)/(n+1) — স্বাধীন যাচাই।"""
from math import comb
return comb(2 * n, n) // (n + 1)
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert [count_balanced(n) for n in range(7)] == [1, 1, 2, 5, 14, 42, 132]
# brute force-এর সাথে মিল (DP সঠিক কিনা)
for n in range(7):
assert count_balanced(n) == count_balanced_brute(n), n
# Catalan closed form-এর সাথে মিল (তৃতীয় স্বাধীন পথ)
for n in range(9):
assert count_balanced(n) == catalan_closed_form(n), n
print([count_balanced(n) for n in range(1, 7)]) # [1, 2, 5, 14, 42, 132]
print(count_balanced(5)) # 42
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
dp = {0: 1}
```
শুরুর state: কিছু বসাইনি, তাই 0টা খোলা bracket, আর সেখানে 1 উপায়ে এসেছি। `dp[open]` = "এই মুহূর্তে open-টা খোলা, কয় উপায়ে"।
```text
if open_cnt + 1 <= n:
new[open_cnt + 1] = new.get(open_cnt + 1, 0) + ways
if open_cnt - 1 >= 0:
new[open_cnt - 1] = new.get(open_cnt - 1, 0) + ways
```
এটাই DP transition। প্রতিটা বর্তমান state থেকে দুই পদক্ষেপ: `(` বসালে খোলা +1 (যদি `n`-এর বেশি না হয় — মোট `n` জোড়া), `)` বসালে খোলা −1 (যদি negative না হয় — বন্ধ বেশি হলে invalid)। উভয় ক্ষেত্রে `ways` যোগ হয়ে নতুন state-এ জমে।
```text
return dp.get(0, 0)
```
`2n` পদক্ষেপ শেষে valid sequence-এর সব bracket মীমাংসিত — মানে 0 খোলা। `dp[0]`-ই মোট উপায়সংখ্যা।
বাকি `count_balanced_brute` সব ক্রম গোনে (যাচাইয়ের জন্য), `catalan_closed_form` স্বাধীন সূত্র, আর `assert` গুলো তিনভাবে মিলিয়ে দেখে: DP, brute force, closed form। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
[1, 2, 5, 14, 42, 132]
42
সব test pass!
```
প্রথম লাইন `n = 1..6`-এর valid sequence সংখ্যা — Catalan number। দ্বিতীয় `n = 5` → 42। তার আগের সব `assert` চুপচাপ pass — counting DP, brute force, আর Catalan closed form তিনটাই একমত। সবশেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n²)** — `2n`টা পদক্ষেপ, প্রতিটায় সর্বোচ্চ `(n+1)`টা state ছড়ানো। brute force ছিল `O(4^n · n)` (exponential) — DP সেটাকে polynomial-এ নামিয়েছে। (Catalan-এর closed-form `O(n)`-এও পাওয়া যায়, কিন্তু DP-চিন্তা সাধারণ — অন্য counting problem-এও খাটে।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(n)** — প্রতি ধাপে `dp` dictionary-তে সর্বোচ্চ `(n+1)`টা state। পুরো `4^n` ক্রম কখনো রাখি না — এটাই DP-র সাশ্রয়। (দুটো স্তর — `dp` আর `new` — রাখলেও `O(n)`।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **ভুল state বাছা** — পুরো sequence state-এ রাখলে আবার exponential; "কয়টা খোলা" এই সারাংশই যথেষ্ট (counting DP-র মূল শিল্প)।
2. **Boundary ভুলে যাওয়া** — `(` বসাতে `open+1 ≤ n`, `)` বসাতে `open ≥ 1`; না মানলে invalid sequence গোনা হয়।
3. **mod ভুলে যাওয়া** — Catalan দ্রুত বিশাল; বড় `n`-এ প্রতি যোগে `% (10⁹+7)` না নিলে overflow/ভুল।
4. **`n = 0` ভুল** — খালি sequence শূন্যভাবে valid, তাই `count_balanced(0) = 1`; 0 ভাবলে base ভুল।
5. **In-place আপডেট** — একই dict-এ লিখলে এক ধাপের মান পরের state দূষিত করে; আলাদা `new` লাগে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Counting Problems** (