Level 8 — Greedy Math Tricks (লোভী কিন্তু প্রমাণসহ)¶
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 | canonical greedy | Classic exercise (greedy fails on {1,3,4} — দেখাও) |
Medium¶
| # | Problem | Pattern | Source |
|---|---|---|---|
| 104 | Jump Game | furthest reach | LeetCode — https://leetcode.com/problems/jump-game/ |
| 105 | Gas Station | reset point | LeetCode — https://leetcode.com/problems/gas-station/ |
| 107 | Interval Scheduling | 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 | event sweep | Classic interview problem (railway platform) |
| 109 | Rearrange with Constraints | most frequent first | LeetCode Reorganize String — https://leetcode.com/problems/reorganize-string/ |
| 110 | Maximum Product by Splitting | break into 3s | LeetCode Integer Break — https://leetcode.com/problems/integer-break/ |
| 111 | Make Array Equal with Minimum Moves | 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 | sort + adjacent / BSoA | Classic exercise |
Hard¶
| # | Problem | Pattern | Source |
|---|---|---|---|
| 106 | Candy Distribution | two pass | LeetCode Candy — https://leetcode.com/problems/candy/ |
পুরো tracker table (status সহ) আছে problems/README.md-তে।
Recommended order¶
- 103 — প্রথমেই greedy-র fail case দেখো; এই ধাক্কাটা খেয়ে শুরু করলে বাকি level-এ সাবধান থাকবে
- 104 → 105 — furthest reach আর reset point; দুটোই "এক pass-এ এক number track" ঘরানার
- 107 — exchange argument-এর সবচেয়ে পরিষ্কার উদাহরণ; এটা ভালো করে বোঝো
- 108 — level 5-এর sweep line-এর সাথে reunion
- 106 — two pass; একটু কঠিন, তাই interval-এর পরে
- 109 → 110 — frequency greedy আর math greedy
- 111 → 112 — median target, তারপর শেষে level 7-এর binary search on answer-এর সাথে মিলিয়ে দেখো
Common mistakes (সাধারণ ভুল)¶
- প্রমাণ ছাড়া greedy বিশ্বাস করা — সবচেয়ে বড় ভুল। "মনে হচ্ছে কাজ করবে" আর "কাজ করে" এক না। অন্তত 2-3টা ছোট case হাতে চালাও, আর fail case খোঁজার চেষ্টা করো।
- Coin change-এ সব system-এ greedy চালানো — {1, 3, 4} দিয়ে 6 বানাও: greedy দেয় 4+1+1 = 3টা coin, optimal 3+3 = 2টা। Canonical system (যেমন টাকার নোট) এ greedy ঠিক, arbitrary system-এ DP লাগে।
- Interval scheduling-এ start time দিয়ে sort করা — earliest start বেছে নিলে একটা লম্বা interval পুরো দিন খেয়ে ফেলতে পারে। Finish time দিয়ে sort করো।
- Gas station-এ O(n²) brute force — প্রতিটা start থেকে simulate করলে slow; reset point observation-এ এক pass-এই হয়।
- Candy এক pass-এ করার চেষ্টা — ডানদিকের neighbor-এর তথ্য বাঁ থেকে যেতে যেতে জানা যায় না; দুই দিক থেকে দুই pass লাগবেই (অথবা আরো চালাক কিছু, কিন্তু আগে two pass বোঝো)।
- Median-এর বদলে mean-এ আনা — sum of absolute differences minimize করতে median লাগে; mean জেতে squared difference-এ। দুটো গুলিয়ে ফেললে WA।
- Sort করতে ভুলে যাওয়া — অনেক greedy-র প্রথম step-ই sort; unsorted data-য় greedy logic ভেঙে পড়ে।
- 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-এ।
Source map¶
এই folder-এর প্রতিটা concept আর problem কোথা থেকে এসেছে, কোন link official, আর কোনটা original লেখা — সব হিসাব আছে source-map.md-তে।