Problem link ও উৎস
- **Original source:** CP-Algorithms — Sprague-Grundy theorem & Nim (game theory basics)
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
- **Difficulty:** Medium
- **Pattern:** W/L labeling (backward DP over game states)
- **Basic idea inherited from:** — (game theory-র শিকড়; নতুন শাখা)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুই player পালা করে চাল দেয়। একটা সাধারণ game ধরি: একটা স্তূপে `n`টা পাথর; প্রতি চালে যে কেউ 1, 2 বা 3টা পাথর নিতে পারে। যে আর চাল দিতে **পারে না** (অর্থাৎ পাথর শেষ, `n = 0`-তে তার পালা) সে **হারে** (এটাকে বলে normal play)।
দুজনেই নিখুঁত খেলে। জিজ্ঞেস: শুরুতে `n` পাথর থাকলে **প্রথম player জিতবে কি**?
এর উত্তর শুধু "হ্যাঁ/না" নয় — আমরা প্রতিটা `n`-এর জন্য ট্যাগ বসাব: **W** (এখান থেকে যার চাল সে জেতে) বা **L** (এখান থেকে যার চাল সে হারে)। এই W/L-চিন্তাই game theory-র ভিত্তি।
> এটা CP-leaning level। Interview-পথে থাকলে এড়িয়ে মূল DS topic-এ যেতে পারো; পরে ফিরে এলে এই recursive W/L-চিন্তা ভালো লাগবে।
### Input ও output {#6-example-input-and-output}
```text
n প্রথম player কারণ
--------------------------------------------------
0 হারে (L) চাল-ই নেই
1 জেতে (W) 1 নিয়ে 0 (L) এ ফেলে
3 জেতে (W) 3 নিয়ে 0 (L) এ ফেলে
4 হারে (L) যা-ই নাও (1/2/3), opponent বাকিটা শেষ করে
8 হারে (L) 4-এর গুণিতক
7 জেতে (W) 3 নিয়ে 4 (L) এ ফেলে
```
মূল edge case: **n = 0** হলো base — সেখানে যার পালা সে হেরে গেছে (L)। আর pattern: **`n % 4 == 0` মানেই L**, বাকি সব W।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা সিঁড়ি খেলা: তুমি আর বন্ধু পালা করে কিছু ধাপ নিচে নামো। যে নিচে পৌঁছাতে পারে (বা যে আটকে যায়) — তার ভাগ্য খেলার নিয়মে ঠিক।
কে জিতবে বুঝতে তুমি **শেষ থেকে** ভাবো: "যদি আমি একদম শেষ ধাপে আটকে থাকি, আমি হারলাম (L)।" তারপর এক ধাপ পেছনে: "এখান থেকে কি এমন একটা চাল আছে যা বন্ধুকে ওই হারা-অবস্থায় ফেলবে? থাকলে আমি জিতি (W)।" এভাবে পেছন থেকে প্রতিটা ধাপে "আমি এখানে থাকলে জিতি না হারি" লিখে ফেলো — শুরুর ধাপে পৌঁছালেই উত্তর।
মূল কথা: **locally ভালো চাল মানেই জেতা নয়** — জেতা মানে opponent-কে হারা-অবস্থায় ঠেলে দেওয়া।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা game theory-র একদম শিকড় (তাই inherited from: —)। তবে কৌশলটা চেনা: এটা আসলে একটা **DP over states**, পেছন থেকে ভরা। ছোট `n` থেকে বড় `n`-এর দিকে table ভরি, প্রতিটা cell-এর মান আগের cell-গুলোর উপর নির্ভর করে — ঠিক যেমন Fibonacci বা coin-change DP।
নতুন যেটা শিখছি: cell-এ সংখ্যা না রেখে **W/L** রাখা, আর transition-এ "any/all" যুক্তি (`W ⟺ অন্তত একটা চাল L-এ যায়`)। এই W/L table-ই পরের দুটো problem-এর (Nim, Grundy) ভিত্তি — 142-এ এই table থেকে XOR pattern বেরোবে, 143-এ W/L-এর জায়গায় আসবে Grundy সংখ্যা।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল ধারণা **backward induction** — শেষ অবস্থা থেকে পেছনে হেঁটে প্রতিটা position-এ W/L ঠিক করা। দুটো নিয়ম সব impartial game-এ একই:
- একটা position **L** (losing): তার **সব** চাল গিয়ে পড়ে W position-এ (যেদিকেই যাও, opponent জেতে)।
- একটা position **W** (winning): **অন্তত একটা** চাল আছে যা গিয়ে পড়ে L position-এ (opponent-কে ফাঁদে ফেলা যায়)।
ভিত্তি (base): যে position থেকে কোনো চাল-ই নেই (`n = 0`) — সেখানে যার পালা সে হেরে গেছে, তাই সেটা **L**।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সোজা ভাবনা: recursion দিয়ে সরাসরি "এই position থেকে কি জেতা যায়?" জিজ্ঞেস করা। একটা position W যদি কোনো চালে opponent-কে L-এ ফেলা যায়:
```python
def win_brute(n, moves=(1, 2, 3)):
if n == 0:
return False # চাল নেই -> হার (L)
for m in moves:
if n >= m and not win_brute(n - m, moves):
return True # opponent-কে L-এ ফেললাম -> W
return False # সব চাল W-তে যায় -> L
```
এটা definition-এর হুবহু অনুবাদ — ঠিক উত্তর দেয়। `win_brute(4)` → False (L), `win_brute(5)` → True (W)।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সমস্যা — memoization ছাড়া এই recursion একই position বারবার গোনে। `win(n)` ডাকে `win(n-1), win(n-2), win(n-3)`, যাদের প্রত্যেকে আবার নিচের গুলো — গাছটা exponentially ছড়ায় (Fibonacci-র মতো)।
```text
n = 40 (memo ছাড়া) -> প্রায় 3^40 / ... টা call — অসম্ভব ধীর
memo / DP দিয়ে -> প্রতিটা n একবার, O(n · |moves|) — দ্রুত
```
মূল শিক্ষা: game state গুলো একে অপরের সাথে overlap করে, তাই প্রতিটা একবার গোনাই যথেষ্ট — DP।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: position গুলো সীমিত (`0` থেকে `n`), তাই পেছন থেকে একটা table-এ প্রতিটার W/L একবার করে ভরে ফেলো। `win[0] = False` (base) থেকে শুরু করে বড় `n`-এর দিকে:
```text
win[k] = True যদি কোনো move m-এ win[k - m] == False (opponent L-এ)
= False অন্যথায়
```
এটা `O(n · |moves|)` — দ্রুত আর নির্ভুল। আর table ভরার পর একটা **bonus**: pattern চোখে পড়ে (`n % 4 == 0` → L), যা থেকে `O(1)` সূত্রও বেরোয়।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
এক লাইনের "আহা": **"আমি কি জিতব?" প্রশ্নটা উল্টে দাও — "এমন কি একটা চাল আছে যা opponent-কে হারা-অবস্থায় ফেলে?"** থাকলে W, না থাকলে L।
আর সবচেয়ে শক্তিশালী tweak: ছোট case-এ W/L table হাতে ভরো → pattern খোঁজো → প্রমাণ করো → `O(1)` সূত্র। পেছন-থেকে-label শুধু উত্তর দেয় না, **pattern আবিষ্কার করিয়ে দেয়** (এই game-এ `n % 4 == 0` → L)। ফাঁদ: "greedy চাল = জেতা" ভাবা ভুল (concept-notes mistake #3) — locally বেশি পাথর নেওয়া মানেই জেতা নয়।
### ছবিতে বোঝা {#5-visual-explanation}
পেছন থেকে W/L ভরা (`n` পাথর, নেওয়া যায় 1/2/3):
```text
n: 0 1 2 3 4 5 6 7 8
L W W W L W W W L
^ ^ ^
base (চাল নেই) 4-এর গুণিতকে L
কীভাবে ভরলাম (তীর = কোন চালে কোথায় যায়):
n=0 : চাল নেই -> L (base)
n=1 : 1 নিলে -> 0 (L) -> W (অন্তত একটা L-এ যায়)
n=2 : 1->1(W) 2->0(L) -> W
n=3 : 1->2(W) 2->1(W) 3->0(L) -> W
n=4 : 1->3(W) 2->2(W) 3->1(W) -> সব W -> L !
n=5 : 1->4(L) ... -> W (4=L এ ফেলতে পারি)
pattern ফুটে উঠল: n % 4 == 0 <=> L
```
লক্ষ করো — `n = 4`-এ সব চাল W-তে যায়, তাই L; আর 4-এর প্রতিটা গুণিতকে এটাই ঘটে।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`n = 5` পর্যন্ত table ভরি (moves = 1, 2, 3):
1. `win[0] = False` — base, চাল নেই → L।
2. `win[1]`: চাল 1 → `win[0] = False` (L)। অন্তত একটা L পেলাম → **W**।
3. `win[2]`: 1→`win[1]=W`, 2→`win[0]=L`। L পেলাম → **W**।
4. `win[3]`: 1→`win[2]=W`, 2→`win[1]=W`, 3→`win[0]=L`। L পেলাম → **W**।
5. `win[4]`: 1→`win[3]=W`, 2→`win[2]=W`, 3→`win[1]=W`। সব W, কোনো L নেই → **L**!
6. `win[5]`: 1→`win[4]=L`। L পেলাম → **W**।
ফল: `[L, W, W, W, L, W]`। `n=4`-এ L — pattern `n % 4 == 0` শুরু।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def label_win_lose(N, moves=(1, 2, 3)):
"""0..N প্রতিটা position-এ W (True) / L (False) ট্যাগ ফেরত দেয়।"""
win = [False] * (N + 1) # win[0] = False: চাল নেই, হার (L)
for n in range(1, N + 1):
# কোনো move m কি opponent-কে L position-এ ফেলে?
win[n] = any(n >= m and not win[n - m] for m in moves)
return win
def first_player_wins(n, moves=(1, 2, 3)):
"""একটা n-এ প্রথম player জেতে কি না।"""
return label_win_lose(n, moves)[n]
def win_brute(n, moves=(1, 2, 3)):
"""memo-হীন সরল recursion — মিলিয়ে দেখার জন্য।"""
if n == 0:
return False
return any(n >= m and not win_brute(n - m, moves) for m in moves)
# --- ছোট test গুলো (সব pass করা উচিত) ---
labels = label_win_lose(12)
# n % 4 == 0 হলে L (False), নাহলে W (True)
for n in range(13):
assert labels[n] == (n % 4 != 0), n
# brute force-এর সাথে মিল (definition নিজেই ঠিক কিনা)
for n in range(15):
assert first_player_wins(n) == win_brute(n), n
# অন্য move set: শুধু {1, 2} -> pattern n % 3 == 0 -> L
lab2 = label_win_lose(12, moves=(1, 2))
for n in range(13):
assert lab2[n] == (n % 3 != 0), n
print([("L", "W")[w] for w in labels]) # ['L','W','W','W','L',...]
print(first_player_wins(4)) # False (L)
print(first_player_wins(7)) # True (W)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
win = [False] * (N + 1)
```
`win[n]` রাখবে position `n`-এ যার পালা সে জেতে কিনা। শুরুতে সব False; বিশেষভাবে `win[0] = False` — base case, চাল নেই মানে হার (L)।
```text
win[n] = any(n >= m and not win[n - m] for m in moves)
```
এটাই হৃদয়। প্রতিটা সম্ভাব্য চাল `m`-এর জন্য দেখি: `m` নেওয়া গেলে (`n >= m`) opponent পড়ে `win[n - m]` position-এ; সেটা যদি **L** (`not win[n-m]`) হয়, তবে আমি জিতি। `any(...)` মানে "অন্তত একটা এমন চাল আছে?" — থাকলেই W।
```text
def first_player_wins(n, moves=(1, 2, 3)):
return label_win_lose(n, moves)[n]
```
পুরো table ভরে শুধু `n`-এর ঘরটা ফেরত — একটা নির্দিষ্ট প্রশ্নের সরাসরি উত্তর।
বাকি `win_brute` definition-এর সরল recursion, আর `assert` গুলো তিনভাবে যাচাই করছে: (১) `n % 4` pattern, (২) brute force-এর সাথে মিল, (৩) ভিন্ন move set-এ `n % 3` pattern। সব মিললে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
['L', 'W', 'W', 'W', 'L', 'W', 'W', 'W', 'L', 'W', 'W', 'W', 'L']
False
True
সব test pass!
```
প্রথম লাইন `n = 0..12`-এর W/L — 0, 4, 8, 12-এ L (`n % 4 == 0`)। দ্বিতীয় লাইন `n=4` → False (প্রথম player হারে)। তৃতীয় `n=7` → True (জেতে)। তার আগের `assert` গুলো চুপচাপ pass করেছে। সবশেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(N · |moves|)** — table-এর প্রতিটা ঘর (`N+1`টা) ভরতে প্রতিটা move দেখা (`|moves|`টা)। উপরের game-এ moves মাত্র 3টা, তাই কার্যত `O(N)`। আর pattern (`n % 4`) ধরা পড়লে `O(1)` সূত্রও বেরোয়।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(N)** — `win` array-টা `N+1` ঘরের। চাইলে শুধু শেষ কয়েকটা ঘর রেখে `O(|moves|)`-এও নামানো যায় (যেহেতু `win[n]` কেবল আগের কয়েকটা ঘর দেখে), কিন্তু পুরো table থাকলে pattern খুঁজতে সুবিধা।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **Greedy চাল = জেতা ভাবা** — locally ভালো চাল মানেই জেতা নয়; W/L recursive (concept-notes mistake #3)।
2. **Base case ভুল** — `win[0]` হলো L (চাল নেই = হার, normal play); এটাকে W ভাবলে পুরো table উল্টে যায়।
3. **"any" আর "all" গুলিয়ে ফেলা** — W ⟺ অন্তত একটা চাল L-এ (any); L ⟺ সব চাল W-তে (all)। উল্টে ফেললে সব ভুল।
4. **Misère variant গুলিয়ে ফেলা** — "শেষ পাথর নিলে হার" (misère) আলাদা নিয়ম; এখানে normal play (চাল না দিতে পারলে হার)।
5. **Memo ছাড়া recursion** — exponential হয়ে TLE; DP/memo লাগবেই।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CP-Algorithms — Sprague-Grundy & Nim** (