# Concept Notes — Hard Mixed CP Patterns (চিন্তার ছাঁচগুলো) ## সহজ করে শুরু: একাধিক ধারণা একসঙ্গে ব্যবহার এখানে একটিমাত্র template নেই। `n` প্রায় 40 হলে subset search দুই ভাগে করা যায়; ছোট state graph হলে DP; impartial game-এ Grundy number; symmetry-র কারণে একই বিন্যাস বারবার গুনলে Burnside বিবেচনা করা যায়। **প্রোগ্রামে কোথায় ব্যবহার করবে:** সীমিত আকারের exhaustive optimization, খেলার state বিশ্লেষণ, symmetry-সহ counting এবং repeated transition-এ এই ধারণাগুলো কাজে লাগে। প্রতিটি সমস্যায় input সীমা দেখে কৌশল বেছে নাও। **কৌশল বাছার আগে শর্ত:** আগে recursion, hashing, graph ও DP-এর মূল ধারণা পড়া ভালো। সাধারণ multi-pile Nim-এ যত পাথর খুশি সরানো যায়; LeetCode Nim Game-এ একটি pile থেকে 1–3টি নেওয়া যায়—নিয়ম ও সূত্র আলাদা। পড়ার ক্রম: এই পরিচয় → নিচের বিস্তারিত ধারণা → [চিত্রে হাতে-কলমে হিসাব](visualization-ideas.md) → [সমস্যার তালিকা](problems/README.md)। প্রতিটি উদাহরণে আগে input, পরে বদলানো state, শেষে output মেলাও। > এই note-এ নতুন কোনো "formula" প্রায় নেই — আছে কয়েকটা **চিন্তার ছাঁচ**, যেগুলো hard problem-কে চেনা টুকরোয় ভাঙে। প্রতিটা ছাঁচের সাথে একটা ছোট, হাতে-চালানো-যায় এমন উদাহরণ আছে — সেগুলোই আসল শিক্ষক। ## 1. Meet in the middle — মাঝখানে ভেঙে দুই দিক থেকে Subset sum: n = 40টা সংখ্যা থেকে কোনো subset-এর যোগফল ঠিক T হয় কি? সব subset = 2⁴⁰ ≈ 10¹² — অসম্ভব। কিন্তু array-টা **দুই অর্ধেকে ভাঙো**: প্রতিটার subset মোটে 2²⁰ ≈ 10⁶। বাঁ অর্ধেকের সব subset-sum বানাও, ডান অর্ধেকেরও; এখন বাঁ-এর প্রতিটা sum `s`-এর জন্য ডানে খোঁজো `T − s` আছে কি না — sorted list-এ binary search বা set lookup: ```python from itertools import combinations from bisect import bisect_left def subset_sums(arr): sums = [] n = len(arr) for mask in range(1 << n): # level 4-এর bitmask enumeration! s = 0 for i in range(n): if mask >> i & 1: s += arr[i] sums.append(s) return sums def meet_in_middle(arr, T): half = len(arr) // 2 L = subset_sums(arr[:half]) R = sorted(subset_sums(arr[half:])) count = 0 for s in L: # R-এ (T − s) কয়বার আছে? lo = bisect_left(R, T - s) while lo < len(R) and R[lo] == T - s: count += 1; lo += 1 return count print(meet_in_middle([1, 2, 3, 4], 5)) # 3টা subset: {1,4}, {2,3}, {1+0|...} ``` Mini dry run (`[1,2] | [3,4]`, T = 5): `L = [0,1,2,3]`, `R = [0,3,4,7]`। `s=1 → চাই 4 ✓`, `s=2 → চাই 3 ✓`, `s=0 → চাই 5 ✗`, `s=3 → চাই 2 ✗`... মোট মিল 3 (পুরো enumeration-এ {1,4}, {2,3}, আর {1,4}-ই অন্য ভাঙনে — নিজে গুনে মেলাও!)। Complexity: O(2^(n/2) · n) — 2⁴⁰ নেমে এলো ~10⁶-এর জগতে। **চেনার লক্ষণ:** n ≈ 34-42 আর "সব subset দেখতে হবে" গন্ধ। Bitmask ঝালাই করতে: `../04-bit-manipulation/`। ## 2. Ternary search — unimodal পাহাড়ের চূড়া Function f-এর একটাই চূড়া (আগে শুধু ওঠে, পরে শুধু নামে = **unimodal**) — চূড়া কোথায়? Binary search চলে না (কোন দিকে যাব বলার মতো "sorted" কিছু নেই), কিন্তু **দুটো** probe নিলেই দিক পাওয়া যায়: ```text m1 m2 f: ▲ • • ╱ ╲ f(m1) < f(m2) মানে চূড়া m1-এর বাঁয়ে নেই ╱ ╲___ → বাঁ অংশ [lo, m1] ছেঁটে ফেলো ``` ```python def ternary_search(f, lo, hi, iters=100): for _ in range(iters): # প্রতি iteration-এ range × 2/3 m1 = lo + (hi - lo) / 3 m2 = hi - (hi - lo) / 3 if f(m1) < f(m2): lo = m1 # চূড়া ডান দিকে else: hi = m2 return (lo + hi) / 2 peak = ternary_search(lambda x: -(x - 3) ** 2 + 5, 0, 10) print(round(peak, 4)) # 3.0 — চূড়া x=3 এ ✓ ``` Integer domain-এ `while hi - lo > 2` দিয়ে শেষে ছোট range-টা সরাসরি check করো। **সাবধান:** unimodal না হলে (দুটো চূড়া) ternary search চুপচাপ ভুল উত্তর দেবে — আগে unimodality-র যুক্তি, তারপর code। Level 7-এর binary search on answer-এর সাথে তুলনা: ওখানে monotonic yes/no, এখানে ওঠা-নামা একটা মান। ## 3. Game theory — পেছন থেকে W/L label দুই player পালা করে চাল দেয়, যে চাল দিতে পারে না সে হারে (normal play)। প্রতিটা position-এ ট্যাগ: **L (losing)** = এখান থেকে যার চাল সে হারবে (দুজনেই নিখুঁত খেললে), **W** = জেতার চাল আছে। নিয়ম দুটোই: ```text position L ⟺ তার সব move যায় W position-এ (যেদিকেই যাও, opponent জেতে) position W ⟺ অন্তত একটা move যায় L position-এ (opponent-কে ফাঁদে ফেলো) ``` উদাহরণ game: stash-এ n পাথর, প্রতি চালে 1, 2 বা 3টা নেওয়া যায়; যে নিতে পারে না (n=0) সে হারে। পেছন থেকে ভরো: ```python def label(N, moves=(1, 2, 3)): win = [False] * (N + 1) # win[0] = False: চাল-ই নেই, হার for n in range(1, N + 1): win[n] = any(n >= m and not win[n - m] for m in moves) return win print([("L", "W")[w] for w in label(8)]) # n: 0 1 2 3 4 5 6 7 8 # L W W W L W W W L ← 4-এর গুণিতকে L! ``` Pattern ফুটে উঠল: `n % 4 == 0` মানে L — পেছন-থেকে-label পদ্ধতি শুধু উত্তর দেয় না, **pattern আবিষ্কার করিয়ে দেয়**, যেটা থেকে O(1) সূত্র বেরোয়। এটাই game problem-এর সাধারণ কৌশল: ছোট case-এ table → pattern → প্রমাণ। ## 4. Nim — XOR-এর theorem আর pairing intuition Nim: কয়েকটা pile, প্রতি চালে যেকোনো **এক** pile থেকে যত খুশি পাথর; চাল-হীন হলে হার। Theorem: ```text সব pile-এর XOR ≠ 0 ⟺ যার চাল সে জিতবে (W) ``` Intuition-টা **pairing/আয়না** দিয়ে: XOR = 0 মানে pile-গুলো bit-এ bit-এ "ভারসাম্যে" আছে। তুমি যা-ই চাল দাও, ভারসাম্য ভাঙবে (XOR ≠ 0 হবে), আর opponent প্রমাণিতভাবে আবার XOR = 0-তে ফিরিয়ে আনতে পারে — যেন তোমার প্রতিটা চালের আয়না-জবাব দিচ্ছে। শেষ position (সব 0, XOR = 0)-এ পৌঁছাবে opponent-এর চালের পরে — মানে চাল-হীন তুমি। উল্টোদিকে XOR ≠ 0 হলে এমন একটা চাল **সবসময় আছে** যা XOR-কে 0 বানায় (সবচেয়ে বড় জ্বলা bit-ওয়ালা pile-টা কমাও) — তুমিই আয়নাধারী হয়ে যাও। ```python def nim_first_player_wins(piles): x = 0 for p in piles: x ^= p return x != 0 print(nim_first_player_wins([3, 4, 5])) # True: 3^4^5 = 2 ≠ 0 print(nim_first_player_wins([1, 2, 3])) # False: 1^2^3 = 0 — ভারসাম্য, তুমি ফাঁদে ``` `[1,2,3]`-এ খেলে দেখো: যা-ই নাও, opponent XOR আবার 0 করে দেবে — হাতে খেলাই সবচেয়ে বড় প্রমাণ। XOR-এর স্বভাব ঝালাই: level 4 (problem 060)। ## 5. Grundy number — সব impartial game-এর সাধারণ মুদ্রা Nim তো এক বিশেষ game; অন্য game-এ XOR theorem চলবে? Sprague-Grundy বলে: **যেকোনো impartial game-এর প্রতিটা position একটা সংখ্যার সমান — তার Grundy number** — আর সেই সংখ্যাটা আচরণ করে Nim pile-এর মতো। সংজ্ঞা: ```text g(position) = mex { g(next) : next = এই position থেকে এক চালে যাওয়া যায় } mex(S) = S-এ নেই এমন ক্ষুদ্রতম অঋণাত্মক integer mex({0,1,3}) = 2, mex({}) = 0 ``` ```python def mex(s): m = 0 while m in s: m += 1 return m # উদাহরণ: n পাথর, নেওয়া যায় 1 বা 2টা def grundy(N): g = [0] * (N + 1) for n in range(1, N + 1): g[n] = mex({g[n - m] for m in (1, 2) if n >= m}) return g print(grundy(7)) # [0, 1, 2, 0, 1, 2, 0, 1] — period 3! ``` দুটো ব্যবহার: (1) `g = 0 ⟺ L position` — W/L এর চেয়ে বেশি তথ্য; (2) **একাধিক স্বাধীন game একসাথে চললে** মোট game-এর Grundy = প্রতিটার Grundy-র **XOR** — এজন্যই Grundy-কে "Nim-মুদ্রা" বলা: সব game ভাঙিয়ে Nim বানিয়ে XOR করো। Sum-of-games-ই Grundy-র আসল শক্তি। ## 6. Expected value — linearity-র জাদু **Linearity of expectation:** `E[X + Y] = E[X] + E[Y]` — আর সবচেয়ে বড় কথা, **X আর Y dependent হলেও!** এটাই probability-র সবচেয়ে underrated অস্ত্র। দুটো classic: **Dice:** দুটো ছক্কার যোগফলের expectation? জটিল distribution লাগবে না: `E[X1 + X2] = E[X1] + E[X2] = 3.5 + 3.5 = 7`। **Coupon collector:** n রকম coupon, প্রতিবার uniformly random একটা পাও — সব কয়টা পেতে গড়ে কত draw? ভাঙো: `T_k` = (k−1)টা পাওয়ার পর k-তম **নতুন** coupon পেতে draw সংখ্যা। নতুন পাওয়ার সম্ভাবনা `p = (n−k+1)/n`, তাই `E[T_k] = n/(n−k+1)` (geometric)। Linearity: ```python def coupon_collector(n): return sum(n / (n - k + 1) for k in range(1, n + 1)) # = n·(1/1 + 1/2 + ... + 1/n) print(round(coupon_collector(4), 3)) # 8.333 — 4 coupon-এ গড়ে ৮.৩৩ draw ``` ছোট sanity check: n=2 → 2·(1 + 1/2) = 3 — প্রথম draw-এ নতুন নিশ্চিত, তারপর গড়ে 2 draw — মিলে যায়। **ছাঁচটা মনে রাখো:** "মোট কত" প্রশ্নকে indicator/ধাপে ভাঙো, প্রতিটার E আলাদা বের করো, যোগ করো — dependence নিয়ে মাথাই ঘামিও না। ## 7. Probability DP — state-এ সম্ভাবনা বওয়া যখন linearity-তে সরাসরি ভাঙা যায় না, তখন DP: state-এ probability (বা expectation) রাখো, transition-এ ছড়িয়ে দাও। উদাহরণ: একটা coin k বার toss — ঠিক h টা head-এর সম্ভাবনা: ```python def prob_heads(k, p=0.5): dp = [1.0] + [0.0] * k # dp[h] = এ পর্যন্ত h-টা head-এর সম্ভাবনা for _ in range(k): new = [0.0] * (k + 1) for h in range(k): new[h] += dp[h] * (1 - p) # tail: head-গোনা একই new[h + 1] += dp[h] * p # head: এক বাড়ল new[k] += dp[k] * (1 - p) dp = new return dp print([round(x, 3) for x in prob_heads(3)]) # [0.125, 0.375, 0.375, 0.125] ``` Dry run (k=2): toss 1 পরে `[0.5, 0.5]`, toss 2 পরে `[0.25, 0.5, 0.25]` ✓। DP-র চেনা কঙ্কাল — শুধু cell-এ count-এর বদলে probability, আর প্রতি স্তরে যোগফল 1 থাকা একটা ফ্রি sanity check। পুরো DP-র রাজ্য: [DP অধ্যায়](../../12-dynamic-programming/README.md)। ## 8. Burnside lemma — ঘোরালে যা এক, তাদের একবার গোনা 3টা পুঁতির necklace, প্রতিটা পুঁতি 2 রঙের — কয়টা **আলাদা** necklace, যদি ঘোরানো necklace একই ধরা হয়? সরাসরি গুনলে গোলমাল; Burnside বলে: ```text distinct objects = (প্রতিটা symmetry-র fixed point সংখ্যার গড়) ``` n = 3, রোটেশন 3টা: 0-ঘোরা (identity), 1-ঘোরা, 2-ঘোরা। ```text identity: সব 2³ = 8 coloring-ই অপরিবর্তিত → fixed = 8 1-ঘোরা: অপরিবর্তিত থাকতে তিন পুঁতিই এক রঙ → fixed = 2 (সব-লাল, সব-নীল) 2-ঘোরা: একই যুক্তি → fixed = 2 উত্তর = (8 + 2 + 2) / 3 = 4 ``` হাতে মিলাও — 4টা necklace: সব-লাল, সব-নীল, 2-লাল-1-নীল, 1-লাল-2-নীল ✓। Intuition: প্রতিটা আসল object গড় হিসাবের সময় তার orbit-এর সব রূপ মিলিয়ে ঠিক একবার গোনা পড়ে — "গড় fixed point" আসলে orbit-গোনারই ছদ্মবেশ। ```python from math import gcd def necklaces(n, k): # n পুঁতি, k রঙ, রোটেশন symmetry return sum(k ** gcd(r, n) for r in range(n)) // n print(necklaces(3, 2)) # 4 ✓ ``` `k^gcd(r,n)` কোথা থেকে এলো — r-ঘোরায় পুঁতিগুলো `gcd(r, n)`-টা cycle-এ ভাগ হয়, প্রতি cycle এক রঙ — এটা problem 146-এ নিজে বের করবে। ## 9. Matrix power on graphs — A^k মানে length-k walk গোনা Adjacency matrix A-তে `A[i][j] = 1` যদি i → j edge থাকে। Matrix গুণের সংজ্ঞা খোলো: ```text A²[i][j] = Σ_m A[i][m] · A[m][j] = "এমন কতগুলো m আছে যাতে i → m → j যাওয়া যায়" = i থেকে j-তে length-2 walk-এর সংখ্যা! ``` Induction-এ: `A^k[i][j]` = length-k walk count। আর level 10-এর matrix exponentiation (131) দিয়ে A^k বের হয় O(V³ log k)-এ — k = 10¹⁸ হলেও! ```python def count_walks(adj, k, mod=10**9 + 7): n = len(adj) def mult(X, Y): return [[sum(X[i][m] * Y[m][j] for m in range(n)) % mod for j in range(n)] for i in range(n)] R = [[int(i == j) for j in range(n)] for i in range(n)] while k: if k & 1: R = mult(R, adj) adj = mult(adj, adj) k >>= 1 return R tri = [[0,1,1],[1,0,1],[1,1,0]] # triangle graph print(count_walks(tri, 2)[0][0]) # 2 — 0→1→0 আর 0→2→0 ``` **সাবধান:** এগুলো walk (vertex repeat চলে), simple path নয়। "ঠিক k ধাপে কয় উপায়ে" ঘরানার problem দেখলেই এই ছাঁচ মনে কোরো। ## 10. Hard inclusion-exclusion — forbidden property-র খেলা ছাঁচ: "অন্তত একটা খারাপ property আছে" এমন গোনা কঠিন; **"কোনো খারাপ property নেই"** গুনতে IE: সব − (১টা property fix) + (২টা fix) − ... Derangement (কেউ নিজের জায়গায় নেই) আবার ফিরে এলো, এবার সূত্রটা IE-চশমায়: ```text D(n) = Σ_{k=0}^{n} (−1)^k · C(n, k) · (n − k)! └─ k-টা নির্দিষ্ট লোক নিজের জায়গায় "আটকে", বাকিরা যেমন খুশি ``` ```python from math import comb, factorial def derangement(n): return sum((-1) ** k * comb(n, k) * factorial(n - k) for k in range(n + 1)) print([derangement(n) for n in range(5)]) # [1, 0, 1, 2, 9] ✓ ``` Hard version-গুলোতে property-র সংখ্যা subset-আকারে বাড়ে — তখন bitmask দিয়ে subset enumerate করে sign `(−1)^popcount(mask)` — level 4-এর bitmask আর level 3-এর IE-র মিলন। আর section 4-এর Mobius (level 10) ছিল এরই সংখ্যাতাত্ত্বিক encode — পুরো বৃত্তটা এখন দেখা যাচ্ছে। ## 11. Counting DP — "কয় উপায়ে" প্রশ্নের ছাঁচ Catalan number মনে আছে (level 3-এর 049)? Balanced bracket sequence গোনা একটা DP-তেই ধরা যায়: state = (কত অক্ষর বসেছে, এখন কত খোলা bracket), transition = `(` বসাও বা `)` বসাও: ```python def count_balanced(n): # n জোড়া bracket # dp[open] = এই মুহূর্তে 'open'-টা খোলা — কয় উপায়ে এলাম dp = {0: 1} for _ in range(2 * n): new = {} for o, ways in dp.items(): if o + 1 <= n: new[o + 1] = new.get(o + 1, 0) + ways # '(' বসালাম if o - 1 >= 0: new[o - 1] = new.get(o - 1, 0) + ways # ')' বসালাম dp = new return dp.get(0, 0) print([count_balanced(n) for n in range(1, 6)]) # [1, 2, 5, 14, 42] — Catalan! ✓ ``` Counting DP-র সাধারণ ছাঁচ: **state = "এ পর্যন্ত যা বানিয়েছি তার সারাংশ"** (পুরো history নয়!), **মান = উপায়সংখ্যা**, transition-এ যোগ। "কয় উপায়ে" দেখলেই এই ছাঁচ; mod 10⁹+7 প্রায়ই সঙ্গী। পূর্ণাঙ্গ চর্চা [DP অধ্যায়](../../12-dynamic-programming/README.md)-এ। ## 12. Constructive — বানাও, নয়তো অসম্ভব প্রমাণ করো Constructive problem: "এমন একটা জিনিস বানিয়ে দাও যার এই এই গুণ আছে — না পারলে বলো impossible"। দুটো মোড একসাথে চালাতে হয়: - **Builder মোড:** ছোট case হাতে বানাও (n = 1, 2, 3...), pattern খোঁজো, pattern-টাকে general construction-এ রূপ দাও - **Prover মোড:** আটকে গেলে জিজ্ঞেস করো — "এমন কোনো রাশি আছে যেটা কোনো operation-এই বদলায় না (**invariant**)?" শুরু আর লক্ষ্যে সেই রাশি না মিললে — impossible, প্রমাণসহ সবচেয়ে সাধারণ invariant — **parity**। উদাহরণ: array-তে এক operation-এ যেকোনো দুটো element-এ +1; সব element সমান করা সম্ভব কি? প্রতি operation মোট sum-এ +2 — `sum-এর parity invariant`। লক্ষ্য `n·x` আকারের sum; n জোড় আর শুরুর sum বিজোড় হলে কোনো x-এই মিলবে না — impossible, এক লাইনে প্রমাণ। (Level 9-এর grid parity — problem 123 — একই পরিবারের সদস্য।) ```python def can_equalize(a): # উপরের game-টা n, s = len(a), sum(a) if n % 2 == 1: return True # n বিজোড়ে sum-এর parity যেকোনো লক্ষ্যে মেলানো যায় return s % 2 == 0 # n জোড়ে n·x সবসময় জোড় — s-ও জোড় হতে হবে ``` **Checklist যখন constructive-এ আটকে যাও:** parity দেখো → sum/XOR invariant দেখো → ছোটতম impossible case খোঁজো → সেটাকে general করো। আর মনে রেখো common mistake #9: এক case-এ না পারা ≠ impossible। ## এক নজরে ছাঁচগুলো ```text ছাঁচ চেনার লক্ষণ মূল চাল ────────────────────────────────────────────────────────────────────── meet in the middle n ≈ 40, সব subset ভাঙো + sort/match ternary search একটাই চূড়া/খাদ দুই probe-এ দিক W/L labeling পালা-খেলা, শেষ থেকে ভাবা যায় পেছন থেকে table Nim / Grundy pile / স্বাধীন game-এর যোগ XOR, mex linearity "মোট/গড় কত" — ভাঙা যায় E যোগ করো, dependence ভুলো probability DP ধাপে ধাপে randomness state-এ probability Burnside ঘোরালে/উল্টালে এক গড় fixed points matrix power "ঠিক k ধাপে কয় উপায়ে" A^k hard IE forbidden properties sign-সহ subset sum counting DP "কয় উপায়ে" + বড় n state = সারাংশ constructive "বানাও বা impossible বলো" build / invariant ``` পরের ধাপ: [visualization-ideas.md](visualization-ideas.md)-এ Nim-এর আয়না আর Burnside-এর necklace আঁকা আছে — তারপর problem 139 দিয়ে শুরু। শেষ level — উপভোগ করো!