# Thinking Patterns — সমস্যা ভাঙার reusable চিন্তা-ছাঁচ

> এই section-এ 150টা problem আছে, কিন্তু চিন্তার মৌলিক move মাত্র গুটিকয়েক। এই file-টা সেই move গুলোর গাইড — কীভাবে একটা অচেনা problem-কে চেনা টুকরোয় ভাঙবে, কোন লক্ষণ দেখে কোন হাতিয়ার তুলবে, আর কীভাবে নিজের ভাবনাকে যাচাই করবে। Formula মুখস্থ নয়, **চিন্তার অভ্যাস** — সেটাই আসল সম্পদ।

## 1. Brute force আগে, optimize পরে

সবচেয়ে গুরুত্বপূর্ণ অভ্যাস: যত সহজ-নোংরা হোক, **আগে যেকোনো একটা সমাধান** দাঁড় করাও — সব ঘুরে দেখা, সব জোড়া try করা, যা-ই হোক। কারণ:

- Brute force লিখলে problem-টা ঠিকঠাক **বুঝেছ কি না** তা পরিষ্কার হয়
- সেটা ছোট input-এ চালিয়ে **চালাক সমাধানের উত্তর verify** করা যায়
- আর সবচেয়ে দামি — brute force-এর দিকে তাকিয়ে জিজ্ঞেস করা যায়: **"কোন হিসাবটা বারবার হচ্ছে?"** সেই পুনরাবৃত্তিই optimization-এর দরজা।

```text
brute force  ──"কী বারবার হচ্ছে?"──▶  precompute / চালাক structure  ──▶  fast solution
   │                                                                         │
   └────────── ছোট input-এ দুটো মিলিয়ে দেখো (একই উত্তর?) ◀────────────────────┘
```

## 2. "Thinking tweak" mindset — ছোট মোচড়ে বড় বদল

অনেক কঠিন সমাধান আসলে সহজ idea-র একটা ছোট মোচড়। এই প্রশ্নগুলো বারবার করো:

- **প্রশ্নটা উল্টে দিলে?** "অন্তত একটা খারাপ" গোনা কঠিন → "একটাও খারাপ নয়" গোনো (inclusion-exclusion)। প্রতি subarray-র যোগফল নয় → প্রতি element কয়টা subarray-তে আছে (contribution)।
- **উত্তরটাকেই variable ধরলে?** সরাসরি min/max বের করা কঠিন → একটা উত্তর ধরে নিয়ে "এটা কি সম্ভব?" জিজ্ঞেস করো (binary search on answer)।
- **মাঝখানে ভাঙলে?** পুরোটা একসাথে অসম্ভব → দুই অর্ধেক আলাদা করে merge (meet in the middle)।
- **পেছন থেকে ভাবলে?** শেষ অবস্থা পরিষ্কার হলে সেখান থেকে পিছিয়ে আসো (game theory W/L labeling)।

এই মোচড়গুলোই concept-notes জুড়ে বারবার ফিরবে — চিনে রাখো।

## 3. Pattern recognition — X দেখলে Y ভাবো

Interview/contest-এ সবচেয়ে দরকারি দক্ষতা: problem-এর গায়ে লেগে থাকা **লক্ষণ** দেখে হাতিয়ার চেনা। নিচের টেবিলটা মুখস্থ নয়, কিন্তু চোখে গেঁথে নাও:

| যা দেখছ (trigger) | যা ভাববে (technique) | Level |
| --- | --- | --- |
| range sum বারবার লাগছে | prefix sum | 05 |
| range-এ বারবার update | difference array / imos | 05 |
| sorted array-তে জোড়া/triplet খুঁজছ | two pointers | 06 |
| longest/shortest subarray with condition | sliding window | 06 |
| window-এ distinct/count রাখতে হবে | sliding window + hash map | 06 |
| "min of max" বা "max of min" চাই | binary search on answer | 07 |
| উত্তর monotonic (একবার সম্ভব হলে বড়টাও) | binary search on answer | 07 |
| subarray sum = K (negative-সহ) | prefix sum + hash map | 05 |
| "কয় উপায়ে" + বড় n | counting DP | 03, 11 |
| ঘোরালে/উল্টালে এক ধরা হয় | Burnside lemma | 11 |
| পালা করে খেলা, optimal play | game theory / Grundy | 11 |
| "মোট/গড় কত", ভাঙা যায় | linearity of expectation | 11 |
| n ≈ 40, সব subset দেখতে হবে | meet in the middle | 11 |
| একটাই চূড়া/খাদ (unimodal) | ternary search | 11 |
| gcd / divisor / coprime | number theory (Level 1) | 01 |
| বড় সংখ্যার power বা mod | modular exponentiation | 02 |
| "একলা element", জোড়ায় বাকি সব | XOR | 04 |
| subset/state ছোট (n ≤ 20) | bitmask | 04 |
| unsorted array-তে জোড়ার যোগফল = target | hash map (seen set) | 05-06 |
| "kth smallest" / "কয়টা ≤ x" | binary search + counting | 07 |
| sequence-এ power/remainder পুনরাবৃত্ত | cycle / period খোঁজা | 02 |
| interval overlap / সর্বোচ্চ একসাথে | sort + sweep line | 05, 08 |

লক্ষণ আর হাতিয়ারের এই জোড়া যত বেশি চিনবে, তত দ্রুত solution-এ পৌঁছাবে। নতুন problem solve করার পর নিজেকে জিজ্ঞেস করো: "এর trigger কী ছিল?" — উত্তরটা note-এ লিখে রাখো।

## 4. Inherited-idea chains — কাঁধে দাঁড়ানো

এই repo-র প্রতিটা problem আগের কোনো problem-এর idea ধার করে — সেটাই "Inherits from" column। এটা শুধু সাজানোর জন্য নয়, এটা একটা **strategy**:

- নতুন problem আটকে গেলে আগে তার "Inherits from" problem-টা দেখো — উত্তরের অর্ধেক প্রায়ই সেখানে।
- Palindrome (005) আসলে Reverse (004) + compare; Power of Two (059) আসলে popcount-এর (058) `n & (n-1)` trick; Nim (142) আসলে XOR (060) + game labeling (141)।
- চিন্তা করো idea গুলো **lego block** — প্রতিটা নতুন problem পুরোনো block-এর নতুন বিন্যাস। নতুন কিছু শেখা মানে আসলে এক-দুটো block যোগ হওয়া।

## 5. একটা problem কীভাবে পড়বে

Code-এ ঝাঁপানোর আগে এই ধাপগুলো — তাড়াহুড়ো এখানেই সবচেয়ে ব্যয়বহুল:

1. **নিজের ভাষায় লেখো** problem-টা কী চায় — এক-দুই বাক্যে। না পারলে বোঝোইনি।
2. **ছোট একটা উদাহরণ হাতে বানাও**, আর তার উত্তর হাতে বের করো — এটাই পরে verifier।
3. **Constraints দেখো** — n-এর সীমা প্রায়ই হাতিয়ার বলে দেয় (n ≤ 20 → bitmask; n ≤ 10⁵ → O(n log n); n ≈ 40 → meet in the middle)।
4. **Edge case খোঁজো** — খালি input, এক element, সব সমান, negative, 0।
5. **তারপর** brute force → optimize।

## 6. Dry run কীভাবে করবে

Dry run মানে কাগজে নিজে compiler হওয়া — bug ধরা পড়ে শুধু এখানেই:

- একটা **ছোট** input নাও (3-5 element / 4-bit সংখ্যা — যথেষ্ট)।
- প্রতিটা গুরুত্বপূর্ণ variable-এর জন্য একটা **কলাম** বানাও, প্রতি step-এ মান লেখো। (binary search হলে `lo | mid | hi | check`; window হলে `l | r | invariant`)।
- প্রতি step-এ নিজেকে জিজ্ঞেস করো: "এই move-টা কেন **নিরাপদ**?" — উত্তর না জানলে সেটা মুখস্থ, শেখা নয়।
- শেষে হাতের উত্তর আর code-এর উত্তর **মেলাও**। না মিললে — খুঁজে বের করো কোথায় ভাবনা আর code আলাদা হলো। সেই ফাঁক খোঁজাই practice।

## এক লাইনে

> অচেনা problem → নিজের ভাষায় বোঝো → ছোট উদাহরণ → brute force → "কী বারবার হচ্ছে / উল্টে দিলে কী" → trigger চিনে হাতিয়ার তোলো → dry run-এ যাচাই।

এই চক্রটা যত বার চালাবে, তত স্বাভাবিক হবে — আর একদিন নতুন problem দেখলেই হাতিয়ারটা নিজে থেকেই মাথায় আসবে। সেদিনই বুঝবে এই section-এর আসল উপহার পেয়ে গেছ।