Problem link ও উৎস
- **Original source:** Classic CP probability-DP pattern (coin/dice state DP)
- **Platform:** Classic CP pattern (AtCoder Educational DP Contest — I: Coins (সম্পর্কিত অনুশীলন) —
)
- **Topic:** Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
- **Difficulty:** Hard
- **Pattern:** probability state (DP-তে সম্ভাবনা বওয়া)
- **Basic idea inherited from:** 144 (Expected Value Problems)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা coin (head আসার সম্ভাবনা `p`) ঠিক `k` বার toss করা হলো। জিজ্ঞেস: **ঠিক `h` টা head** আসার সম্ভাবনা কত? আর বাড়িয়ে: প্রতিটা সম্ভাব্য head-সংখ্যার (0 থেকে `k`) সম্পূর্ণ সম্ভাবনা-তালিকা চাই।
উদাহরণ: ন্যায্য coin (`p = 0.5`), `k = 3` toss। উত্তর-তালিকা `[0.125, 0.375, 0.375, 0.125]` — মানে 0 head-এর সম্ভাবনা 0.125, 1 head-এর 0.375, এভাবে।
এটা একটা **probability DP**-র সরলতম রূপ: প্রতিটা toss-এর পর "এ পর্যন্ত কত head, আর সেই অবস্থায় পৌঁছানোর সম্ভাবনা কত" — এই তথ্যটা state-এ বয়ে নিয়ে যাওয়া।
> এটা CP-leaning level। Interview-পথে থাকলে এড়িয়ে মূল DS topic-এ যেতে পারো; DP শেখার পরে ([DP অধ্যায়](../../../12-dynamic-programming/README.md)) ফিরলে এটা প্রায় ফ্রি লাগবে।
### বাইরের অনুশীলনের সঙ্গে সম্পর্ক {#_1}
এই নোটে প্রতিবার একই p এবং ঠিক hটি head-এর probability বের করা হয়। [AtCoder I — Coins](https://atcoder.jp/contests/dp/tasks/dp_i)-এ প্রতিটি coin-এর p আলাদা এবং head-এর সংখ্যা tail-এর চেয়ে বেশি হওয়ার মোট probability চাই। একই DP কৌশল লাগে, কিন্তু transition-এ প্রতিটি coin-এর p নিয়ে শেষে উপযুক্ত state-গুলো যোগ করতে হবে।
### Input ও output {#6-example-input-and-output}
```text
k p সম্ভাবনা-তালিকা [0 head, 1, ..., k]
---------------------------------------------------------
3 0.5 [0.125, 0.375, 0.375, 0.125]
2 0.5 [0.25, 0.5, 0.25]
1 0.5 [0.5, 0.5]
4 0.3 [0.2401, 0.4116, 0.2646, 0.0756, 0.0081]
0 0.5 [1.0] (toss নেই -> 0 head নিশ্চিত)
```
দুটো জিনিস খেয়াল করো: যেকোনো সারির যোগফল **সবসময় 1** (sanity check); আর `k = 0` হলে শুধু `[1.0]` — কোনো toss নেই মানে 0 head নিশ্চিত।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা জলধারা পাহাড়ের চূড়া থেকে নামছে, পথে পথে দুই ভাগ হয়ে। চূড়ায় 1 লিটার (পুরো সম্ভাবনা)। প্রতিটা কাঁটায় জল ভাগ হয় — কোনো দিকে `p` অংশ, অন্য দিকে `1−p` অংশ।
প্রতিটা toss একটা কাঁটা: head-শাখায় `p` অংশ জল যায় (head-গণনা বাড়ে), tail-শাখায় `1−p` (গণনা একই)। কয়েক স্তর পরে নিচে কয়েকটা পাত্র — প্রতিটা একটা নির্দিষ্ট head-সংখ্যা। প্রতি পাত্রে কত জল জমল = সেই head-সংখ্যা আসার সম্ভাবনা। মোট জল সবসময় 1 লিটার থাকে — কারণ জল হারিয়ে যায় না, শুধু ভাগ হয়। এটাই probability DP।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
দাঁড়িয়ে আছে **expected value / probability** (problem 144)-এর উপর। 144-এ যখন সমস্যা সরল indicator-এ ভাঙা যেত, linearity যথেষ্ট ছিল — কোনো state লাগেনি। কিন্তু এখানে head-গণনা ধাপে ধাপে গড়ায়, প্রতিটা পরের ধাপ আগেরটার উপর নির্ভর — সরল ভাঙা যায় না। তাই 144-এর "ভাঙো-যোগ" বদলে এখানে "state-এ probability বইয়ে transition-এ ছড়াও"।
আর কাঠামোটা চেনা counting-DP-র (যেমন climbing stairs): cell-এ "কয় উপায়ে" রাখার বদলে এখানে "কত সম্ভাবনায়" রাখি, আর transition-এ যোগের জায়গায় probability-গুণ-করে-যোগ। তাই এটা একই সাথে 144 (probability) আর DP-চিন্তার মিলন।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল ধারণা **probability-কে DP state-এ বওয়া** — আর প্রতি ধাপে total probability ভাগ করে ছড়ানো:
```text
dp[h] = এ পর্যন্ত ঠিক h টা head পাওয়ার সম্ভাবনা
প্রতি toss-এ ছড়াও:
head এলে (সম্ভাবনা p): head-গণনা 1 বাড়ে -> dp[h] এর অংশ যায় new[h+1] এ
tail এলে (সম্ভাবনা 1-p): head-গণনা একই -> dp[h] এর অংশ যায় new[h] এ
```
পেছনে আছে **law of total probability**: একটা অবস্থায় পৌঁছানোর মোট সম্ভাবনা = তার দিকে আসা সব পথের সম্ভাবনার যোগ। DP ঠিক এটাই করে — প্রতি cell-এ সব আগত পথের probability জমায়। আর একটা ফ্রি sanity check: প্রতি ধাপে সব cell-এর যোগফল সবসময় 1।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
DP না ভেবে — সব সম্ভাব্য ফলাফল-ক্রম (sequence) enumerate করা। `k` toss-এর প্রতিটা head/tail হতে পারে, তাই `2^k` sequence; প্রতিটার সম্ভাবনা গুণে head গুনে যোগ করি:
```python
from itertools import product
def prob_heads_brute(k, p=0.5):
dist = [0.0] * (k + 1)
for seq in product((0, 1), repeat=k): # 0=tail, 1=head, সব 2^k ক্রম
h = sum(seq)
prob = 1.0
for x in seq:
prob *= p if x == 1 else (1 - p)
dist[h] += prob
return dist
```
এটা সংজ্ঞার হুবহু — ঠিক উত্তর দেয় (`k=3` → `[0.125, ...]`)। আর DP যাচাইয়ের নিখুঁত মাপকাঠি। কিন্তু `2^k` sequence — তাড়াতাড়ি অসম্ভব হয়ে ওঠে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
Sequence-সংখ্যা `2^k` — exponential:
```text
k = 10 -> 2^10 ≈ 1000 (ঠিক আছে)
k = 30 -> 2^30 ≈ 100 কোটি (ধীর)
k = 60 -> 2^60 (অসম্ভব)
DP: প্রতি ধাপে (k+1)টা cell, k ধাপ -> O(k²) — exponential থেকে polynomial!
```
মূল কথা — একই head-সংখ্যায় পৌঁছানো হাজারো ভিন্ন sequence-কে আলাদা গোনা অপচয়; তাদের শুধু **মোট সম্ভাবনা** দরকার, যেটা DP cell-এ একসাথে জমে।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: পুরো sequence মনে রাখার দরকার নেই — শুধু "এ পর্যন্ত কত head, আর সেই অবস্থার সম্ভাবনা কত" যথেষ্ট। এটাই state।
```text
dp[h] = এ পর্যন্ত ঠিক h head পাওয়ার সম্ভাবনা
প্রতি toss-এ:
new[h] += dp[h] · (1-p) # tail: head একই
new[h+1] += dp[h] · p # head: head বাড়ল
```
প্রতি ধাপে দুটো শাখায় probability ছড়িয়ে দিই। `2^k` sequence-এর বদলে `k` ধাপ × `(k+1)` cell = `O(k²)`। একই head-সংখ্যার সব পথ এক cell-এ মিশে যায় — এটাই DP-র সাশ্রয়।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
এক লাইনের "আহা": **পুরো random history মনে রেখো না — শুধু যেটুকু ভবিষ্যৎ সিদ্ধান্তে দরকার (এখানে "কত head") সেটাই state-এ রাখো, আর প্রতি ধাপে probability শাখায় শাখায় ছড়িয়ে দাও।**
সবচেয়ে কাজের অভ্যাস: **প্রতি ধাপে cell-গুলোর যোগফল 1 কিনা চেক করো** — এটা ফ্রি sanity check, transition ভুল হলে সাথে সাথে ধরা পড়ে (concept-notes section 7)। আর মনে রাখো — counting DP-তে cell-এ count, এখানে শুধু সেই count-এর জায়গায় probability; কাঠামো হুবহু এক।
### ছবিতে বোঝা {#5-visual-explanation}
DP table ধাপে ধাপে (ন্যায্য coin, প্রতি ধাপে head শাখায় ও tail শাখায় সমান ভাগ):
```text
dp[h] = এ পর্যন্ত h টা head; প্রতি ধাপে যোগফল 1
শুরু (0 toss): [1]
|
ভাগ p / (1-p)
toss 1 পরে: [0.5, 0.5] (0 head, 1 head)
| \ / |
toss 2 পরে: [0.25, 0.5, 0.25] (0, 1, 2 head)
| \ / \ / |
toss 3 পরে: [0.125, 0.375, 0.375, 0.125] (0,1,2,3 head)
প্রতি cell <- বাম-উপর (head এসে) × p + ঠিক-উপর (tail এসে) × (1-p)
যোগফল চেক: 0.125+0.375+0.375+0.125 = 1.0 ✓
```
এটা Pascal's triangle-এরই probability-রূপ — তাই উত্তর binomial: `C(k, h)·pʰ·(1−p)^(k−h)`।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`k = 2`, `p = 0.5` হাতে চালাই:
1. **শুরু:** `dp = [1.0]` (0 toss, 0 head নিশ্চিত)। আসলে আমরা `dp = [1, 0, 0]` ধরি (cell 0..k)।
2. **Toss 1:** cell 0-এর 1.0 ছড়ায় — tail → new[0] += 1.0×0.5 = 0.5; head → new[1] += 1.0×0.5 = 0.5। `dp = [0.5, 0.5, 0]`। যোগফল 1.0 ✓।
3. **Toss 2:**
- cell 0 (0.5): tail → new[0] += 0.25; head → new[1] += 0.25।
- cell 1 (0.5): tail → new[1] += 0.25; head → new[2] += 0.25।
- `dp = [0.25, 0.5, 0.25]`। যোগফল 1.0 ✓।
4. **শেষ:** `[0.25, 0.5, 0.25]` — 0 head 0.25, 1 head 0.5, 2 head 0.25। binomial-এর সাথে মেলে।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def prob_heads(k, p=0.5):
"""k বার toss-এ ঠিক h head-এর সম্ভাবনা — তালিকা dp[0..k] ফেরত।"""
dp = [1.0] + [0.0] * k # dp[h] = এ পর্যন্ত h head-এর সম্ভাবনা
for _ in range(k):
new = [0.0] * (k + 1)
for h in range(k + 1):
if dp[h] == 0.0:
continue
new[h] += dp[h] * (1 - p) # tail: head একই
if h + 1 <= k:
new[h + 1] += dp[h] * p # head: head বাড়ল
dp = new
return dp
from itertools import product
def prob_heads_brute(k, p=0.5):
"""সব 2^k sequence enumerate — DP যাচাইয়ের জন্য।"""
dist = [0.0] * (k + 1)
for seq in product((0, 1), repeat=k):
prob = 1.0
for x in seq:
prob *= p if x == 1 else (1 - p)
dist[sum(seq)] += prob
return dist
# --- ছোট test গুলো (সব pass করা উচিত) ---
d3 = prob_heads(3)
assert abs(sum(d3) - 1.0) < 1e-12 # যোগফল সবসময় 1
assert all(abs(a - b) < 1e-12 for a, b in
zip(d3, [0.125, 0.375, 0.375, 0.125]))
# binomial-এর সাথে মিল (closed form)
from math import comb
for k in range(7):
for p in (0.5, 0.3, 0.75):
dp = prob_heads(k, p)
for h in range(k + 1):
expected = comb(k, h) * p ** h * (1 - p) ** (k - h)
assert abs(dp[h] - expected) < 1e-12, (k, p, h)
# brute force-এর সাথে মিল
for k in range(0, 9):
for p in (0.5, 0.4):
dp = prob_heads(k, p)
bf = prob_heads_brute(k, p)
assert all(abs(a - b) < 1e-12 for a, b in zip(dp, bf)), (k, p)
print([round(x, 3) for x in prob_heads(3)]) # [0.125, 0.375, 0.375, 0.125]
print([round(x, 4) for x in prob_heads(4, 0.3)]) # [0.2401, 0.4116, ...]
print(round(sum(prob_heads(5, 0.6)), 10)) # 1.0
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
dp = [1.0] + [0.0] * k
```
শুরুর state: 0 toss-এ 0 head নিশ্চিত, তাই `dp[0] = 1.0`, বাকি সব 0। এই `dp[h]` মানে "এ পর্যন্ত ঠিক h head পাওয়ার সম্ভাবনা"।
```text
new[h] += dp[h] * (1 - p)
if h + 1 <= k:
new[h + 1] += dp[h] * p
```
এটাই DP transition। বর্তমান cell `dp[h]`-এর probability দুই শাখায় ছড়ায়: tail এলে (`1−p`) head একই থাকে → `new[h]`; head এলে (`p`) head বাড়ে → `new[h+1]`। সব আগত অংশ যোগ হয়ে নতুন cell-এর মোট probability।
```text
dp = new
```
এক toss-এর হিসাব শেষে `dp` আপডেট করে পরের toss-এ যাই।
বাকি `prob_heads_brute` সব sequence গোনে (যাচাইয়ের জন্য), আর `assert` গুলো তিনভাবে মিলিয়ে দেখে: (১) যোগফল 1, (২) binomial closed form, (৩) brute force। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
[0.125, 0.375, 0.375, 0.125]
[0.2401, 0.4116, 0.2646, 0.0756, 0.0081]
1.0
সব test pass!
```
প্রথম লাইন ন্যায্য coin 3 toss-এর head-distribution। দ্বিতীয় biased coin (`p=0.3`) 4 toss। তৃতীয় — যেকোনো distribution-এর যোগফল ঠিক 1.0 (sanity check)। তার আগের সব `assert` চুপচাপ pass — DP, binomial সূত্র, আর brute force তিনটাই একমত। সবশেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(k²)** — `k`টা toss, প্রতিটায় `(k+1)`টা cell ছড়ানো। brute force ছিল `O(2^k · k)` (exponential) — DP সেটাকে polynomial-এ নামিয়েছে। (একই head-সংখ্যার সব পথ এক cell-এ মেলায় বলে।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(k)** — শুধু একটা `dp` array (`k+1` ঘর), প্রতি ধাপে `new` দিয়ে আপডেট। পুরো `2^k` history কখনো রাখি না — এটাই DP-র মূল সাশ্রয়।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **যোগফল 1 চেক না করা** — transition ভুল হলে সবচেয়ে দ্রুত ধরা পড়ে cell-যোগফল ≠ 1 দেখে; এই ফ্রি check বাদ দিও না।
2. **head/tail-এ p আর 1−p উল্টে ফেলা** — head শাখায় `p`, tail শাখায় `1−p`; biased coin-এ উল্টে ফেললে distribution উল্টে যায়।
3. **Boundary (`h+1 <= k`) ভুলে যাওয়া** — সর্বোচ্চ head-এর cell থেকে আর head বাড়ানো যায় না; index error বা ভুল।
4. **Probability আর count গুলিয়ে ফেলা** — কাঠামো একই, কিন্তু probability-তে ভগ্নাংশ গুণ হয় (count-এ শুধু যোগ); float ব্যবহার করো।
5. **In-place আপডেট** — একই array-তে সরাসরি লিখলে এক toss-এর মান পরের cell-কে দূষিত করে; আলাদা `new` array লাগে (বা সাবধানী ক্রম)।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **AtCoder Educational DP Contest — I: Coins (সম্পর্কিত অনুশীলন) — Probability & Expected Value DP** (