Skip to content

Problems — Level 8: Greedy Math Tricks

এই folder-এ Level 8-এর 10টা problem-এর note থাকবে। প্রতিটা problem-এর জন্য আলাদা একটা .md file — সেখানে থাকবে নিজের ভাষায় problem বোঝা, greedy idea, প্রমাণ বা counterexample, dry run, code, আর ভুল থেকে শেখা। এই level-এ "প্রমাণ" section-টাই হৃদপিণ্ড — greedy কেন কাজ করে সেটা না লিখে কোনো note শেষ কোরো না।

কীভাবে problem গুলো use করবে?

প্রতিটা problem-এর note লেখা হয় ../../../templates/math-problem-note-template.md follow করে — ২০টা section-এর একটা template, problem বোঝা থেকে brute force → optimization → dry run → complexity → "ভবিষ্যতের আমাকে এক লাইনে কী বলব" পর্যন্ত। Greedy-র জন্য বিশেষ নিয়ম: template-এর intuition section-এ exchange argument বা counterexample — দুটোর অন্তত একটা লিখতেই হবে।

নিয়মটা সহজ:

  1. Table থেকে একটা problem নাও (recommended order ../README.md-তে আছে)
  2. আগে নিজে খাতায় solve করার চেষ্টা করো — greedy idea মাথায় এলে আগে counterexample খোঁজো, অন্তত 5 মিনিট
  3. তারপর note file বানাও/পড়ো, নিজের approach-এর সাথে মেলাও
  4. Solve হয়ে গেলে Status planned থেকে done করে দাও

Tracker table

# Problem Difficulty Pattern Inherits from Source Note file Status
103 Minimum Coins Basic Easy canonical greedy — Classic exercise (greedy fails on {1,3,4}) 103-minimum-coins-basic.md planned
104 Jump Game Medium furthest reach — LeetCode — https://leetcode.com/problems/jump-game/ 104-jump-game.md planned
105 Gas Station Medium reset point 104 LeetCode — https://leetcode.com/problems/gas-station/ 105-gas-station.md planned
106 Candy Distribution Hard two pass — LeetCode Candy — https://leetcode.com/problems/candy/ 106-candy-distribution.md planned
107 Interval Scheduling Medium earliest finish — LeetCode Non-overlapping Intervals — https://leetcode.com/problems/non-overlapping-intervals/, CSES Movie Festival — https://cses.fi/problemset/task/1629 107-interval-scheduling.md planned
108 Minimum Platforms Medium event sweep 080 Classic interview problem (railway platform) 108-minimum-platforms.md planned
109 Rearrange with Constraints Medium most frequent first — LeetCode Reorganize String — https://leetcode.com/problems/reorganize-string/ 109-rearrange-with-constraints.md planned
110 Maximum Product by Splitting Medium break into 3s — LeetCode Integer Break — https://leetcode.com/problems/integer-break/ 110-maximum-product-splitting.md planned
111 Make Array Equal with Minimum Moves Medium 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 111-make-array-equal-min-moves.md planned
112 Minimize Maximum Difference Medium sort + adjacent / BSoA 100 Classic exercise 112-minimize-maximum-difference.md planned

"Inherits from" column-টা কী?

প্রতিটা problem আগের কোনো problem-এর কাঁধে দাঁড়িয়ে আছে। যেমন 105 (Gas Station) আসলে 104 (Jump Game)-এর আত্মীয় — দুটোতেই এক pass-এ একটা সংখ্যা track করে চলা; 108 ফিরিয়ে আনে level 5-এর sweep idea (problem 080); আর 112 দাঁড়িয়ে আছে level 7-এর binary search on answer (problem 100)-এর উপর। আটকে গেলে আগে "Inherits from"-এর problem-টা আবার দেখো।

104 (furthest reach) ──▶ 105 (reset point)
080 [level 5 sweep] ───▶ 108 (event sweep)
100 [level 7 BSoA] ────▶ 112 (minimize max diff)

স্বাধীন শাখা:
103 (coin fail!)   107 (earliest finish)   106 (two pass)
109 (frequency)    110 (break into 3s)     111 (median)

একটা ছোট পরামর্শ

Greedy problem-এ সবচেয়ে বড় ফাঁদ হলো "মনে হচ্ছে কাজ করবে" অনুভূতিটা। প্রতিটা note-এ একটা লাইন রাখো: "আমার প্রথম idea কী ছিল, আর সেটা টিকল কি?" — এই সৎ হিসাবটাই কয়েক মাস পরে সবচেয়ে দামি জিনিস হবে। আর 103 দিয়ে শুরু করতে ভুলো না — greedy-র fail দেখে শুরু করলে বাকি 9টায় সাবধানি চোখ নিয়ে ঢুকবে।

Concept ঝালাই করতে হলে → ../concept-notes.md। ছবি এঁকে বুঝতে চাইলে → ../visualization-ideas.md।