# Level 8 — Greedy Math Tricks (লোভী কিন্তু প্রমাণসহ)

[ধারণা](concept-notes.md) · [চিত্র ও উদাহরণ](visualization-ideas.md) · [সমস্যার তালিকা](problems/README.md) · [মূল উৎস](source-map.md) · [পুরো শেখার মানচিত্র](../roadmap.md)

> Greedy মানে প্রতি step-এ locally সেরা choice — কিন্তু প্রমাণ ছাড়া greedy বিশ্বাস কোরো না। এই level-এ আমরা শিখব কখন greedy কাজ করে, কখন মুখ থুবড়ে পড়ে, আর exchange argument দিয়ে কীভাবে নিজেকে convince করতে হয়।

## এই level এ কী শিখবে?

Greedy algorithm দেখতে সবচেয়ে সহজ — "প্রতিবার best টা নাও, ব্যস!" কিন্তু এই সরলতাই বিপদ। অনেক problem-এ greedy ভুল উত্তর দেয়, আর contest-এ WA খেয়ে তখন বোঝা যায়। তাই এই level-এর আসল শিক্ষা code নয় — **প্রমাণের অভ্যাস**। প্রতিটা greedy-র পেছনে একটা "কেন" থাকতে হবে।

মূল idea গুলো:

- **Exchange argument** — অন্য কোনো optimal solution-কে ধাপে ধাপে আমার greedy solution-এ বদলে দাও; প্রতি বদলে খারাপ না হলে greedy-ও optimal
- **Counterexample শিকার** — coin system {1, 3, 4}-এ greedy fail করে; নিজে counterexample খুঁজতে শেখা greedy-র ঢাল
- **Furthest reach** — jump game-এ "কতদূর পর্যন্ত পৌঁছানো সম্ভব" এই একটা সংখ্যা track করা
- **Reset point** — gas station-এ total fuel ≥ 0 হলেই answer আছে, আর tank negative হলে নতুন start point
- **Two pass** — candy-র মতো problem-এ বাঁ থেকে এক pass, ডান থেকে আরেক pass, তারপর max
- **Earliest finish first** — interval scheduling-এর classic greedy, exchange argument দিয়ে প্রমাণসহ
- **Event sweep** — arrival-এ +1, departure-এ −1 — level 5-এর sweep line আবার ফিরে এলো
- **Median target** — সবাইকে সমান করতে median-এ আনো, mean নয়!

## কেন এই level দরকার?

**Competitive programming (CP) এ:** Codeforces-এর Div 2 A/B/C-র বিশাল অংশ greedy + observation। Sort করে greedy, কোনো invariant ধরে greedy — এগুলো contest-এর রুটি-রুজি। আর greedy ভুল হলে কী হয় সেটা চেনাও সমান জরুরি — তখন DP বা binary search on answer-এ যেতে হয় (level 7 মনে আছে?)।

**Interview এ:** Jump Game, Gas Station, Candy, Non-overlapping Intervals — এগুলো common interview pattern। Interviewer greedy solution শুনে প্রায়ই জিজ্ঞেস করে: "Why does this work?" — তখন exchange argument-এর ভাষায় দু-লাইন বলতে পারলেই বাজিমাত।

**পরের level গুলোতে:** Geometry-তে (level 9) convex hull-এর ভেতরে greedy-ই লুকিয়ে আছে; আর hard mixed patterns-এ (level 11) constructive problem মানেই greedy-র বড় ভাই।

## Prerequisites

- Level 0–7 শেষ করা — বিশেষ করে:
  - Level 5-এর sweep line / prefix idea (108-এ লাগবে)
  - Level 7-এর binary search on answer (112-এর সাথে তুলনা হবে)
- Sorting আর `sort(key=...)` Python-এ স্বচ্ছন্দে ব্যবহার করতে পারা
- Heap-এর নাম শোনা থাকলে ভালো — 109-এ একটা teaser আছে (পুরো heap পরে: `../../08-heap-priority-queue/`)

## Learning goals (checklist)

এই level শেষে নিজেকে জিজ্ঞেস করো:

- [ ] Exchange argument কী — এক লাইনে বলতে পারি, আর interval scheduling-এ apply করে দেখাতে পারি
- [ ] Coin system {1, 3, 4}-এ greedy কোথায় fail করে — counterexample মুখস্থ আছে (n = 6)
- [ ] Jump game-এর furthest reach loop dry run করতে পারি
- [ ] Gas station-এ "total ≥ 0 হলে answer আছে" — এই দাবিটার যুক্তি বুঝি
- [ ] Candy-র two pass কেন এক pass-এ হয় না — উদাহরণ দিয়ে দেখাতে পারি
- [ ] Interval scheduling-এ "earliest finish" কেন, "earliest start" বা "shortest" কেন নয় — counterexample জানি
- [ ] Minimum platforms-এ event sweep-এর +1/−1 trick লিখতে পারি
- [ ] Median কেন mean-কে হারায় (absolute difference-এর জন্য) — ছোট উদাহরণে দেখাতে পারি
- [ ] কোনো greedy দেখলে প্রথম প্রশ্ন করি: "প্রমাণ কী? counterexample আছে কি?"

## Problem list

মোট 10টা problem — 1টা Easy, 8টা Medium, 1টা Hard।

### Easy

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 103 | [Minimum Coins Basic](problems/103-minimum-coins-basic.md) | canonical greedy | Classic exercise (greedy fails on {1,3,4} — দেখাও) |

### Medium

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 104 | [Jump Game](problems/104-jump-game.md) | furthest reach | LeetCode — <https://leetcode.com/problems/jump-game/> |
| 105 | [Gas Station](problems/105-gas-station.md) | reset point | LeetCode — <https://leetcode.com/problems/gas-station/> |
| 107 | [Interval Scheduling](problems/107-interval-scheduling.md) | earliest finish | LeetCode Non-overlapping Intervals — <https://leetcode.com/problems/non-overlapping-intervals/>, CSES Movie Festival — <https://cses.fi/problemset/task/1629> |
| 108 | [Minimum Platforms](problems/108-minimum-platforms.md) | event sweep | Classic interview problem (railway platform) |
| 109 | [Rearrange with Constraints](problems/109-rearrange-with-constraints.md) | most frequent first | LeetCode Reorganize String — <https://leetcode.com/problems/reorganize-string/> |
| 110 | [Maximum Product by Splitting](problems/110-maximum-product-splitting.md) | break into 3s | LeetCode Integer Break — <https://leetcode.com/problems/integer-break/> |
| 111 | [Make Array Equal with Minimum Moves](problems/111-make-array-equal-min-moves.md) | median target | LeetCode Minimum Moves to Equal Array Elements II — <https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/>, CSES Stick Lengths — <https://cses.fi/problemset/task/1074> |
| 112 | [Minimize Maximum Difference](problems/112-minimize-maximum-difference.md) | sort + adjacent / BSoA | Classic exercise |

### Hard

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 106 | [Candy Distribution](problems/106-candy-distribution.md) | two pass | LeetCode Candy — <https://leetcode.com/problems/candy/> |

পুরো tracker table (status সহ) আছে [problems/README.md](problems/README.md)-তে।

## Recommended order

1. **103** — প্রথমেই greedy-র fail case দেখো; এই ধাক্কাটা খেয়ে শুরু করলে বাকি level-এ সাবধান থাকবে
2. **104 → 105** — furthest reach আর reset point; দুটোই "এক pass-এ এক number track" ঘরানার
3. **107** — exchange argument-এর সবচেয়ে পরিষ্কার উদাহরণ; এটা ভালো করে বোঝো
4. **108** — level 5-এর sweep line-এর সাথে reunion
5. **106** — two pass; একটু কঠিন, তাই interval-এর পরে
6. **109 → 110** — frequency greedy আর math greedy
7. **111 → 112** — median target, তারপর শেষে level 7-এর binary search on answer-এর সাথে মিলিয়ে দেখো

## Common mistakes (সাধারণ ভুল)

1. **প্রমাণ ছাড়া greedy বিশ্বাস করা** — সবচেয়ে বড় ভুল। "মনে হচ্ছে কাজ করবে" আর "কাজ করে" এক না। অন্তত 2-3টা ছোট case হাতে চালাও, আর fail case খোঁজার চেষ্টা করো।
2. **Coin change-এ সব system-এ greedy চালানো** — {1, 3, 4} দিয়ে 6 বানাও: greedy দেয় 4+1+1 = 3টা coin, optimal 3+3 = 2টা। Canonical system (যেমন টাকার নোট) এ greedy ঠিক, arbitrary system-এ DP লাগে।
3. **Interval scheduling-এ start time দিয়ে sort করা** — earliest start বেছে নিলে একটা লম্বা interval পুরো দিন খেয়ে ফেলতে পারে। Finish time দিয়ে sort করো।
4. **Gas station-এ O(n²) brute force** — প্রতিটা start থেকে simulate করলে slow; reset point observation-এ এক pass-এই হয়।
5. **Candy এক pass-এ করার চেষ্টা** — ডানদিকের neighbor-এর তথ্য বাঁ থেকে যেতে যেতে জানা যায় না; দুই দিক থেকে দুই pass লাগবেই (অথবা আরো চালাক কিছু, কিন্তু আগে two pass বোঝো)।
6. **Median-এর বদলে mean-এ আনা** — sum of absolute differences minimize করতে median লাগে; mean জেতে squared difference-এ। দুটো গুলিয়ে ফেললে WA।
7. **Sort করতে ভুলে যাওয়া** — অনেক greedy-র প্রথম step-ই sort; unsorted data-য় greedy logic ভেঙে পড়ে।
8. **Reorganize string-এ feasibility check না করা** — সবচেয়ে frequent character-এর count `(n + 1) // 2`-এর বেশি হলে অসম্ভব; আগে এটা check করো।

## পরের level এ যাওয়ার আগে checklist

- [ ] 10টা problem-ই অন্তত একবার নিজে solve করেছি
- [ ] {1, 3, 4} coin counterexample টা না দেখে লিখে দেখাতে পারি
- [ ] Interval scheduling-এর exchange argument টা নিজের ভাষায় (বাংলায়!) কাউকে বুঝিয়ে বলেছি
- [ ] Candy-র two pass-এ কোন pass কী guarantee দেয় — table এঁকে দেখিয়েছি
- [ ] Median vs mean — তিনটা সংখ্যার উদাহরণে হাতে হিসাব করে পার্থক্য দেখেছি
- [ ] 112-তে greedy আর binary search on answer — দুই পথের তুলনা ভেবেছি
- [ ] অন্তত একটা problem-এ আমার প্রথম greedy idea ভুল ছিল, আর আমি নিজেই counterexample খুঁজে পেয়েছি

সব টিক দিতে পারলে — চলো [Level 9: Geometry & Coordinate Math](../09-geometry-coordinate-math/README.md)-এ।

## Source map

এই folder-এর প্রতিটা concept আর problem কোথা থেকে এসেছে, কোন link official, আর কোনটা original লেখা — সব হিসাব আছে [source-map.md](source-map.md)-তে।