# Concept Notes — Greedy Math Tricks (লোভের পেছনের যুক্তি) ## সহজ করে শুরু: এখনকার সিদ্ধান্ত কেন ভবিষ্যৎ নষ্ট করে না Greedy একটি সিদ্ধান্ত নিয়ে তা সাধারণত ফিরিয়ে নেয় না। তাই সিদ্ধান্তের প্রমাণ চাই। Interval scheduling-এ আগে শেষ হওয়া কাজ নিলে পরের কাজের জন্য অন্তত আগের মতোই সময় থাকে—এভাবেই exchange argument তৈরি হয়। **প্রোগ্রামে কোথায় ব্যবহার করবে:** একটি ঘরে সর্বাধিক meeting নেওয়া, reachability পরীক্ষা, interval merge-এর প্রস্তুতি এবং absolute deviation কমাতে median বাছাইয়ে লাগে। **কৌশল বাছার আগে শর্ত:** কয়েকটি test মেলা প্রমাণ নয়। Coin {1,3,4}, amount 6-এ বড় coin আগে নিলে 3টি coin লাগে; 3+3-এ লাগে 2টি। ইচ্ছেমতো coin system-এ এই greedy চলে না। পড়ার ক্রম: এই পরিচয় → নিচের বিস্তারিত ধারণা → [চিত্রে হাতে-কলমে হিসাব](visualization-ideas.md) → [সমস্যার তালিকা](problems/README.md)। প্রতিটি উদাহরণে আগে input, পরে বদলানো state, শেষে output মেলাও। > Greedy-র code প্রায়ই 5 লাইনের — কিন্তু সেই 5 লাইন লেখার সাহস আসে প্রমাণ থেকে। এই note-এর লক্ষ্য: প্রতিটা greedy pattern-এর পেছনের "কেন"-টা ছবি আর ছোট উদাহরণ দিয়ে মাথায় গেঁথে দেওয়া। মুখস্থ নয় — convince হও। ## 1. Greedy মানে কী, আর কখন বিশ্বাস করব? Greedy = প্রতি step-এ **locally** সেরা choice নাও, পেছনে ফিরে তাকিও না। যেমন পাহাড়ে উঠছ আর প্রতি মোড়ে সবচেয়ে খাড়া রাস্তাটা নিচ্ছ — কখনো এতে চূড়ায় পৌঁছাবে, কখনো একটা ছোট টিলায় আটকে যাবে। তাহলে কখন কাজ করে? দুটো জিনিস লাগে: - **Greedy choice property** — locally সেরা choice টা কোনো না কোনো optimal solution-এর অংশ - **Optimal substructure** — choice নেওয়ার পর বাকি problem টা একই রকম ছোট problem এগুলো শুনতে ভারী লাগে, তাই practical নিয়ম: **greedy idea পেলে আগে counterexample খোঁজো।** 5 মিনিট খুঁজে না পেলে exchange argument দিয়ে প্রমাণের চেষ্টা করো। দুটোর একটাও না পারলে greedy টা ঝুঁকিপূর্ণ — DP বা অন্য পথ ভাবো। ## 2. Exchange argument — greedy প্রমাণের প্রধান হাতিয়ার ধারণাটা এক লাইনে: **যেকোনো optimal solution নাও, তার সাথে আমার greedy solution-এর প্রথম যেখানে অমিল, সেখানে optimal-এর choice টা greedy-র choice দিয়ে বদলে (exchange করে) দেখাও যে solution খারাপ হয় না।** বারবার বদলাতে থাকলে optimal টা greedy-তে রূপান্তরিত হয়, কিন্তু মান একই থাকে — তাই greedy-ও optimal। Interval scheduling (earliest finish first) দিয়ে দেখি। ধরো optimal solution O-র প্রথম interval `j`, আর greedy নিয়েছে `g` (সবচেয়ে আগে শেষ হওয়াটা)। তাহলে `finish(g) ≤ finish(j)`। O-তে `j`-এর জায়গায় `g` বসাও: ```text greedy: [--g--] optimal: [----j----] [--পরের গুলো--] g আগে শেষ হয় ⇒ j-এর পরের সব interval g-এর পরেও শুরু হতে পারে ⇒ j-কে g দিয়ে বদলালে কোনো clash হয় না, interval সংখ্যাও কমে না ``` এই বদলে solution খারাপ হলো না — মানে greedy-র প্রথম choice নিরাপদ। বাকিটা একই যুক্তি ছোট problem-এ। এটাই exchange argument-এর পুরো কঙ্কাল। ## 3. Coin change — greedy-র সবচেয়ে বিখ্যাত ফাঁদ Canonical system (যেমন টাকা: 1, 2, 5, 10, 20, 50, 100...) এ greedy ঠিকঠাক: সবচেয়ে বড় coin যতবার পারো নাও। ```python def min_coins_greedy(amount, coins): # coins বড় থেকে ছোট sorted count = 0 for c in coins: count += amount // c amount %= c return count if amount == 0 else -1 print(min_coins_greedy(67, [50, 20, 10, 5, 2, 1])) # 50+10+5+2 = 4 coins ✓ ``` কিন্তু coin set `{1, 3, 4}` দিয়ে 6 বানাও: ```text greedy: 6 → 4 নিলাম (বাকি 2) → 1 নিলাম (বাকি 1) → 1 নিলাম → মোট 3 coin optimal: 3 + 3 → মোট 2 coin ✗ greedy হেরে গেল! ``` কেন fail? 4 নেওয়াটা locally লোভনীয়, কিন্তু বাকি 2-টা গড়তে দুটো 1 লাগে — বড় coin টা ভবিষ্যৎ নষ্ট করল। **শিক্ষা:** greedy-র correctness coin set-এর গঠনের উপর নির্ভর করে; arbitrary set-এ DP লাগে (level 12-র coin change অপেক্ষা করছে)। এই counterexample টা মুখস্থ রাখো — interview-তে "greedy কেন সবসময় কাজ করে না" প্রশ্নের one-shot উত্তর। ## 4. Furthest reach — Jump Game-এর এক-সংখ্যার জাদু Array-র প্রতিটা ঘরে লেখা সেখান থেকে সর্বোচ্চ কত ঘর লাফানো যায়। শেষ ঘরে পৌঁছানো সম্ভব কি? সব path ঘাঁটতে হবে না — শুধু track করো **এখন পর্যন্ত সর্বোচ্চ কোথায় পৌঁছানো সম্ভব**: ```python def can_jump(nums): furthest = 0 for i, x in enumerate(nums): if i > furthest: # এই ঘরেই তো আসা যায় না! return False furthest = max(furthest, i + x) return True ``` Mini dry run (`nums = [2, 3, 1, 1, 4]`): ```text i=0, x=2: furthest = max(0, 0+2) = 2 i=1, x=3: 1 ≤ 2 ✓, furthest = max(2, 1+3) = 4 i=2, x=1: 2 ≤ 4 ✓, furthest = max(4, 3) = 4 i=3, i=4: সবই ≤ 4 → True ``` আর `nums = [3, 2, 1, 0, 4]` হলে: furthest আটকে যায় 3-এ, `i = 4 > 3` → False। কেন greedy ঠিক? কারণ "কোন ঘর থেকে লাফালাম" তথ্যটা দরকারই নেই — পৌঁছানো যায় কি না সেটা শুধু furthest-এর উপর নির্ভর করে। অপ্রয়োজনীয় তথ্য ফেলে দেওয়াই এখানে greedy-র জোর। ## 5. Reset point — Gas Station-এর দুই observation বৃত্তাকার রাস্তায় n টা station; `gain[i] = gas[i] - cost[i]`। কোন station থেকে শুরু করলে পুরো চক্কর সম্ভব? - **Observation 1:** মোট `sum(gain) < 0` হলে কোনো start-ই কাজ করবে না (মোট জ্বালানিই কম)। আর `≥ 0` হলে অন্তত একটা start আছেই। - **Observation 2:** station `s` থেকে শুরু করে station `i`-তে এসে tank negative হলে — `s` থেকে `i`-এর মাঝের **কোনো** station-ই valid start না। কারণ মাঝের যেকোনো station থেকে শুরু করলে `i`-তে পৌঁছানোর সময় tank আরো কম থাকত (পথে জমা fuel হারাচ্ছ)। তাই সোজা `i + 1` থেকে নতুন করে শুরু করো — এটাই reset। ```python def gas_station(gas, cost): total, tank, start = 0, 0, 0 for i in range(len(gas)): gain = gas[i] - cost[i] total += gain tank += gain if tank < 0: start = i + 1 # reset: মাঝের কাউকে আর try করতে হবে না tank = 0 return start if total >= 0 else -1 ``` O(n²) simulate না করে এক pass — দুটো observation মিলেই জাদু। ## 6. Two pass — Candy-তে দুই প্রতিবেশীকে আলাদাভাবে খুশি করা প্রতিটা শিশুর rating আছে; বেশি rating-এর শিশু **দুই পাশের** প্রতিবেশীর চেয়ে বেশি candy পাবে, প্রত্যেকে অন্তত 1টা। সমস্যা: এক pass-এ বাঁ-প্রতিবেশীর শর্ত মেটালেও ডান-প্রতিবেশী তো এখনো দেখাই হয়নি! তাই: - **Pass 1 (বাঁ → ডান):** `rating[i] > rating[i-1]` হলে `candy[i] = candy[i-1] + 1` — শুধু বাঁ দিকের শর্ত guarantee - **Pass 2 (ডান → বাঁ):** `rating[i] > rating[i+1]` হলে `candy[i] = max(candy[i], candy[i+1] + 1)` — ডান দিকের শর্ত, আর `max` নেওয়ায় বাঁ দিকের guarantee ভাঙে না ```python def candy(ratings): n = len(ratings) c = [1] * n for i in range(1, n): # pass 1 if ratings[i] > ratings[i - 1]: c[i] = c[i - 1] + 1 for i in range(n - 2, -1, -1): # pass 2 if ratings[i] > ratings[i + 1]: c[i] = max(c[i], c[i + 1] + 1) return sum(c) ``` Mini dry run (`ratings = [1, 3, 2, 1]`): ```text pass 1: c = [1, 2, 1, 1] (3 > 1 বলে index 1 বাড়ল; বাকি বাড়েনি) pass 2: i=2: 2 > 1 → c[2] = max(1, 1+1) = 2 i=1: 3 > 2 → c[1] = max(2, 2+1) = 3 c = [1, 3, 2, 1] → মোট 7 ``` প্রতিটা ঘরে এখন দুই দিকের শর্তই সত্য — কারণ `max` কখনো কমায় না, শুধু বাড়ায়। ## 7. Event sweep — Minimum Platforms (level 5-এর পুরোনো বন্ধু) ট্রেনের arrival/departure সময় দেওয়া; এক মুহূর্তে সর্বোচ্চ কয়টা ট্রেন station-এ — সেটাই minimum platform। প্রতিটা arrival = `+1` event, departure = `−1` event; সময় ধরে sort করে চলন্ত যোগফলের maximum নাও — হুবহু level 5-এর sweep line / prefix trick: ```python def min_platforms(arrivals, departures): events = [(t, +1) for t in arrivals] + [(t, -1) for t in departures] events.sort() # সমান সময়ে departure (−1) আগে — tuple sort এটা ফ্রি-তে দেয় cur = best = 0 for _, delta in events: cur += delta best = max(best, cur) return best ``` Dry run (arrivals `[900, 940, 950]`, departures `[910, 1200, 1120]`): ```text sorted events: (900,+1) (910,−1) (940,+1) (950,+1) (1120,−1) (1200,−1) running: 1 0 1 2 1 0 best = 2 → 2টা platform যথেষ্ট ``` লক্ষ করো sort-এ `(950, −1)` থাকলে সেটা `(950, +1)`-এর আগে আসত — মানে একই মুহূর্তে ছাড়া ট্রেনের platform-টা আসা ট্রেন পেয়ে যায়। Problem-এর নিয়ম উল্টো হলে event-এ `+1`-কে আগে আনার মতো করে sort key পাল্টাতে হবে — এটা একটা classic edge case। ## 8. Most frequent first — Reorganize String (heap-এর teaser) কোনো দুটো একই character পাশাপাশি থাকবে না — সম্ভব হলে rearrange করো। Greedy intuition: **সবচেয়ে বেশি frequency-র character-টাই সবচেয়ে বড় হুমকি** — তাকে আগে আগে বসাও, ফাঁকে ফাঁকে। Feasibility check: কোনো character-এর count `(n + 1) // 2`-এর বেশি হলে অসম্ভব (ফাঁকই নেই অত)। সহজ Python কৌশল — সবচেয়ে frequent character টা index 0, 2, 4...-এ আগে বসাও, বাকিরা পরের ফাঁকা even ঘর শেষে odd ঘরে: ```python from collections import Counter def reorganize(s): n = len(s) cnt = Counter(s) ch, freq = cnt.most_common(1)[0] if freq > (n + 1) // 2: return "" # অসম্ভব res = [None] * n i = 0 for c, f in cnt.most_common(): # frequency descending for _ in range(f): res[i] = c i += 2 if i >= n: i = 1 # even ঘর শেষ → odd ঘরে যাও return "".join(res) print(reorganize("aab")) # "aba" ``` প্রতিবার "এখন সবচেয়ে frequent কে?" — dynamic ভাবে জানতে চাইলে max-heap লাগে; সেই পুরো গল্প `../../08-heap-priority-queue/`-তে। এখানে শুধু greedy idea-টা চেনো: **বড় বোঝা আগে নামাও।** ## 9. Break into 3s — Integer Break-এর math greedy n-কে অন্তত দুই টুকরো (positive integer) করে গুণফল maximize করো। দাবি: **যত পারো 3 ভাঙো; 4 থাকলে 2+2 রাখো; 1 কখনো রেখো না।** কেন? ```text 6 = 3+3 → 9 কিন্তু 2+2+2 → 8 (3 জেতে) 4 = 2+2 → 4 কিন্তু 3+1 → 3 (1 মানেই অপচয় — গুণে কিছু যোগ করে না) 5-এর বেশি যেকোনো টুকরো ভাঙলে গুণফল বাড়ে: x ≥ 5 হলে 3(x−3) = 3x−9 > x ``` ```python def integer_break(n): if n <= 3: return n - 1 # অন্তত দুই টুকরো বাধ্যতামূলক prod = 1 while n > 4: prod *= 3 n -= 3 return prod * n # শেষে n হবে 2, 3 বা 4 print(integer_break(10)) # 3*3*4 = 36 ``` এটা greedy কারণ এক-একটা local নিয়ম ("3 নাও") সরাসরি ছোট অসমতা দিয়ে প্রমাণিত — exchange argument-এর ক্ষুদ্রতম রূপ। ## 10. Median target — সমান করতে median, mean নয়! সব element সমান করতে হবে; এক move-এ একটা element ±1। মোট move = `sum(|a[i] − target|)` — এটা minimize করে **median**, mean নয়। ছোট উদাহরণে দেখো: ```text a = [1, 2, 100] mean = 34.33 → 34-এ আনলে: 33 + 32 + 66 = 131 move median = 2 → 2-এ আনলে: 1 + 0 + 98 = 99 move ✓ ``` Intuition: target-টা একটু ডানে সরাও — median-এর বাঁয়ে যত element, প্রত্যেকের cost +1; ডানে যত, প্রত্যেকের −1। দুই পাশে সমান সংখ্যা থাকলে (median-এ) সরে লাভ নেই — এটাই minimum। Mean জেতে **squared** difference-এ; absolute difference-এ median-ই রাজা। ```python def min_moves(a): a.sort() m = a[len(a) // 2] return sum(abs(x - m) for x in a) ``` ## 11. Minimize Maximum Difference — greedy নাকি binary search on answer? k টা element বেছে নিয়ে (বা ভাগ করে) maximum gap minimize করার ঘরানার problem-এ দুটো রাস্তা: (1) sort করে **adjacent difference** নিয়ে greedy ভাবা — কারণ sorted array-তে যেকোনো বাছাইয়ের সেরা প্রার্থীরা পাশাপাশি বসে; (2) "answer ≤ x সম্ভব কি?" — এই check monotonic, তাই level 7-এর binary search on answer (BSoA) চলে (`../07-binary-search-on-answer/`)। Problem 112-এ দুই পথ পাশাপাশি দাঁড় করিয়ে তুলনা করবে — কোনটা কখন সহজ, এই বিচারবোধটাই এই level-এর শেষ উপহার। ## এক নজরে pattern গুলো ```text pattern মূল প্রশ্ন প্রমাণের ধরন ───────────────────────────────────────────────────────────────────── canonical greedy বড় coin আগে নিলে ঠিক হবে? counterexample খোঁজো! furthest reach সর্বোচ্চ কোথায় পৌঁছাই? তথ্য কমানো যুক্তি reset point fail করলে কোথা থেকে আবার? observation 1 + 2 two pass দুই দিকের শর্ত একসাথে কীভাবে? max-এ guarantee রক্ষা earliest finish কোন interval আগে? exchange argument event sweep এক মুহূর্তে কয়জন? +1/−1 চলন্ত যোগফল most frequent first কে সবচেয়ে বড় হুমকি? feasibility bound break into 3s কত টুকরোয় ভাঙব? ছোট অসমতা median target কোথায় টেনে আনব? বাঁ-ডান ভারসাম্য ``` পরের ধাপ: প্রতিটা problem-এ ঢোকার আগে [visualization-ideas.md](visualization-ideas.md)-র ছবিগুলো একবার দেখে নাও — greedy-র যুক্তি চোখে দেখলে অর্ধেক প্রমাণ এমনিই হয়ে যায়।