# Problems — Level 11: Hard Mixed CP Patterns

> এই folder-এ Level 11-এর 12টা problem-এর নোট আছে। মনে করিয়ে দিই: এই level interview-এর জন্য **optional**, CP-র জন্য deep — তাড়াহুড়ো নেই, মূল DS topic গুলো (02-13) শেষ করে ফিরলেও চলবে। প্রতিটা problem-এর জন্য আলাদা `.md` file — নিজের ভাষায় বোঝা, চিন্তার ছাঁচ, dry run, code, আর ভুল থেকে শেখা।

## কীভাবে problem গুলো use করবে?

প্রতিটা note লেখা হয় [../../../templates/math-problem-note-template.md](../../../templates/math-problem-note-template.md) follow করে — ২০টা section-এর একটা template, problem বোঝা থেকে brute force → optimization → dry run → complexity → "ভবিষ্যতের আমাকে এক লাইনে কী বলব" পর্যন্ত। এই level-এ template-এর intuition section-টাই হৃদপিণ্ড: প্রতিটা problem আসলে **কোন চেনা টুকরোয় ভাঙছে** — সেটা এক লাইনে লিখে তবেই code-এ হাত দাও।

নিয়মটা সহজ:

1. Table থেকে একটা problem নাও (recommended order [../README.md](../README.md)-তে আছে — game theory trilogy 141-142-143 ভেঙো না!)
2. সংশ্লিষ্ট CP-Algorithms / CSES page-টা একবার চোখ বুলাও, তারপর **না দেখে** ছোট case-এ নিজে হাতে চালাও — অন্তত 30-40 মিনিট
3. তারপর বিদ্যমান নোট পড়ো, নিজের approach-এর সাথে মেলাও
4. নিজের অগ্রগতি আলাদা করে চিহ্নিত করো; “নোট আছে” মানে এই সাইটে ব্যাখ্যা আছে, তুমি সমাধান করেছ—এমন দাবি নয়।

## Tracker table

| # | Problem | Difficulty | Pattern | Inherits from | Source | Note file | নোটের অবস্থা |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 139 | Meet in the Middle | Hard | split + merge | 047, 062 | CSES Meet in the Middle — <https://cses.fi/problemset/task/1628> | [139-meet-in-the-middle.md](139-meet-in-the-middle.md) | নোট আছে |
| 140 | Ternary Search | Medium | unimodal | 091 | CP-Algorithms — <https://cp-algorithms.com/num_methods/ternary_search.html> | [140-ternary-search.md](140-ternary-search.md) | নোট আছে |
| 141 | Game Theory Basics | Medium | W/L labeling | — | CP-Algorithms — <https://cp-algorithms.com/game_theory/sprague-grundy-nim.html> | [141-game-theory-basics.md](141-game-theory-basics.md) | নোট আছে |
| 142 | Nim Game | Medium | XOR theorem | 141, 060 | LeetCode Nim Game — <https://leetcode.com/problems/nim-game/> | [142-nim-game.md](142-nim-game.md) | নোট আছে |
| 143 | Grundy Number Intro | Hard | mex + XOR | 142 | CP-Algorithms sprague-grundy page | [143-grundy-number-intro.md](143-grundy-number-intro.md) | নোট আছে |
| 144 | Expected Value Problems | Medium | linearity | 052 | Classic probability | [144-expected-value-problems.md](144-expected-value-problems.md) | নোট আছে |
| 145 | Probability DP | Hard | probability state | 144 | Classic CP pattern (AtCoder Educational DP Contest — I: Coins (সম্পর্কিত অনুশীলন) — <https://atcoder.jp/contests/dp/tasks/dp_i>) | [145-probability-dp.md](145-probability-dp.md) | নোট আছে |
| 146 | Burnside Lemma Intro | Hard | average fixed points | 044 | CP-Algorithms — <https://cp-algorithms.com/combinatorics/burnside.html> | [146-burnside-lemma-intro.md](146-burnside-lemma-intro.md) | নোট আছে |
| 147 | Matrix Power on Graphs | Hard | path counting | 131 | Classic CP technique | [147-matrix-power-on-graphs.md](147-matrix-power-on-graphs.md) | নোট আছে |
| 148 | Inclusion-Exclusion Hard | Hard | forbidden properties | 044, 050 | CP-Algorithms — <https://cp-algorithms.com/combinatorics/inclusion-exclusion.html> | [148-inclusion-exclusion-hard.md](148-inclusion-exclusion-hard.md) | নোট আছে |
| 149 | Combinatorics with DP | Hard | counting DP | 049, 042 | CSES Bracket Sequences I (সম্পর্কিত অনুশীলন) — <https://cses.fi/problemset/task/2064/> | [149-combinatorics-with-dp.md](149-combinatorics-with-dp.md) | নোট আছে |
| 150 | Constructive Math Problems | Hard | build + invariant | — | Codeforces constructive tag — <https://codeforces.com/problemset?tags=constructive+algorithms> | [150-constructive-math-problems.md](150-constructive-math-problems.md) | নোট আছে |

## "Inherits from" column-টা কী?

এই level-এর শিকড় ছড়িয়ে আছে আগের প্রায় সব level-এ — 139 দাঁড়িয়ে subset enumeration-এর (047, 062) উপর, 142 ফেরায় XOR (060), 147 দাঁড়িয়ে matrix exponentiation-এর (131) উপর, 148 আবার আনে IE আর derangement (044, 050)। আর level-এর ভেতরেই একটা শৃঙ্খল: game theory trilogy 141 → 142 → 143। আটকে গেলে আগে "Inherits from" problem-টায় ফিরে যাও।

```text
047, 062 [subset/bitmask] ──▶ 139 (meet in the middle)
091 [binary search] ───────▶ 140 (ternary search)
141 (W/L label) ──▶ 142 (Nim XOR) ◀── 060 [XOR] ──▶ 143 (Grundy)
052 [birthday/probability] ──▶ 144 (expected value) ──▶ 145 (probability DP)
044 [IE] ──▶ 146 (Burnside)        044, 050 [IE+derangement] ──▶ 148 (hard IE)
131 [matrix expo] ──▶ 147 (matrix power on graphs)
049, 042 [Catalan/Pascal] ──▶ 149 (counting DP)        150 (constructive — আলাদা শাখা)
```

## একটা ছোট পরামর্শ

এই level-এ problem গুলো বড়, কিন্তু আসল কাজ ছোট: **চেনা টুকরো খোঁজা।** Code লেখার আগে নিজেকে জিজ্ঞেস করো — "এটা কি subset-ভাঙা? পেছন-থেকে-label? নাকি invariant-এর খেলা?" উত্তরটা পেয়ে গেলে অর্ধেক কাজ শেষ। আর প্রতিটা game/counting problem-এ ছোট case-এর table হাতে বানিয়ে pattern খোঁজো — এই level-এ table-ই সবচেয়ে বিশ্বস্ত বন্ধু। Python-এর built-in (`pow`, `math.comb`) শেখার পর্বে নিষিদ্ধ, শেখা শেষে পুরস্কার।

Concept ঝালাই করতে → [../concept-notes.md](../concept-notes.md)। ছবি এঁকে বুঝতে → [../visualization-ideas.md](../visualization-ideas.md)।