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

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

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

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

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

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-এর আসল উপহার পেয়ে গেছ।