Problem link ও উৎস
- **Original source:** Sprague-Grundy theorem (impartial games)
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
- **Difficulty:** Hard
- **Pattern:** mex + XOR (Grundy value, sum of games)
- **Basic idea inherited from:** 142 (Nim Game)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
142-এ Nim-এর রহস্য XOR-এ ধরা পড়েছিল। কিন্তু সব game তো Nim নয় — যেমন "এক স্তূপে `n` পাথর, প্রতি চালে 1 বা 2টা নেওয়া যায়"। এমন game-এ কে জেতে?
Sprague-Grundy theorem বলে: **যেকোনো impartial game-এর প্রতিটা position-কে একটা সংখ্যা দেওয়া যায় — তার Grundy number** — আর সেই সংখ্যাটা ঠিক Nim pile-এর মতো আচরণ করে। দুটো বড় কাজ:
- একটা position-এর Grundy 0 ⟺ সেটা **L** (হারা-অবস্থা)।
- **একাধিক স্বাধীন game একসাথে** চললে, মোট game জেতা যায় কি না — সব game-এর Grundy-র **XOR** দেখলেই বলা যায়।
> এটা CP-leaning level। Interview-পথে থাকলে এড়িয়ে মূল DS topic-এ যেতে পারো; পরে ফিরে এলে sum-of-games-এর জাদু আরও স্পষ্ট লাগবে।
### Input ও output {#6-example-input-and-output}
```text
এক স্তূপ, নেওয়া যায় {1, 2}:
n Grundy W/L
-----------------------
0 0 L
3 0 L
1 1 W
2 2 W
sum of two heaps (Grundy XOR):
heaps g_a ^ g_b প্রথম player
-----------------------------------------------------
[3, 3] g[3]^g[3]=0^0=0 হারে (L)
[1, 2] g[1]^g[2]=1^2=3≠0 জেতে (W)
[3, 5] g[3]^g[5]=0^2=2≠0 জেতে (W)
mex উদাহরণ:
mex({0,1,2}) = 3, mex({0,2}) = 1, mex({}) = 0
```
মূল edge case: **`mex({}) = 0`** — কোনো চাল না থাকলে Grundy 0 (হারা-অবস্থা); আর দুটো **সমান Grundy** XOR করলে 0 (L)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার সামনে কয়েকটা আলাদা আলাদা mini-game একসাথে চলছে (একটা দাবা-ধাঁচ, একটা পাথর-স্তূপ, একটা ধাঁধা) — প্রতি চালে তুমি যেকোনো **একটা** game-এ একটা চাল দাও। সব game-এ চাল ফুরোলে যে আটকায় সে হারে।
এত মিশ্র খেলা কীভাবে বিশ্লেষণ করবে? Grundy বলে: প্রতিটা mini-game-কে একটা "ওজন" (Grundy number) দাও — যেন প্রতিটা একটা Nim pile। তারপর সব ওজন XOR করো; ≠ 0 হলে তুমি জেতো। মানে যত আলাদা খেলাই হোক, প্রতিটাকে একটা সংখ্যায় অনুবাদ করে সব Nim-এ মিশিয়ে দেওয়া যায় — এটাই Grundy-র জাদু।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **Nim** (problem 142) থেকে। Nim-এ pile-এর আকারই ছিল তার "মান", আর XOR বলত কে জেতে। Grundy এটাকে সাধারণীকরণ করে: যেকোনো game-এর প্রতিটা position-এর একটা "Nim-সমতুল্য আকার" = তার Grundy number। তারপর Nim-এর সেই একই XOR rule খাটে।
আর 141-এর W/L labeling-ও আছে — Grundy আসলে W/L-এর **উন্নত রূপ**: W/L শুধু দুই মান (জিতি/হারি), Grundy দেয় পুরো সংখ্যা যা sum-of-games-এ XOR করা যায়। তাই trilogy: 141 (W/L) → 142 (Nim XOR) → 143 (Grundy = দুটোর মিলন ও সাধারণীকরণ)।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল ধারণা **mex (minimum excludant)** আর **XOR of games**:
```text
g(position) = mex { g(next) : next = এই position থেকে এক চালে যাওয়া যায় }
mex(S) = S-এ নেই এমন ক্ষুদ্রতম অঋণাত্মক integer
mex({0,1,3}) = 2, mex({}) = 0, mex({1,2}) = 0
```
`g = 0` মানে position L; `g > 0` মানে W। আর Sprague-Grundy-র মূল উপপাদ্য: একাধিক game যোগ করলে মোট Grundy = প্রতিটার Grundy-র **XOR** — এজন্যই Grundy-কে বলে "Nim-মুদ্রা": প্রতিটা game-কে সমতুল্য একটা Nim pile (যার আকার = তার Grundy) বানিয়ে XOR করো।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
XOR rule না জেনেও sum-of-games-এর W/L সরাসরি recursion-এ বের করা যায় — state = সব heap একসাথে:
```python
from functools import lru_cache
def two_heap_brute_win(a, b, moves=(1, 2)):
@lru_cache(maxsize=None)
def win(x, y):
nexts = []
for t in moves:
if x >= t:
nexts.append((x - t, y))
if y >= t:
nexts.append((x, y - t))
for ns in nexts:
if not win(*ns): # opponent L-এ
return True
return False
return win(a, b)
```
এটা definition-এর সরল রূপ — ঠিক উত্তর দেয়, আর Grundy-XOR rule যাচাইয়ের মাপকাঠি। কিন্তু heap বাড়লে state বিস্ফোরক।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
Sum-of-games-এ state হলো সব game-এর মিলিত অবস্থা — সংখ্যাটা গুণফলে বাড়ে:
```text
2 heap, প্রতিটা ≤ 1000 -> ~10^6 state (memo লাগবে)
5 heap, প্রতিটা ≤ 1000 -> ~10^15 state — অসম্ভব
Grundy: প্রতিটা game আলাদা O(M) তে precompute,
তারপর XOR -> মোট O(সব game-এর আকার) — গুণফল ভেঙে যোগফল!
```
মূল শিক্ষা: combined game-এর exponential state-কে Grundy ভেঙে দেয় — প্রতিটা game **আলাদা** বিশ্লেষণ করে শুধু XOR; গুণফল-জটিলতা যোগফল-জটিলতায় নামে।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight (Sprague-Grundy): প্রতিটা game আলাদাভাবে তার Grundy number বের করো (mex দিয়ে, পেছন থেকে), তারপর সব game-এর Grundy **XOR** করো:
```text
combined Grundy = g(game₁) XOR g(game₂) XOR ...
≠ 0 -> প্রথম player W; = 0 -> L
```
একটা game-এর Grundy বের করা মানে 141-এর মতোই backward fill — শুধু W/L-এর জায়গায় mex। আর sum-of-games-এ Nim-এর XOR rule সরাসরি খাটে কারণ প্রতিটা Grundy number একটা Nim pile-এর সমতুল্য।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
এক লাইনের "আহা": **যেকোনো impartial game = ছদ্মবেশী Nim — প্রতিটা position-কে তার mex-দিয়ে-পাওয়া Grundy সংখ্যায় অনুবাদ করো, তারপর একাধিক game XOR করে Nim-এর মতো খেলো।**
ফাঁদ: **mex ভুল করা** — mex মানে set-এ **নেই** এমন ক্ষুদ্রতম অঋণাত্মক integer; min নয়, max নয় (concept-notes mistake #5)। `mex({1,2,3}) = 0` (0 নেই!), `mex({0,1,2}) = 3`। আর Grundy = 0 ⟺ L — এই একটা সমীকরণ মনে রাখলেই W/L আর Grundy এক সুতোয় বাঁধা।
### ছবিতে বোঝা {#5-visual-explanation}
mex দিয়ে Grundy ভরা (n পাথর, নেওয়া যায় 1 বা 2):
```text
g[n] = mex { g[n-1], g[n-2] } (যতগুলো বৈধ)
n : 0 1 2 3 4 5 6
g : 0 1 2 0 1 2 0 <- period 3!
কীভাবে:
g[0] = mex {} = 0 (চাল নেই)
g[1] = mex {g[0]} = mex {0} = 1
g[2] = mex {g[1],g[0]} = mex {1,0} = 2
g[3] = mex {g[2],g[1]} = mex {2,1} = 0 <- L!
g[4] = mex {g[3],g[2]} = mex {0,2} = 1
g = 0 ঘরগুলো (n = 0, 3, 6, ...) = L position
sum of games (দুই স্তূপ a, b):
মোট Grundy = g[a] XOR g[b]
≠ 0 -> প্রথম player W
```
লক্ষ করো — mex মানে "set-এ যে সবচেয়ে ছোট অঋণাত্মক integer **নেই**"; min নয়, max নয়।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`n` পাথর, নেওয়া যায় {1, 2} — Grundy table ভরি, তারপর sum-of-games চেক:
1. `g[0] = mex {} = 0` — চাল নেই, L।
2. `g[1] = mex {g[0]} = mex {0} = 1` — W।
3. `g[2] = mex {g[1], g[0]} = mex {1, 0} = 2` — W।
4. `g[3] = mex {g[2], g[1]} = mex {2, 1} = 0` — L! (0, 1, 2 কেউ নেই বাদ দিয়ে... আসলে 0 set-এ নেই, তাই mex = 0)।
5. `g[4] = mex {g[3], g[2]} = mex {0, 2} = 1` — W। Pattern: `g[n] = n % 3`।
6. **sum-of-games `[1, 2]`:** combined Grundy = `g[1] ^ g[2]` = `1 ^ 2` = 3 ≠ 0 → প্রথম player **W**। (brute force-ও True বলে — মিলে গেল।)
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def mex(s):
"""s-এ নেই এমন ক্ষুদ্রতম অঋণাত্মক integer।"""
m = 0
while m in s:
m += 1
return m
def grundy_subtraction(N, moves=(1, 2)):
"""এক স্তূপ: 0..N প্রতিটার Grundy number (নেওয়া যায় moves থেকে)।"""
g = [0] * (N + 1)
for n in range(1, N + 1):
g[n] = mex({g[n - m] for m in moves if n >= m})
return g
def sum_of_games_wins(heaps, moves=(1, 2)):
"""একাধিক স্বাধীন স্তূপ — combined Grundy = XOR; ≠ 0 হলে W।"""
g = grundy_subtraction(max(heaps) if heaps else 0, moves)
x = 0
for h in heaps:
x ^= g[h]
return x != 0
from functools import lru_cache
def two_heap_brute_win(a, b, moves=(1, 2)):
"""দুই স্তূপ W/L সরাসরি — Grundy-XOR যাচাইয়ের জন্য।"""
@lru_cache(maxsize=None)
def win(x, y):
for t in moves:
if x >= t and not win(x - t, y):
return True
if y >= t and not win(x, y - t):
return True
return False
return win(a, b)
# --- ছোট test গুলো (সব pass করা উচিত) ---
g = grundy_subtraction(9)
for n in range(10):
assert g[n] == n % 3, n # {1,2}-game: Grundy period 3
assert mex({0, 1, 2}) == 3
assert mex({0, 2}) == 1
assert mex(set()) == 0
assert mex({1, 2, 3}) == 0 # 0 নেই -> mex 0
# Grundy = 0 ⟺ L: একক স্তূপে brute W/L-এর সাথে মিল
for n in range(10):
single_W = two_heap_brute_win(n, 0) # দ্বিতীয় heap খালি = একক game
assert single_W == (g[n] != 0), n # g লম্বা 0..9
# sum-of-games XOR rule brute force-এর সাথে মিল
import random
gg = grundy_subtraction(10)
for _ in range(300):
a, b = random.randint(0, 8), random.randint(0, 8)
pred = (gg[a] ^ gg[b]) != 0
assert pred == two_heap_brute_win(a, b), (a, b)
print(g) # [0,1,2,0,1,2,0,1,2,0]
print(sum_of_games_wins([1, 2])) # True (1^2=3≠0)
print(sum_of_games_wins([3, 3])) # False (0^0=0)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def mex(s):
m = 0
while m in s:
m += 1
return m
```
0 থেকে গুনি, set-এ যতক্ষণ আছে এগোই; প্রথম যেটা **নেই** সেটাই mex। `mex({0,1,3})` → 0 আছে, 1 আছে, 2 নেই → 2।
```text
g[n] = mex({g[n - m] for m in moves if n >= m})
```
position `n` থেকে এক চালে যেসব position-এ যাওয়া যায় (`n-1`, `n-2`), তাদের Grundy-র set বানিয়ে mex নিই — এটাই Grundy-র সংজ্ঞা।
```text
x = 0
for h in heaps:
x ^= g[h]
return x != 0
```
Sum-of-games: প্রতিটা heap-এর Grundy XOR করি (প্রতিটা যেন একটা Nim pile)। ≠ 0 হলে প্রথম player W — Nim-এর সেই একই rule।
বাকি `two_heap_brute_win` definition-এর সরল recursion (যাচাইয়ের জন্য), আর `assert` গুলো চারভাবে মিলিয়ে দেখে: (১) Grundy period, (২) mex-এর মান, (৩) Grundy=0 ⟺ L, (৪) sum-of-games XOR rule vs brute। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
[0, 1, 2, 0, 1, 2, 0, 1, 2, 0]
True
False
সব test pass!
```
প্রথম লাইন {1,2}-game-এর Grundy (period 3, 0/3/6/9-এ 0 = L)। দ্বিতীয় `[1,2]` → `1^2=3≠0` → True (W)। তৃতীয় `[3,3]` → `0^0=0` → False (L)। তার আগের সব `assert` চুপচাপ pass — Grundy theory আর brute force একমত। সবশেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
এক game-এর Grundy precompute: **O(N · |moves|)** — প্রতিটা position-এ moves দেখে mex (mex নিজে ছোট set-এ প্রায় constant)। Sum-of-games-এ মোট: প্রতিটা game precompute + heap-সংখ্যা বার XOR — গুণফল-state-এর exponential থেকে নেমে **প্রতিটা game-এর আকারের যোগফল**।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(N)** — এক game-এর Grundy array। Sum-of-games-এ সব game-এর সবচেয়ে বড়টার আকার (একই moves হলে একটাই array শেয়ার করা যায়)। brute version memo-র জন্য `O(state)` নেয়, কিন্তু আসল solution তা নয়।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **mex ভুল করা** — mex = set-এ নেই এমন ক্ষুদ্রতম অঋণাত্মক integer; min/max নয় (concept-notes mistake #5)। `mex({1,2}) = 0`।
2. **Grundy = 0-কে W ভাবা** — `g = 0` মানে L (হারা); উল্টে ভাবলে সব W/L উল্টে যায়।
3. **Sum-of-games-এ XOR ভুলে যোগ করা** — combined Grundy = XOR, sum নয় (Nim-এর মতোই)।
4. **next-states ভুল গোনা** — Grundy-তে শুধু **এক চালে** যাওয়া position-এর Grundy নিতে হয়, তাদের next নয়।
5. **এক game-এর Grundy আরেকটায় ভুলে ব্যবহার** — moves/নিয়ম আলাদা হলে Grundy table আলাদা; শেয়ার করার আগে নিশ্চিত হও নিয়ম এক।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CP-Algorithms — Sprague-Grundy & Nim** (