# Level 11 — Hard Mixed CP Patterns (boss level)

[ধারণা](concept-notes.md) · [চিত্র ও উদাহরণ](visualization-ideas.md) · [সমস্যার তালিকা](problems/README.md) · [মূল উৎস](source-map.md) · [পুরো শেখার মানচিত্র](../roadmap.md)

> ⚠️ **আগে পড়ো:** 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-র পূর্ণ রূপ অপেক্ষা করছে [DP অধ্যায়](../../12-dynamic-programming/README.md)-এ — সেখানে গেলে এই 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](problems/140-ternary-search.md) | unimodal | CP-Algorithms — <https://cp-algorithms.com/num_methods/ternary_search.html> |
| 141 | [Game Theory Basics](problems/141-game-theory-basics.md) | W/L labeling | CP-Algorithms — <https://cp-algorithms.com/game_theory/sprague-grundy-nim.html> |
| 142 | [Nim Game](problems/142-nim-game.md) | XOR theorem | LeetCode Nim Game — <https://leetcode.com/problems/nim-game/>, CP-Algorithms sprague-grundy page |
| 144 | [Expected Value Problems](problems/144-expected-value-problems.md) | linearity | Classic probability |

### Hard

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 139 | [Meet in the Middle](problems/139-meet-in-the-middle.md) | split + merge | CSES Meet in the Middle — <https://cses.fi/problemset/task/1628> |
| 143 | [Grundy Number Intro](problems/143-grundy-number-intro.md) | mex + XOR | CP-Algorithms sprague-grundy page |
| 145 | [Probability DP](problems/145-probability-dp.md) | probability state | Classic CP pattern (AtCoder Educational DP Contest — I: Coins (সম্পর্কিত অনুশীলন) — <https://atcoder.jp/contests/dp/tasks/dp_i>) |
| 146 | [Burnside Lemma Intro](problems/146-burnside-lemma-intro.md) | average fixed points | CP-Algorithms — <https://cp-algorithms.com/combinatorics/burnside.html> |
| 147 | [Matrix Power on Graphs](problems/147-matrix-power-on-graphs.md) | path counting | Classic CP technique |
| 148 | [Inclusion-Exclusion Hard](problems/148-inclusion-exclusion-hard.md) | forbidden properties | CP-Algorithms — <https://cp-algorithms.com/combinatorics/inclusion-exclusion.html> |
| 149 | [Combinatorics with DP](problems/149-combinatorics-with-dp.md) | counting DP | CSES Bracket Sequences I (সম্পর্কিত অনুশীলন) (<https://cses.fi/problemset/task/2064/>) |
| 150 | [Constructive Math Problems](problems/150-constructive-math-problems.md) | build + invariant | Codeforces constructive tag — <https://codeforces.com/problemset?tags=constructive+algorithms> |

পুরো tracker table (status সহ) আছে [problems/README.md](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) পূর্ণতা পাবে [DP অধ্যায়](../../12-dynamic-programming/README.md)-এ।

## Source map

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