Concept Notes — Hard Mixed CP Patterns (চিন্তার ছাঁচগুলো)¶
এই 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:
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 নিলেই দিক পাওয়া যায়:
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 = জেতার চাল আছে। নিয়ম দুটোই:
position L ⟺ তার সব move যায় W position-এ (যেদিকেই যাও, opponent জেতে)
position W ⟺ অন্তত একটা move যায় L position-এ (opponent-কে ফাঁদে ফেলো)
উদাহরণ game: stash-এ n পাথর, প্রতি চালে 1, 2 বা 3টা নেওয়া যায়; যে নিতে পারে না (n=0) সে হারে। পেছন থেকে ভরো:
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:
Intuition-টা pairing/আয়না দিয়ে: XOR = 0 মানে pile-গুলো bit-এ bit-এ "ভারসাম্যে" আছে। তুমি যা-ই চাল দাও, ভারসাম্য ভাঙবে (XOR ≠ 0 হবে), আর opponent প্রমাণিতভাবে আবার XOR = 0-তে ফিরিয়ে আনতে পারে — যেন তোমার প্রতিটা চালের আয়না-জবাব দিচ্ছে। শেষ position (সব 0, XOR = 0)-এ পৌঁছাবে opponent-এর চালের পরে — মানে চাল-হীন তুমি। উল্টোদিকে XOR ≠ 0 হলে এমন একটা চাল সবসময় আছে যা XOR-কে 0 বানায় (সবচেয়ে বড় জ্বলা bit-ওয়ালা pile-টা কমাও) — তুমিই আয়নাধারী হয়ে যাও।
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-এর মতো। সংজ্ঞা:
g(position) = mex { g(next) : next = এই position থেকে এক চালে যাওয়া যায় }
mex(S) = S-এ নেই এমন ক্ষুদ্রতম অঋণাত্মক integer mex({0,1,3}) = 2, mex({}) = 0
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:
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-এর সম্ভাবনা:
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-র রাজ্য: ../../12-dynamic-programming/।
8. Burnside lemma — ঘোরালে যা এক, তাদের একবার গোনা¶
3টা পুঁতির necklace, প্রতিটা পুঁতি 2 রঙের — কয়টা আলাদা necklace, যদি ঘোরানো necklace একই ধরা হয়? সরাসরি গুনলে গোলমাল; Burnside বলে:
n = 3, রোটেশন 3টা: 0-ঘোরা (identity), 1-ঘোরা, 2-ঘোরা।
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-গোনারই ছদ্মবেশ।
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 গুণের সংজ্ঞা খোলো:
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¹⁸ হলেও!
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-চশমায়:
D(n) = Σ_{k=0}^{n} (−1)^k · C(n, k) · (n − k)!
└─ k-টা নির্দিষ্ট লোক নিজের জায়গায় "আটকে", বাকিরা যেমন খুশি
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 = ( বসাও বা ) বসাও:
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 প্রায়ই সঙ্গী। পূর্ণাঙ্গ চর্চা ../../12-dynamic-programming/-এ।
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 — একই পরিবারের সদস্য।)
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।
এক নজরে ছাঁচগুলো¶
ছাঁচ চেনার লক্ষণ মূল চাল
──────────────────────────────────────────────────────────────────────
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-এ Nim-এর আয়না আর Burnside-এর necklace আঁকা আছে — তারপর problem 139 দিয়ে শুরু। শেষ level — উপভোগ করো!