Skip to content

Problems — Level 11: Hard Mixed CP Patterns

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

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

প্রতিটা note লেখা হয় ../../../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-তে আছে — game theory trilogy 141-142-143 ভেঙো না!)
  2. সংশ্লিষ্ট CP-Algorithms / CSES page-টা একবার চোখ বুলাও, তারপর না দেখে ছোট case-এ নিজে হাতে চালাও — অন্তত 30-40 মিনিট
  3. তারপর note file বানাও/পড়ো, নিজের approach-এর সাথে মেলাও
  4. Solve হয়ে গেলে Status planned থেকে done করে দাও

Tracker table

# Problem Difficulty Pattern Inherits from Source Note file Status
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 planned
140 Ternary Search Medium unimodal 091 CP-Algorithms — https://cp-algorithms.com/num_methods/ternary_search.html 140-ternary-search.md planned
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 planned
142 Nim Game Medium XOR theorem 141, 060 LeetCode Nim Game — https://leetcode.com/problems/nim-game/ 142-nim-game.md planned
143 Grundy Number Intro Hard mex + XOR 142 CP-Algorithms sprague-grundy page 143-grundy-number-intro.md planned
144 Expected Value Problems Medium linearity 052 Classic probability 144-expected-value-problems.md planned
145 Probability DP Hard probability state 144 Classic CP pattern (USACO Guide — https://usaco.guide/) 145-probability-dp.md planned
146 Burnside Lemma Intro Hard average fixed points 044 CP-Algorithms — https://cp-algorithms.com/combinatorics/burnside.html 146-burnside-lemma-intro.md planned
147 Matrix Power on Graphs Hard path counting 131 Classic CP technique 147-matrix-power-on-graphs.md planned
148 Inclusion-Exclusion Hard Hard forbidden properties 044, 050 CP-Algorithms — https://cp-algorithms.com/combinatorics/inclusion-exclusion.html 148-inclusion-exclusion-hard.md planned
149 Combinatorics with DP Hard counting DP 049, 042 CSES Counting Problems — https://cses.fi/problemset/ 149-combinatorics-with-dp.md planned
150 Constructive Math Problems Hard build + invariant — Codeforces constructive tag — https://codeforces.com/problemset?tags=constructive+algorithms 150-constructive-math-problems.md planned

"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-টায় ফিরে যাও।

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। ছবি এঁকে বুঝতে → ../visualization-ideas.md।