Level 11 — Hard Mixed CP Patterns (boss level)

⚠️ আগে পড়ো: level 10-এর মতো এই level-ও big-tech interview-এর জন্য optional — competitive programming-এর জন্য deep material। Interview-পথে থাকলে নির্দ্বিধায় মূল DS topic গুলোতে (02-13) চলে যাও; সেগুলো শেষ করার পরে এখানে ফিরলে বরং বেশি মজা পাবে — কারণ এই level-এর অনেক pattern (probability DP, counting DP) DP শেখার পরে অর্ধেক ফ্রি হয়ে যায়।

এই level এ কী শিখবে?

এটা math fundamentals-এর শেষ স্টেশন — যেখানে আগের 11টা level-এর hatiyar গুলো মিশে নতুন pattern তৈরি করে। আলাদা আলাদা কোনো একটা theorem নয়; এখানে শেখার জিনিস হলো চিন্তার ছাঁচ — কীভাবে একটা অসম্ভব-দেখতে problem-কে চেনা টুকরোয় ভাঙতে হয়।

মূল idea গুলো:

• Meet in the middle — 2⁴⁰ অসম্ভব, কিন্তু দুটো 2²⁰ + sort/match সম্ভব; brute force-কে মাঝখানে ভেঙে দুই দিক থেকে আসা
• Ternary search — unimodal function (একটাই চূড়া) এ পাহাড়ের চূড়া খোঁজা; binary search-এর ভাই
• Game theory W/L labeling — শেষ অবস্থা থেকে পেছনে হেঁটে প্রতিটা position-এ Win/Lose ট্যাগ
• Nim XOR theorem — সব pile-এর XOR ≠ 0 হলে প্রথম player জেতে; pairing intuition-এ প্রমাণ
• Grundy number — যেকোনো impartial game-এর "Nim-মান"; mex of next states, একাধিক game-এর XOR
• Expected value linearity — expectation যোগে ভাঙা যায়, ঘটনা dependent হলেও! Dice আর coupon collector
• Probability DP — state-এ probability/expectation বয়ে নিয়ে চলা
• Burnside lemma — symmetry-র নিচে গোনা: "average fixed points"; necklace counting-এর জাদু
• Matrix power on graphs — adjacency matrix-এর k-তম power = length-k path count (level 10-এর 131 ফিরে এলো)
• Hard inclusion-exclusion — forbidden property-র উপর IE; derangement আবার, এবার বড় মঞ্চে
• Counting DP — Catalan-ঘরানার গোনা; "কয়টা উপায়ে" প্রশ্নের DP উত্তর
• Constructive — উত্তর নিজে বানাও, আর invariant/parity দিয়ে "impossible" প্রমাণ করো

কেন এই level দরকার?

Competitive programming (CP) এ: এটাই Codeforces Div 2 D/E/F-এর মূল খাদ্য। Constructive tag-এ হাজার হাজার problem; game theory আর expected value নিয়মিত অতিথি; আর meet in the middle জানা-না-জানায় কিছু problem-এ TLE আর AC-র ফারাক।

Interview এ: সরাসরি প্রায় আসে না — তবে দুটো ব্যতিক্রম: expected value-র linearity (probability question-এ) আর counting DP (climbing stairs-ঘরানার "কয় উপায়ে" প্রশ্নে) — এ দুটো common interview pattern-এর সাথে আত্মীয়তা রাখে। বাকিটা CP-র সম্পদ।

পরের পথে: এই level শেষ মানে math fundamentals সম্পূর্ণ। Bitmask-ভিত্তিক meet in the middle-এর শিকড় ../04-bit-manipulation/-এ, আর probability DP / counting DP-র পূর্ণ রূপ অপেক্ষা করছে ../../12-dynamic-programming/-এ — সেখানে গেলে এই level-এর problem গুলো নতুন চোখে দেখো।

Prerequisites

• Level 0-10 (অন্তত 0-8 শক্তভাবে; 10-এর 131 লাগবে 147-এ)
• Level 3-এর combinatorics — inclusion-exclusion (044), derangement (050), Catalan-এর সাথে পরিচয় (049)
• Level 4-এর bitmask subset enumeration (047, 062) — meet in the middle-এর কাঁচামাল (../04-bit-manipulation/)
• Level 4-এর XOR অভ্যাস (060) — Nim-এ লাগবে
• Probability-র বেসিক (level 3-এর 052) — expected value-র জন্য
• Recursion-এ আত্মবিশ্বাস — game state explore করতে হবে

Learning goals (checklist)

এই level শেষে নিজেকে জিজ্ঞেস করো:

• [ ] Meet in the middle কখন প্রয়োগযোগ্য (n ≈ 40-এর subset ঘরানা) — চিনতে পারি, আর দুই অর্ধেক merge-এর কৌশল জানি
• [ ] Ternary search-এর শর্ত (unimodal) আর binary search-এর সাথে পার্থক্য বলতে পারি
• [ ] একটা ছোট game-এর W/L table পেছন থেকে ভরতে পারি
• [ ] Nim-এ XOR ≠ 0 → winning — এই theorem-টা একটা ছোট উদাহরণে খেলে দেখাতে পারি
• [ ] Grundy number-এর সংজ্ঞা (mex of next states) আর games-এর XOR rule জানি
• [ ] Linearity of expectation-এর সবচেয়ে বড় চমক — dependence লাগে না — একটা উদাহরণে ব্যবহার করেছি
• [ ] Burnside-এর n=3 necklace উদাহরণটা (8+2+2)/3 = 4 — হাতে গুনে মিলিয়েছি
• [ ] Adjacency matrix-এর square-এ কেন path count আসে — গুণের সংজ্ঞা খুলে দেখাতে পারি
• [ ] Constructive problem-এ "impossible" দাবি করার আগে কোন invariant খুঁজি — অন্তত দুটো (parity, sum) জানি

Problem list

মোট 12টা problem — 4টা Medium, 8টা Hard।

Medium

#	Problem	Pattern	Source
140	Ternary Search	unimodal	CP-Algorithms — https://cp-algorithms.com/num_methods/ternary_search.html
141	Game Theory Basics	W/L labeling	CP-Algorithms — https://cp-algorithms.com/game_theory/sprague-grundy-nim.html
142	Nim Game	XOR theorem	LeetCode Nim Game — https://leetcode.com/problems/nim-game/, CP-Algorithms sprague-grundy page
144	Expected Value Problems	linearity	Classic probability

Hard

#	Problem	Pattern	Source
139	Meet in the Middle	split + merge	CSES Meet in the Middle — https://cses.fi/problemset/task/1628
143	Grundy Number Intro	mex + XOR	CP-Algorithms sprague-grundy page
145	Probability DP	probability state	Classic CP pattern (USACO Guide — https://usaco.guide/)
146	Burnside Lemma Intro	average fixed points	CP-Algorithms — https://cp-algorithms.com/combinatorics/burnside.html
147	Matrix Power on Graphs	path counting	Classic CP technique
148	Inclusion-Exclusion Hard	forbidden properties	CP-Algorithms — https://cp-algorithms.com/combinatorics/inclusion-exclusion.html
149	Combinatorics with DP	counting DP	CSES Counting Problems (https://cses.fi/problemset/)
150	Constructive Math Problems	build + invariant	Codeforces constructive tag — https://codeforces.com/problemset?tags=constructive+algorithms

পুরো tracker table (status সহ) আছে problems/README.md-তে।

Recommended order

1. 139 → 140 — search-ঘরানার দুটো দিয়ে warmup: ভাঙো-মেলাও আর চূড়া-খোঁজা
2. 141 → 142 → 143 — game theory trilogy: W/L labeling → Nim XOR → Grundy; এই ক্রমেই, লাফিয়ো না
3. 144 → 145 — probability জোড়া: আগে linearity-র জাদু, তারপর DP-তে probability বওয়া
4. 146 — Burnside; একদম আলাদা স্বাদ, fresh মাথায় বোসো
5. 147 — level 10-এর matrix exponentiation-এর graph-রূপ
6. 148 → 149 — counting জোড়া: hard IE তারপর counting DP
7. 150 — শেষ boss: constructive; এতদিনের সব invariant-চিন্তা এখানে কাজে লাগবে

Common mistakes (সাধারণ ভুল)

1. Meet in the middle-এ merge-এর খরচ ভুলে যাওয়া — দুই অর্ধেক বানানো 2^(n/2), কিন্তু match করতে sort + binary search / two pointer না করলে আবার 2^n-এ ফিরে যাবে।
2. Ternary search-কে non-unimodal function-এ চালানো — একাধিক চূড়া থাকলে ternary search ভুল চূড়ায় আটকাবে; আগে unimodality-র যুক্তি দাও।
3. Game theory-তে "greedy move" ভাবা — game-এ locally ভালো চাল মানেই জেতা নয়; W/L definition recursive — "এমন একটা চাল আছে যা opponent-কে L-এ ফেলে"।
4. Nim-এ XOR-এর বদলে sum দেখা — pile-এর যোগফল কিছুই বলে না; XOR-ই একমাত্র সত্য। আর misère variant (শেষ পাথর নিলে হার) আলাদা নিয়ম — গুলিয়ো না।
5. Grundy-তে mex ভুল করা — mex মানে minimum excludant: set-এ নেই এমন ক্ষুদ্রতম অঋণাত্মক integer; min নয়, max-ও নয়।
6. Expected value-তে independence খোঁজা — linearity-র জন্য independence লাগে না; এটা ভুলে গিয়ে অনেকে সহজ problem-কে কঠিন বানিয়ে ফেলে।
7. Burnside-এ identity rotation বাদ দেওয়া — identity-ও একটা group element, আর সে সব coloring fix করে; তাকে বাদ দিলে উত্তর ভুল।
8. Matrix power-এ path আর walk গুলিয়ে ফেলা — A^k গোনে length-k walk (vertex repeat হতে পারে); simple path চাইলে এ পথ নয়।
9. Constructive-এ একটা case-এ আটকে general claim করা — n = 4-এ পারোনি মানেই impossible না; impossible বলতে হলে invariant-প্রমাণ লাগবে, না পারলে আরো খোঁজো।
10. IE-তে sign-এর হিসাব হারানো — k-টা property-র intersection-এ sign (−1)^k; term গোনার আগে sign-এর pattern-টা ছোট case-এ লিখে নাও।

পরের level এ যাওয়ার আগে checklist

এটাই শেষ level — তাই checklist-টা একটু "graduation exam"-ধাঁচের:

• [ ] 12টা problem-ই অন্তত একবার নিজে solve করেছি
• [ ] Meet in the middle-এর subset sum version-টা scratch থেকে লিখতে পারি
• [ ] 1-pile, 2-pile Nim-এর W/L table নিজে বানিয়ে XOR theorem-এর সাথে মিলিয়েছি
• [ ] Grundy দিয়ে একটা ছোট নিজের-বানানো game analyze করেছি
• [ ] Coupon collector-এর expected value linearity দিয়ে বের করেছি
• [ ] Burnside-এর necklace উদাহরণ না দেখে কাউকে বুঝিয়েছি
• [ ] একটা Codeforces constructive problem-এ অন্তত 45 মিনিট নিজে লড়েছি
• [ ] পেছনে তাকিয়ে level 0-এর problem গুলো দেখে হেসেছি

সব টিক দিতে পারলে — math fundamentals সম্পূর্ণ! এবার মূল data structures-এর পথে: arrays থেকে শুরু (../../02-arrays-and-strings/), আর এই level-এর অসমাপ্ত প্রেম (probability DP, counting DP) পূর্ণতা পাবে ../../12-dynamic-programming/-এ।

Source map

এই folder-এর প্রতিটা concept আর problem কোথা থেকে এসেছে, কোন link official, আর কোনটা original লেখা — সব হিসাব আছে source-map.md-তে।